二叉树
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长12分钟
二叉树是一种树形存储结构，每个节点最多有两个子节点，通常叫做左子树和右子树。
更多二叉树的介绍可查看维基百科
注释- 1
- 2
- 4
- 5
- 3
- 6
- 7
最顶部的节点称为根节点 ，在节点下方与该节点直接相连的节点叫做子节点，反过来称为父节点，没有子节点的称为叶子节点 ，从根节点到最底下的叶子节点经过的节点数就是树的高度，也就是树的最大层数。在上面的二叉树中，1是根节点，2和3是1的子节点，1是2的父节点，4，5，6，7是叶子节点，树的高度是3。
上面这个二叉树也称为满二叉树，因为它满足除最后一层以外，其它层的节点都有两个子节点，除了满二叉树，还有一种常提到的是完全二叉树，它的特点是除最后一层以外，其它层都是满的，最后一层要么是满的，要么就是右边缺若干个节点，下面这个就是完全二叉树。
还有一些经常能听到或者用到的二叉树，比如
- 二叉搜索树， 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值， 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，它的左、右子树也分别为二叉排序树，是一种既能快速查找元素，又可以快速插入元素的数据结构，两种操作的平均时间复杂度为O(logN)。
- AVL树，一种高度自平衡的二叉搜索树，在树中任一节点对应的两棵子树的最大高度差为1，之所以要保持平衡，主要是防止二叉搜索树退化为链表，导致效率降低。
- 红黑树，也是一种自平衡的二叉搜索树，但是平衡度没有AVL树高，在红黑树中，从根节点出发到叶子节点的任何一条路径长度都不会超过其它路径的两倍。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。红黑树在Java 中的TreeMap、HashMap、TreeSet中有应用。
- 哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。树的带权路径长度（WPL）指的是，所有叶子结点的权值乘以该叶子结点到根节点的路径长度的总和。哈夫曼树的最主要应用是哈夫曼编码，一种能够实现编码总长度最短的二进制前缀编码。
还有一种树，虽然不是二叉树，但是也经常用到，那就是Trie树，又叫前缀树和字典树，可以用来高效的查找字符串。
关于二叉树，最基础的就是二叉树的遍历，二叉树常见的遍历有以下几种：
- 前序遍历，先访问父节点，再访问左子节点，最后访问右子节点。
- 中序遍历，先访问左子节点，再访问父节点，最后访问右子节点。
- 后序遍历，先访问左子节点，再访问右子节点，最后访问父节点。
- 层次遍历，从上到下，从左到右依次访问节点。
上面这棵树的几种遍历结果。
前序遍历：[1,2,4,5,3,6,7]
中序遍历：[4,2,5,1,6,3,7]
后序遍历：[4,5,2,6,7,3,1]
层次遍历：[1,2,3,4,5,6,7]
下面是二叉树几种遍历方式的Java代码实现，除了层次遍历外，都有递归和迭代的实现。
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Collections;
4import java.util.List;
5
6class TreeNode {
7 int val;
8 TreeNode left;
9 TreeNode right;
10
11 TreeNode(int x) {
12 val = x;
13 }
14}
15
16public class Main {
17
18 public static void main(String[] args) {
19 TreeNode root = buildTree("1,2,4,-,-,5,-,-,3,6,-,-,7,-,-");
20 System.out.println("层序遍历");
21 System.out.println(iterationLevel(root));
22 System.out.println("先序遍历");
23 System.out.println(recursionPreorder(root));
24 System.out.println(iterationPreorder(root));
25 System.out.println("中序遍历");
26 System.out.println(recursionInOrder(root));
27 System.out.println(iterationInOrder(root));
28 System.out.println("后序遍历");
29 System.out.println(recursionPostOrder(root));
30 System.out.println(iterationPostOrder(root));
31 }
32
33 /**
34 * 层次遍历，迭代的方式
35 */
36 public static List<Integer> iterationLevel(TreeNode root) {
37 List<Integer> res = new ArrayList<>();
38 if (root == null) {
39 return res;
40 }
41 ArrayDeque<TreeNode> queue = new ArrayDeque<>();
42 queue.offer(root);
43 while (!queue.isEmpty()) {
44 TreeNode node = queue.poll();
45 res.add(node.val);
46 if (node.left != null) {
47 queue.offer(node.left);
48 }
49 if (node.right != null) {
50 queue.offer(node.right);
51 }
52 }
53 return res;
54 }
55
56
57 /**
58 * 先序遍历，迭代的方式
59 */
60 public static List<Integer> iterationPreorder(TreeNode root) {
61 List<Integer> res = new ArrayList<>();
62 if (root == null) {
63 return res;
64 }
65 ArrayDeque<TreeNode> stack = new ArrayDeque<>();
66 while (!stack.isEmpty() || root != null) {
67 while (root != null) {
68 res.add(root.val);
69 stack.push(root);
70 root = root.left;
71 }
72 root = stack.pop();
73 root = root.right;
74 }
75 return res;
76 }
77
78 /**
79 * 先序遍历，递归的形式
80 */
81 public static List<Integer> recursionPreorder(TreeNode root) {
82 List<Integer> result = new ArrayList<>();
83 recursionPreorder(root, result);
84 return result;
85 }
86
87 public static void recursionPreorder(TreeNode root, List<Integer> result) {
88 if (root == null) {
89 return;
90 }
91 result.add(root.val);
92 recursionPreorder(root.left, result);
93 recursionPreorder(root.right, result);
94 }
95
96 /**
97 * 中序遍历，迭代的方式
98 */
99 public static List<Integer> iterationInOrder(TreeNode root) {
100 List<Integer> res = new ArrayList<>();
101 if (root == null) {
102 return res;
103 }
104 ArrayDeque<TreeNode> stack = new ArrayDeque<>();
105 while (!stack.isEmpty() || root != null) {
106 while (root != null) {
107 stack.push(root);
108 root = root.left;
109 }
110 root = stack.pop();
111 res.add(root.val);
112 root = root.right;
113 }
114 return res;
115 }
116
117 /**
118 * 中序遍历，递归的形式
119 */
120 public static List<Integer> recursionInOrder(TreeNode root) {
121 List<Integer> result = new ArrayList<>();
122 recursionInOrder(root, result);
123 return result;
124 }
125
126 public static void recursionInOrder(TreeNode root, List<Integer> result) {
127 if (root == null) {
128 return;
129 }
130 recursionInOrder(root.left, result);
131 result.add(root.val);
132 recursionInOrder(root.right, result);
133 }
134
135 /**
136 * 后序遍历，迭代的方式
137 */
138 public static List<Integer> iterationPostOrder(TreeNode root) {
139 List<Integer> res = new ArrayList<>();
140 if (root == null) {
141 return res;
142 }
143 ArrayDeque<TreeNode> stack = new ArrayDeque<>();
144 while (!stack.isEmpty() || root != null) {
145 while (root != null) {
146 stack.push(root);
147 res.add(root.val);
148 root = root.right;
149 }
150 root = stack.pop();
151 root = root.left;
152 }
153 Collections.reverse(res);
154 return res;
155 }
156
157 /**
158 * 后序遍历，递归的形式
159 */
160 public static List<Integer> recursionPostOrder(TreeNode root) {
161 List<Integer> result = new ArrayList<>();
162 recursionPostOrder(root, result);
163 return result;
164 }
165
166 public static void recursionPostOrder(TreeNode root, List<Integer> result) {
167 if (root == null) {
168 return;
169 }
170 recursionPostOrder(root.left, result);
171 recursionPostOrder(root.right, result);
172 result.add(root.val);
173 }
174
175 /**
176 * 构建二叉树
177 */
178 public static TreeNode buildTree(String data) {
179 String[] arr = data.split(",");
180 ArrayDeque<String> queue = new ArrayDeque<>();
181 for (String s : arr) {
182 queue.offer(s);
183 }
184 return deserialize(queue);
185 }
186
187 public static TreeNode deserialize(ArrayDeque<String> queue) {
188 if (queue.isEmpty()) {
189 return null;
190 }
191 String s = queue.poll();
192 if ("-".equals(s)) {
193 return null;
194 }
195 TreeNode node = new TreeNode(Integer.parseInt(s));
196 node.left = deserialize(queue);
197 node.right = deserialize(queue);
198 return node;
199 }
200}注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
二叉树binary tree遍历二叉树
1