树

发表于 更新于 分类于 阅读次数： Valine：

树

预备知识

  1. 树：由称作根的节点以及0个或者多个非空字数组成，这些子树每一个根都被来自根r的一条有向的边所连接。
  2. 儿子/父亲/兄弟：每一个子树的根叫做根r的儿子，而r是每一个子树的根的父亲，具有相同父亲节点的称为兄弟。
  3. 树叶：没有儿子节点的称为树叶

树的实现

实现树的一种方法可以是在每一个节点除数据之外还要有一些链，使得该节点的每一个儿子节点都指向他。但是每一个节点的儿子是不确定的，在数据结构中直接建立与子节点的链接是不可行的，这样不清楚需要多少个链

但是我们可以将所有的儿子节点放到树节点的链表中

1
2
3
4
5
6
7
8
9
10
11
//一个树节点的定义，这里就不使用泛型了
class TreeNode{
    //本节点的数据
    String data;
    //第一儿子的链，这样里面相当于嵌套了链表，而firstChild表示头节点
    TreeNode firstChild;
    //下一兄弟节点
    TreeNode nextSibling;
    //定义父节点
    TreeNode parent;
}

image-20220705093937391

现在要实现上面的这一个树

image-20220705103741710

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package 数据结构和算法.树;

import java.util.List;

/**
 * @author 21050
 * @date 2022-07-05 09:27:18
 * @description
 */
public class TreeImpl {


    public static void main(String[] args) {
        TreeNode root=new TreeNode("A");
        TreeNode node1=new TreeNode("B");
        TreeNode node2=new TreeNode("C");
        TreeNode node3=new TreeNode("D");
        TreeNode node4=new TreeNode("E");
        TreeNode node5=new TreeNode("F");
        TreeNode node6=new TreeNode("G");
        TreeNode node7=new TreeNode("H");
        TreeNode node8=new TreeNode("I");

        //根节点添加第一个子节点
        root.addAsChild(root,node1);
        //B节点添加兄弟节点,或者为根节点A添加子节点C,都可以实现
        node1.addAsSib(node1,node2);
        //同理实现其他节点的添加,添加DE
        node1.addAsChild(node1,node3);
        node1.addAsChild(node1,node4);
        //添加F
        node2.addAsChild(node2,node5);
        //添加GHI
        node4.addAsChild(node4,node6);
        node4.addAsChild(node4,node7);
        node4.addAsChild(node4,node8);
    }


}

//一个树节点的定义，这里就不使用泛型了
class TreeNode {
    //本节点的数据
    String data;
    //第一儿子的链，这样里面相当于嵌套了链表，而firstChild表示头节点
    TreeNode firstChild;
    //下一兄弟节点
    TreeNode nextSibling;
    //定义父节点
    TreeNode parent;

    public TreeNode(String data) {
        this.data = data;
    }
    /**
     * @param node    表示当前节点
     * @param newNode 新加入的节点
     *                表示添加子节点
     */
    public void addAsChild(TreeNode node, TreeNode newNode) {
        //为node添加子节点其实为node的firstChild添加兄弟节点
        //如果是叶子节点，就第一个子节点就是newnode
        if (isLeaf(node)) {
            node.firstChild = newNode;
        } else {
            //不是子节点，就在子节点的兄弟链上加上一个节点
            TreeNode temp = node.firstChild;
            addAsSib(temp, newNode);
        }
    }

    //这里添加兄弟节点直接添加到最后了
    public void addAsSib(TreeNode node, TreeNode newNode) {
        TreeNode temp = node;
        while (node.nextSibling != null) {
            node = node.nextSibling;
        }
        node.nextSibling = newNode;
    }

    //是否是叶子节点
    public boolean isLeaf(TreeNode node) {
        return node.firstChild == null;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data='" + data + '\'' +
                '}';
    }
}

当然上面的这个树结构还是存在一定的瑕疵，比如无法判断根节点，总不能给根节点添加兄弟节点，这个时候我们可以在添加一个parent等等，许多元素我们可以自定义添加。

树的遍历

前面已经实现了一个树，那么如果进行遍历？？

前序遍历

前序遍历的是根左右（这是对于二叉树），而对于下面的非二叉树也是相应的规则，只不过这个称为根左中右

image-20220705093937391

这个遍历出来应该是ABDEGHICF

那么遍历的代码，我们首先分析一下递归遍历的顺序，这样方便我们书写代码

image-20220706101053246

1
2
3
4
5
6
7
8
9
10
//传入一个普通树的根节点
public void preorderTraversal(TreeNode root) {
    System.out.println(root);
    if (!isLeaf(root)) {
        preorderTraversal(root.firstChild);
    }
    if (root.nextSibling != null) {
        preorderTraversal(root.nextSibling);
    }
}

image-20220706100444411

中序遍历

多余这个子节点数不确定的树，中序遍历无法进行

后序遍历

后序遍历可以认为左右根，那么这个其实我们也可以根据递归遍历出,但是这样我们就不能立即将这个root输出，因为传入的root是最后才输出的，我们需要先将他的字节点全部遍历完毕。

image-20220705093937391

那么输出的方式为DGHIEBFCA

1
2
3
4
5
6
7
8
9
10
11
12
//传入一个普通树的根节点
public void postOrderTraversal(TreeNode root){
    if (!isLeaf(root)){
        postOrderTraversal(root.firstChild);
    }
    //当第一次到达这里的时候，其实已经找到属于最左边的节点了
    System.out.println(root);
    //查看最左边节点是否有兄弟节点
    if (root.nextSibling!=null){
        postOrderTraversal(root.nextSibling);
    }
}

image-20220706104428125

这个代码的思路和前序遍历相同，只是这个的顺序不同罢了

二叉树

二叉树是我们经常使用到的一个结构，每一个节点都不能超过两个儿子

二叉树的一个性质是一个平均二叉树的深度要比节点个数N小得多，这是性质很重要，其平均深度为N^1/2,即二叉查找树。

实现

二叉树的子节点个数可以确定，那么我们就可以使用左右节点表示两个节点

1
2
3
4
5
class TreeNode{
    String data;
    TreeNode left;
    TreeNode right;
}

现在要实现下面这个二叉树

image-20220707141022177

写到这里我发现，上面实现那个普通的二叉树其实不用直接写函数，直接指定指定即可！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package 数据结构和算法.树;

/**
 * @author 21050
 * @date 2022-07-07 14:06:25
 * @description
 */
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("A");
        TreeNode node1 = new TreeNode("B");
        TreeNode node2 = new TreeNode("C");
        TreeNode node3 = new TreeNode("D");
        TreeNode node4 = new TreeNode("E");
        TreeNode node5 = new TreeNode("F");
        TreeNode node6 = new TreeNode("G");
        TreeNode node7 = new TreeNode("H");

        root.left=node1;
        root.right=node2;
        node1.left=node3;
        node1.right=node4;
        node2.right=node5;
        node4.left=node6;
        node4.right=node7;
    }

}

class TreeNode {
    String data;
    TreeNode left;
    TreeNode right;

    

    public TreeNode(String data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data='" + data + '\'' +
                '}';
    }
}

image-20220707142257449

前序遍历

其实就是上面的普通的改变一下，前面的普通树的遍历，是兄弟节点和子节点之间选择，而这个是左右子节点之间的选择

1
2
3
4
5
6
7
8
9
10
//传入一个二叉树的根节点
public void preorderTraversal(TreeNode root) {
    System.out.println(root);
    if (root.left!=null){
        preorderTraversal(root.left);
    }
    if (root.right!=null){
        preorderTraversal(root.right);
    }
}

image-20220707143002949

中序遍历

中序遍历是左中右

那么这个中序遍历是DBGEHACF

1
2
3
4
5
6
7
8
9
public void inorderTraversal(TreeNode root){
    if (root.left!=null){
        inorderTraversal(root.left);
    }
    System.out.println(root);
    if (root.right!=null){
        inorderTraversal(root.right);
    }
}

image-20220707143703446

后序遍历

后序遍历是左右中，那么这个输出应该是

DGHEBFCA

1
2
3
4
5
6
7
8
9
public void postOrderTraversal(TreeNode root){
    if (root.left!=null){
        postOrderTraversal(root.left);
    }
    if (root.right!=null){
        postOrderTraversal(root.right);
    }
    System.out.println(root);
}

image-20220707144051399

表达式树

二叉树的主要用处之一是在编译器设计领域，我们现在看一个表达式树

image-20220707144703193

在这个结构中叶子节点全部为数字，而其他节点为符号运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package 数据结构和算法.树;

/**
 * @author 21050
 * @date 2022-07-07 14:06:25
 * @description
 */
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("+");
        TreeNode node1 = new TreeNode("+");
        TreeNode node2 = new TreeNode("*");
        TreeNode node3 = new TreeNode("a");
        TreeNode node4 = new TreeNode("*");
        TreeNode node5 = new TreeNode("d");
        TreeNode node6 = new TreeNode("e");
        TreeNode node7 = new TreeNode("b");
        TreeNode node8 = new TreeNode("c");

        root.left=node1;
        root.right=node2;
        node1.left=node3;
        node1.right=node4;
        node2.left=node5;
        node2.right=node6;
        node4.left=node7;
        node4.right=node8;
        root.postOrderTraversal(root);
    }

}

class TreeNode {
    String data;
    TreeNode left;
    TreeNode right;


    //传入一个二叉树的根节点
    public void preorderTraversal(TreeNode root) {
        System.out.print(root);
        if (root.left!=null){
            preorderTraversal(root.left);
        }
        if (root.right!=null){
            preorderTraversal(root.right);
        }
    }

    public void inorderTraversal(TreeNode root){
        if (root.left!=null){
            inorderTraversal(root.left);
        }
        System.out.print(root);
        if (root.right!=null){
            inorderTraversal(root.right);
        }
    }

    public void postOrderTraversal(TreeNode root){
        if (root.left!=null){
            postOrderTraversal(root.left);
        }
        if (root.right!=null){
            postOrderTraversal(root.right);
        }
        System.out.print(root);
    }


    public TreeNode(String data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return data;
    }
}

现在我们使用中序遍历（并没有使用括号判断）

image-20220707145307973

前序遍历

image-20220707145415334

后序遍历

image-20220707145502830

其实我们清除后序遍历出的是后缀表达式，符合计算机的计算，而中序遍历我们人容易读懂

栈实现中缀表达式转换后缀表达式

那么现在我们需要输入一个后缀表达式树，要生成对应的二叉树，这个也要使用到对应的栈空间

加入说现在输入ab+cde+**

  1. 创建一个栈空间，当读到字母的时候，直接压入栈中
  2. 读到符号的时候，我们将栈中的头和次节点弹出栈，作为符号的左右节点，将符号入栈

ab入栈

image-20220707151113137

+入栈，弹出ab作为节点，而+作为新的入栈，然后cde入栈

image-20220707151457780

遇到+，de出栈作为节点

image-20220707151609625

接下来相同的操作，即可完成一个树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static TreeNode beginTree(String str){
        //建立一个栈
        Stack<TreeNode> stack=new Stack<>();
        for (char c:str.toCharArray()){
            //如果是字母，入栈
            if (0<=c-'a'&&c-'a'<=26){
                stack.add(new TreeNode(c+""));
            }else {
                //不是字母出栈
                TreeNode treeNode1=stack.pop();
                TreeNode treeNode2=stack.pop();
                //符号入栈
                TreeNode temp =new TreeNode(c+"");
                //成为子节点
                temp.left=treeNode1;
                temp.right=treeNode2;
                stack.add(temp);
            }
        }
        return stack.get(0);
    }

}

image-20220707153549912

image-20220707153648926

查找树ADT–二叉查找树

二叉查找树：对于树中的每一个节点X，都有左子树中所有项的值小于X，而右子树的所有项的值大于X中的值

在这里我们建议使用CompareTo进行比较，他的比较类型更加广泛

CompareTo的优点

实现

1
2
3
4
5
6
//这里泛型继承compareable是为了方便使用compareto的比较操作
class TreeNode<Object extends Comparable<? super Object>>  {
    Object data;
    TreeNode<Object> left;
    TreeNode<Object> right;
}

contains方法

如果存在则返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param t 表示查找的树的根节点
 * @param x 表示要查找的数据
 */
private boolean contains(Object x, TreeNode<Object> t) {
    //为空，则返回false
    if (t == null) {
        return false;
    }
    //现在比较两个数的值，以便找到我们要找的方法,如果返回小0，则说明t中数据比较大
    int result = x.compareTo(t.data);
    if (result == 0) {
        return false;
    } else if (result < 0) {
        return contains(x, t.left);
    } else {
        return contains(x, t.right);

findmax（）与findmin方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private TreeNode<Object> findMax(TreeNode<Object> t){
    if (t!=null){
        while (t.right!=null){
            t=t.right;
        }
    }
    return t;
}

private TreeNode<Object> findMin(TreeNode<Object> t){
    if (t!=null){
        while (t.left!=null){
            t=t.left;
        }
    }
    return t;
}

insert方法

这里规定了不允许插入相同的值，可以自行按照需求更改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * @param t 表示根节点
     * @param x 表示插入的数据
     * */
    public TreeNode<Object> insert(Object x,TreeNode<Object> t){
        if(t==null){
            return new TreeNode<>(x, null, null);
        }
        int result=x.compareTo(t.data);
        if (result==0){
            System.out.println("不允许插入相同的值");
        }else if (result<0){
            t.left=insert(x,t.left);
        }else {
            t.right=insert(x,t.right);
        }
        return t;
    }

remove方法

remove方法其实是一种比较难的方法，我们这里删除的时候，如果是一个叶子节点，我们直接删除即可，如果有一个子节点，直接使用这个子节点代替删除的节点。

但是如果存在两个子节点，那么我们可以使用这个删除节点的右子树的最小节点代替删除的节点，这样，我们仍旧可以保持查找树的状态，当然也可以使用左子树的最大节点来代替

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param x 表示要删除节点的数据
 * @param t 表示填入的根节点
 * */
private TreeNode<Object> remove(Object x,TreeNode<Object> t){
    if (t==null){
        return t;
    }
    int result= x.compareTo(t.data);
    
    if (result<0){
        t.left=t.remove(x,t.left);
    }else if (result>0){
        t.right=t.remove(x,t.right);
        //如果为0.则表示已经找到，含有两个节点
    }else if (t.right!=null&&t.left!=null){
        //现在要找到右子节点的最小值
        TreeNode<Object> temp=t.findMin(t.right);
        //删除此节点，将这个值替换上去，这里也有两种方式，将找到节点的data直接替换掉要删除的data，而；另外一种则是和我们删除链表的操作一样，这里采用第一种
        t.data=temp.data;
        //现在删除temp
        remove(temp.data,t.right);
    }
    //含有一个或者0个节点
    else {
        t=(t.left!=null)?t.left:t.right;
    }
    return t;
}

实战

现在学生有成绩年龄等等属性，要求编号不同，而且按照同学3的标号为根构造树，排序按照编号进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Student implements Comparable<Student>{
    int order;
    int age;
    int score;

    public Student(int order, int age, int score) {
        this.order = order;
        this.age = age;
        this.score = score;
    }

    @Override
    public int compareTo(Student o) {
        return this.order-o.order;
    }
}

现在思考一个问题，对于这个树来说，哪一个遍历可以按照从小到大进行输出？？？

左中右，中序遍历

在这里给出大家所有代码,其实这里的比较规则我们可以自己定义，比如按照年龄排序，年龄相同按照成绩排序等等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package 数据结构和算法.树;

import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author 21050
 * @date 2022-07-07 14:06:25
 * @description
 */
public class BinaryTree implements Comparator<Student> {
    public static void main(String[] args) {
        Student student1=new Student(1,12,99);
        Student student2=new Student(1,12,98);
        Student student3=new Student(2,56,99);
        Student student4=new Student(3,56,99);
        Student student5=new Student(4,16,88);
        Student student6=new Student(5,3,60);

        //左右节点我们不直接指定，测试插入方法
        TreeNode<Student> treeNode1=new TreeNode<>(student3);


        treeNode1.insert(student1,treeNode1);
        treeNode1.insert(student2,treeNode1);
        treeNode1.insert(student4,treeNode1);
        treeNode1.insert(student5,treeNode1);
        treeNode1.insert(student6,treeNode1);

        treeNode1.inorderTraversal(treeNode1);

    }

    @Override
    public int compare(Student o1, Student o2) {
        return o1.order-o2.order;
    }
}

class TreeNode<Object extends Comparable<? super Object>> {
    Object data;
    TreeNode<Object> left;
    TreeNode<Object> right;

    /**
     * @param t 表示查找的树的根节点
     * @param x 表示要查找的数据
     */
    private boolean contains(Object x, TreeNode<Object> t) {
        //为空，则返回false
        if (t == null) {
            return false;
        }
        //现在比较两个数的值，以便找到我们要找的方法,如果返回小0，则说明t中数据比较大
        int result = x.compareTo(t.data);
        if (result == 0) {
            return false;
        } else if (result < 0) {
            return contains(x, t.left);
        } else {
            return contains(x, t.right);
        }
    }

    private TreeNode<Object> findMax(TreeNode<Object> t){
        if (t!=null){
            while (t.right!=null){
                t=t.right;
            }
        }
        return t;
    }

    private TreeNode<Object> findMin(TreeNode<Object> t){
        if (t!=null){
            while (t.left!=null){
                t=t.left;
            }
        }
        return t;
    }



    /**
     * @param x 表示要删除节点的数据
     * @param t 表示填入的根节点
     * */
    private TreeNode<Object> remove(Object x,TreeNode<Object> t){
        if (t==null){
            return t;
        }
        int result= x.compareTo(t.data);

        if (result<0){
            t.left=t.remove(x,t.left);
        }else if (result>0){
            t.right=t.remove(x,t.right);
            //如果为0.则表示已经找到，含有两个节点
        }else if (t.right!=null&&t.left!=null){
            //现在要找到右子节点的最小值
            TreeNode<Object> temp=t.findMin(t.right);
            //删除此节点，将这个值替换上去，这里也有两种方式，将找到节点的data直接替换掉要删除的data，而；另外一种则是和我们删除链表的操作一样，这里采用第一种
            t.data=temp.data;
            //现在删除temp
            remove(temp.data,t.right);
        }
        //含有一个或者0个节点
        else {
            t=(t.left!=null)?t.left:t.right;
        }
        return t;
    }

    /**
     * @param t 表示根节点
     * @param x 表示插入的数据
     * */
    public TreeNode<Object> insert(Object x,TreeNode<Object> t){
        if(t==null){
            return new TreeNode<>(x, null, null);
        }
        int result=x.compareTo(t.data);
        if (result==0){
            System.out.println("不允许插入相同的值");
        }else if (result<0){
            t.left=insert(x,t.left);
        }else {
            t.right=insert(x,t.right);
        }
        return t;
    }

    public TreeNode(Object data, TreeNode<Object> left, TreeNode<Object> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public TreeNode(Object data) {
        this.data = data;
    }

    public void inorderTraversal(TreeNode<Object> root){
        if (root.left!=null){
            inorderTraversal(root.left);
        }
        System.out.println(root);
        if (root.right!=null){
            inorderTraversal(root.right);
        }
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data=" + data +
                '}';
    }
}

class Student implements Comparable<Student>{
    int order;
    int age;
    int score;

    public Student(int order, int age, int score) {
        this.order = order;
        this.age = age;
        this.score = score;
    }

    @Override
    public int compareTo(Student o) {
        return this.order-o.order;
    }

    @Override
    public String toString() {
        return "Student{" +
                "order=" + order +
                ", age=" + age +
                ", score=" + score +
                '}';
    }
}

image-20220708100933538