树结构基础

一、二叉树

1、为什么需要树

1）数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点：如果要检索具体某个值，或者插入值（按一定顺序）会整体移动，效率较低

2）链式存储方式的分析

优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链按到链表中即可，删除效率也很好）。

缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从头节点开始遍历）

3）树存储方式的分析

可以提高数据存储，读取的效率

比如利用二叉排序树（Binary Sort Tree），既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

2、树的常用术语

节点
根节点
父节点
子节点
叶子节点：没有子节点的节点
节点的权：节点值
路径：从root 节点找到该节点的路线
层
子树
树的高度（最大层数）
森林：多颗子树构成森林

3、二叉树概述

二叉树：每个节点最多只能有两个子节点（左节点和右节点）
满二叉树：二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1（n 为层数）
完全二叉树：二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续

4、二叉树遍历概述

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点

小结：看输出父节点的顺序，就确定是前序，中序还是后序

5、二叉树代码实现

java

package work.rexhao.tree;

/**
 * 二叉树的遍历和查找
 *
 * @author 王铭颢
 * @Date 2022/7/5 10:23
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        System.out.print("先序遍历: ");
        BinaryTree.preOrder(bt.head);//先序遍历：12453
        System.out.println();
        System.out.print("中序遍历: ");
        BinaryTree.infixOrder(bt.head);//中序遍历：42513
        System.out.println();
        System.out.print("后序遍历: ");
        BinaryTree.postOrder(bt.head);//后续遍历：45231
        System.out.println();
        System.out.println("------------");
        System.out.println("先序查找3: " + BinaryTree.preOrderSearch(bt.head, 3));
        System.out.println("先序查找6: " + BinaryTree.preOrderSearch(bt.head, 6));
        System.out.println("中序查找3: " + BinaryTree.infixOrderSearch(bt.head, 3));
        System.out.println("中序查找6: " + BinaryTree.infixOrderSearch(bt.head, 6));
        System.out.println("后序查找3: " + BinaryTree.postOrderSearch(bt.head, 3));
        System.out.println("后序查找6: " + BinaryTree.postOrderSearch(bt.head, 6));
        System.out.println("------------");
        BinaryTree.delTree(bt.head, 2);
        BinaryTree.infixOrder(bt.head);//中序遍历：13
        System.out.println();
        BinaryTree.delTree(bt.head, 6);
        BinaryTree.infixOrder(bt.head);//中序遍历：13
        System.out.println();
        System.out.println("------------");
        bt = new BinaryTree();
        BinaryTree.delNode(bt.head, 2);
        BinaryTree.infixOrder(bt.head);//中序遍历：453
        System.out.println();
    }
}

/**
 * 二叉树
 */
class BinaryTree {
    TreeNode head;

    public BinaryTree() {
        head = new TreeNode(1);
        head.leftNode = new TreeNode(2);
        head.rightNode = new TreeNode(3);
        head.leftNode.leftNode = new TreeNode(4);
        head.leftNode.rightNode = new TreeNode(5);
        /*
        初始化树结构示意图
                 1
               /  \
              2    3
            /  \
           4    5

        先序遍历：12453
        中序遍历：42513
        后续遍历：45231
         */
    }

    /**
     * 先序遍历
     */
    public static void preOrder(TreeNode tn) {
        if (tn != null) {
            System.out.print(tn.getData());
            preOrder(tn.leftNode);
            preOrder(tn.rightNode);
        }
    }

    /**
     * 中序遍历
     */
    public static void infixOrder(TreeNode tn) {
        if (tn != null) {
            infixOrder(tn.leftNode);
            System.out.print(tn.getData());
            infixOrder(tn.rightNode);
        }
    }

    /**
     * 后序遍历
     */
    public static void postOrder(TreeNode tn) {
        if (tn != null) {
            postOrder(tn.leftNode);
            postOrder(tn.rightNode);
            System.out.print(tn.getData());
        }
    }

    /**
     * 先序查找
     */
    public static boolean preOrderSearch(TreeNode tn, int target) {
        if (tn == null) return false;
        if (target == tn.getData()) {
            return true;
        } else if (preOrderSearch(tn.leftNode, target)) {
            return preOrderSearch(tn.leftNode, target);
        } else {
            return preOrderSearch(tn.rightNode, target);
        }
    }

    /**
     * 中序查找
     */
    public static boolean infixOrderSearch(TreeNode tn, int target) {
        if (tn == null) return false;
        if (infixOrderSearch(tn.leftNode, target)) {
            return infixOrderSearch(tn.leftNode, target);
        } else if (target == tn.getData()) {
            return true;
        } else {
            return infixOrderSearch(tn.rightNode, target);
        }
    }

    /**
     * 后序查找
     */
    public static boolean postOrderSearch(TreeNode tn, int target) {
        if (tn == null) return false;
        if (postOrderSearch(tn.leftNode, target)) {
            return postOrderSearch(tn.leftNode, target);
        } else if (postOrderSearch(tn.rightNode, target)) {
            return postOrderSearch(tn.rightNode, target);
        } else {
            return target == tn.getData();
        }
    }

    /**
     * 删除子树
     * 叶子结点：删除节点
     * 非叶子节点：删除子树
     * 注：不删除根节点
     */
    public static void delTree(TreeNode tn, int target) {
        if (tn == null) {
            return;
        }
        if (tn.leftNode != null) {
            if (tn.leftNode.getData() == target) {
                tn.leftNode = null;
                return;
            } else {
                delTree(tn.leftNode, target);
            }
        }
        if (tn.rightNode != null) {
            if (tn.rightNode.getData() == target) {
                tn.rightNode = null;
                return;
            } else {
                delTree(tn.rightNode, target);
            }
        }
    }

    /**
     * 删除节点
     * 叶子节点：删除
     * 非叶子节点（一个子节点）：替代原节点
     * 非叶子节点（两个子节点）：左节点代替原节点
     */
    public static void delNode(TreeNode tn, int target) {
        if (tn == null) return;
        if (tn.leftNode != null) {
            if (tn.leftNode.getData() == target) {
                if (tn.leftNode.rightNode == null && tn.leftNode.leftNode == null) {
                    // 叶子节点
                    tn.leftNode = null;
                } else if (tn.leftNode.rightNode != null && tn.leftNode.leftNode != null) {
                    // 两个节点
                    tn.leftNode = tn.leftNode.leftNode;
                } else {
                    // 一个节点
                    if (tn.leftNode.leftNode != null) {
                        // 左节点
                        tn.leftNode = tn.leftNode.leftNode;
                    } else {
                        // 右节点
                        tn.leftNode = tn.leftNode.rightNode;
                    }
                }
                return;
            } else {
                delNode(tn.leftNode, target);
            }
        }
        if (tn.rightNode != null) {
            if (tn.rightNode.getData() == target) {
                if (tn.rightNode.rightNode == null && tn.rightNode.leftNode == null) {
                    // 叶子节点
                    tn.rightNode = null;
                } else if (tn.rightNode.rightNode != null && tn.rightNode.leftNode != null) {
                    // 两个节点
                    tn.rightNode = tn.rightNode.leftNode;
                } else {
                    // 一个节点
                    if (tn.rightNode.leftNode != null) {
                        // 左节点
                        tn.rightNode = tn.rightNode.leftNode;
                    } else {
                        // 右节点
                        tn.rightNode = tn.rightNode.rightNode;
                    }
                }
                return;
            } else {
                delNode(tn.rightNode, target);
            }
        }
    }

}

/**
 * 二叉树的节点
 */
class TreeNode {
    private int data;
    TreeNode leftNode;
    TreeNode rightNode;

    TreeNode(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }


}

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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

二、顺序存储二叉树

1、顺序存储二叉树的说明

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组

2、顺序存储二叉树的特点

顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为 2*n+1
第n个元素的右子节点为 2*n+2
第n个元素的父节点为 (n-1)/2
n：表示二叉树中的第几个元素（按0开始编号）

3、顺序存储二叉树代码实现

java

package work.rexhao.tree;

/**
 * 顺序存储二叉树
 *
 * @author 王铭颢
 * @Date 2022/7/5 14:56
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        ArrBinaryTree abt = new ArrBinaryTree(7);
        for (int i = 0; i < abt.data.length; i++) {
            abt.data[i] = i + 1;
        }
        System.out.print("前序:");
        ArrBinaryTree.preOrder(abt, 0);
        System.out.println();
        System.out.print("中序:");
        ArrBinaryTree.infixOrder(abt, 0);
        System.out.println();
        System.out.print("后序:");
        ArrBinaryTree.postOrder(abt, 0);
        System.out.println();

    }
}

class ArrBinaryTree {
    int[] data;

    ArrBinaryTree(int maxSize) {
        data = new int[maxSize];
    }

    /**
     * 先序遍历
     */
    public static void preOrder(ArrBinaryTree abt, int index) {
        // 数组越界
        if (index >= abt.data.length) {
            return;
        }
        System.out.print(abt.data[index]);
        preOrder(abt, index * 2 + 1);
        preOrder(abt, index * 2 + 2);
    }

    /**
     * 中序遍历
     */
    public static void infixOrder(ArrBinaryTree abt, int index) {
        // 数组越界
        if (index >= abt.data.length) {
            return;
        }
        infixOrder(abt, index * 2 + 1);
        System.out.print(abt.data[index]);
        infixOrder(abt, index * 2 + 2);
    }

    /**
     * 后序遍历
     */
    public static void postOrder(ArrBinaryTree abt, int index) {
        // 数组越界
        if (index >= abt.data.length) {
            return;
        }
        postOrder(abt, index * 2 + 1);
        postOrder(abt, index * 2 + 2);
        System.out.print(abt.data[index]);
    }
}

三、线索化二叉树

1、前序线索二叉树

...

2、中序线索二叉树

...

3、后序线索二叉树

...

树结构基础 ​

一、二叉树 ​

1、为什么需要树 ​

1）数组存储方式的分析 ​

2）链式存储方式的分析 ​

3）树存储方式的分析 ​

2、树的常用术语 ​

3、二叉树概述 ​

4、二叉树遍历概述 ​

5、二叉树代码实现 ​

二、顺序存储二叉树 ​

1、顺序存储二叉树的说明 ​

2、顺序存储二叉树的特点 ​

3、顺序存储二叉树代码实现 ​

三、线索化二叉树 ​

1、前序线索二叉树 ​

2、中序线索二叉树 ​

3、后序线索二叉树 ​