图解二叉树
二叉树定义:二叉树是每个结点最多有两个子树的树结构。
二叉树的特点:
-
每个节点最多有两个子节点,即二叉树不存在大于2的节点;
-
二叉树的子树有左右之分,其子树的次序不能颠倒。
二叉树的结构:

二叉树的性质:
-
在非空二叉树中,第 i 层的节点总数不超过 2 i-1,i >= 1;
-
深度为 h 的二叉树最多有 2 h - 1 个节点(h>=1),最少有 h 个节点;
-
对于任意一棵二叉树,如果其叶节点总数为 n1,而度数为2的节点总数为 n2,则 n1 = n2+1;
-
具有 n 个节点的完全二叉树的深度为 (Log2n) +1;
-
对于任意一个根节点,如果根节点的下标为n,那么它的左节点下标为 2n+1,右节点下标为 2n+2,根据这点可以很方便的用数组来保存二叉树的节点。
实现二叉树:
1import java.util.ArrayList;
2import java.util.List;
3
4class BinaryTree<E> {
5 // 根节点
6 private Node<E> _root;
7 // 用列表暂时保存下节点
8 private List<Node<E>> nodes = new ArrayList<>();
9
10 public void createTree(E[] array) {
11 if (array.length == 0) {
12 return;
13 }
14 for (E e : array) {
15 nodes.add(new Node<>(null, null, null, e));
16 }
17 // 获取根节点
18 if (nodes.get(0) != null) {
19 _root = nodes.get(0);
20 }
21 // 根据二叉树的特性5来确定每个节点的左右子节点
22 for (int i = 0; i < nodes.size(); i++) {
23 if ((i * 2 + 1) < nodes.size() && nodes.get(i * 2 + 1) != null) {
24 nodes.get(i).left = nodes.get(i * 2 + 1);
25 }
26 if ((i * 2 + 2) < nodes.size() && nodes.get(i * 2 + 2) != null) {
27 nodes.get(i).right = nodes.get(i * 2 + 2);
28 }
29 }
30 }
31
32 // 节点类
33 static class Node<E> {
34 // 父节点暂时没有用到
35 Node<E> parent;
36 // 左节点
37 Node<E> left;
38 // 右节点
39 Node<E> right;
40 // 节点中存储的数据
41 E data;
42
43 Node(Node<E> parent, Node<E> left, Node<E> right, E data) {
44 this.data = data;
45 this.parent = parent;
46 this.left = left;
47 this.right = right;
48 }
49
50 @Override
51 public String toString() {
52 return data.toString();
53 }
54 }
55
56 public static void main(String[] args) {
57 Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8};
58 BinaryTree<Integer> binaryTree = new BinaryTree<>();
59 binaryTree.createTree(array);
60 }
61}
实现二叉树的代码很简单,主要就是通过上述的性质5来确定每一个节点的左右子节点,一层一层的绑定关系,最终就可以将所有的节点联系完整。下面是二叉树生成的整个顺序:

二叉树的遍历:
前面我们生成了一棵二叉树,虽然生成了,但是却不知道如果去遍历二叉树输出每个节点对应的数据,那就等于拿到了某件东西却不会使用,这也是不希望看到的一种情况,下面就看看如果遍历一棵二叉树吧!
-
先序遍历: 首先访问根节点,这也就是为什么上面创建二叉树的时候要保存根节点的用处,根节点访问之后在访问其左子树,最后再访问右子树;在访问左右子树的时候依旧是按照先根然左后右的顺序。文字想必大家都看的模棱两可的,下面看顺序图吧,更直观,更清晰:
image.png
以上就是整个先序遍历的流程,这九个步骤大家应该一眼就能看的懂,用代码更加容易实现:
1 /**
2 * 先序遍历,访问根节点的操作发生在遍历其左右节点之前
3 *
4 * @param node 某个根节点
5 */
6 public void preOrder(Node<E> node) {
7 if (node == null) {
8 return;
9 }
10 System.out.print(node + " ");
11 preOrder(node.left);
12 preOrder(node.right);
13 }
-
中序遍历:首先访问根节点的左子树,直到左子树访问完,回过头来访问根节点,最后访问左子树,这里便不在贴流程图了,简单的把实现代码贴出来:
1 /**
2 * 中序遍历,访问根节点的操作发生在遍历左右节点中间
3 *
4 * @param node 某个根节点
5 */
6 public void inOrder(Node<E> node) {
7 if (node == null) {
8 return;
9 }
10 inOrder(node.left);
11 System.out.print(node + " ");
12 inOrder(node.right);
13 }
-
后序遍历:首先访问根节点的左子树,直到左子树访问完,回到根节点的右子树,访问完,最后访问根节点,照样贴上实现代码:
1 /**
2 * 后序遍历,访问根节点的操作发生在遍历左右节点之后
3 *
4 * @param node 某个根节点
5 */
6 public void postOrder(Node<E> node) {
7 if (node == null) {
8 return;
9 }
10 postOrder(node.left);
11 postOrder(node.right);
12 System.out.print(node + " ");
13 }
至此为止,二叉树的内容就结束了,整个的源码可以扫描下方的二维码,我会将源码奉上,切记多敲几遍,这样就才能在脑海中加深印象,不然看过觉得理解了,三天之后就又抛之脑后了!
如果本文章你发现有不正确或者不足之处,欢迎你在下方留言或者扫描下方的二维码留言也可!

原文始发于微信公众号(Taonce):图解二叉树