java 实现二叉树
复习二叉树，实现树的一系列的操作。
参考：http://www.bilibili.com/video/av10472353/
一、实现最简单粗暴的二叉树
首先实现一个节点类Node，然后在main方法中手工将二叉树拼凑起来，再通过findNode方法遍历该二叉树中的所有节点。
MyBinaryTree1.java
|
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 |
package com.xie.DataStructure.SimpleBinaryTree; public class MyBinaryTree1<E> { public static class Node { Object data = null; Node left = null; Node right = null; public Node() { } public Node(Object data) { this.data = data; } public Node(Object data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } public static void findNode(Node node) { if (node.left != null) { System.out.println(node.data + "的左节点为：" + node.left.data); findNode(node.left); } if (node.right != null) { System.out.println(node.data + "的右节点为：" + node.right.data); findNode(node.right); } return; } public static void main(String[] args) { Node node1 = new Node(4); Node node2 = new Node(3, node1, null); Node node3 = new Node(2); Node root = new Node(1, node2, node3); findNode(root); } } |
运行结果为：
|
1 2 3 |
1的左节点为：3 3的左节点为：4 1的右节点为：2 |
二、实现三种遍历方式
实现三种遍历方式。
MyBinaryTree2.java
|
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 |
package com.xie.DataStructure.SimpleBinaryTree; public class MyBinaryTree2 { public static class Node { Object data = null; Node left = null; Node right = null; public Node() { } public Node(Object data) { this.data = data; } public Node(Object data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } // 根->左->右 public static void preorder(Node node) { if (node != null) { System.out.println(node.data); preorder(node.left); preorder(node.right); } } // 左->根->右 public static void inorder(Node node) { if (node != null) { inorder(node.left); System.out.println(node.data); inorder(node.right); } } // 左->右->根 public static void postorder(Node node) { if (node != null) { postorder(node.left); postorder(node.right); System.out.println(node.data); } } public static void main(String[] args) { Node node1 = new Node(4); Node node2 = new Node(3, node1, null); Node node3 = new Node(2); Node root = new Node(1, node2, node3); System.out.println("先序遍历"); preorder(root); System.out.println("中序遍历"); inorder(root); System.out.println("后序遍历"); postorder(root); } } |
运行结果为（syso纵向显示太浪费文章空间，所以我后期加工弄成横向显示了）：
|
1 2 3 4 5 6 |
先序遍历 1 3 4 2 中序遍历 4 3 1 2 后序遍历 4 3 2 1 |
在这里要注意的是三种遍历的顺序，先序遍历是根->左->右，中序遍历是左->根->右，后序遍历是左->右->根。
三种遍历的难点是递归的用法。个人认为递归的关键在于局部思考问题，不要被绕进递归的过程中，不需要全局地看问题，否则容易被复杂的过程搞晕。我们只需要找到正确的入口、结果两个要素就可以写出正确的递归。
举个例子：我们应该如何写一个先序遍历的方法？
首先要注意方法的返回值。因为我只想输出各节点的数据，所以只需要void就行了。
|
1 2 3 |
public static void preorder(Node node) { ..... } |
接着我们要确定遍历的节点是否null。如果是null，就不存在数据和下面的节点，不需要继续往下遍历，直接结束方法。
|
1 2 3 4 |
if (node != null) { ..... } |
因为先序遍历的顺序是根->左->右，获得一个节点之后应该马上将其数据输出，所以直接syso。
|
1 |
System.out.println(node.data); |
获取了根的数据后，就轮到左节点->右节点。如何获取左节点的数据？当然再次调用先序遍历的方法了（递归），右节点也是同理。
|
1 2 |
preorder(node.left); preorder(node.right); |
总之，递归的难点在于如何正确地调用自身。只要把一个流程写好，递归就不会出现问题。
三、改进构造二叉树的方式，实现更多方法
Tree.java
|
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 |
package com.xie.DataStructure.SimpleBinaryTree; // 根>左,根<右,没有重复节点 public class Tree { public static class Node { int data = 0; Node left = null; Node right = null; public Node() { } public Node(int data) { this.data = data; } public Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } // 知道根节点，就可以操作整棵树 Node root; // 根->左->右 public static void preorder(Node node) { if (node != null) { System.out.println(node.data); preorder(node.left); preorder(node.right); } } // 左->根->右 // 中序遍历正好是从小到大的排序 public static void inorder(Node node) { if (node != null) { inorder(node.left); System.out.println(node.data); inorder(node.right); } } // 左->右->根 public static void postorder(Node node) { if (node != null) { postorder(node.left); postorder(node.right); System.out.println(node.data); } } public static void insert(Tree tree, int value) { Node node = new Node(value); Node temp = null; if (tree.root == null) { tree.root = node; } else { temp = tree.root; while (temp != null) { if (value < temp.data) { if (temp.left == null) { temp.left = node; return; } else { temp = temp.left; } } else { if (temp.right == null) { temp.right = node; return; } else { temp = temp.right; } } } } } public static int getHeight(Node node) { if (node == null) { return 0; } else { // 求左右子树最大高度 int left_height = getHeight(node.left); int right_height = getHeight(node.right); int max = left_height; if (right_height > left_height) { max = right_height; } return max + 1; } } public static int getMax(Node node) { if (node == null) { return -1; } else { int m1 = getMax(node.left); int m2 = getMax(node.right); int n = node.data; int max = m1; if (m2 > max) { max = m2; } if (n > max) { max = n; } return max; } } public static void main(String[] args) { int arr[] = { 6, 3, 8, 2, 5, 1, 7 }; Tree tree = new Tree(); tree.root = null; for (int i : arr) { insert(tree, i); } // preorder(tree.root); inorder(tree.root); System.out.println(getHeight(tree.root)); System.out.println(getMax(tree.root)); } } |
我们详细分析二叉树的实现思路。
（1）二叉排序树的构造
在前面一、二章的例子中，我们都是使用“简单粗暴”的方式，一个一个建立节点，然后组成二叉树。那么问题来了，如果要构成拥有很多节点的二叉树，就要建立一大堆节点，此过程全部需要手工实现（而且结构很复杂），代码量很大。
所以，我们应该写一个构造方法，按照一定的规律（根>左,根<右,没有重复节点）构造一棵二叉排序树（Binary Sort Tree，简称BST）。
这里提一下，二叉排序树也被成为二叉搜索树（Binary Search Tree），实际上就是一回事。二叉排序树只是二叉树中的基础，基本上不会用于生产（生产中使用的都是优化版本，比如AVL、红黑树）。
|
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 |
public static void insert(Tree tree, int value) { Node node = new Node(value); Node temp = null; if (tree.root == null) { tree.root = node; } else { temp = tree.root; while (temp != null) { if (value < temp.data) { if (temp.left == null) { temp.left = node; return; } else { temp = temp.left; } } else { if (temp.right == null) { temp.right = node; return; } else { temp = temp.right; } } } } } |
如果新插入的节点值比“根节点”（不一定是最开始的根节点）的值要小，那么肯定要放在“根节点”的左边。如果“根节点”左节点为空，那么直接插入。如果左节点不为空，那么继续和左节点进行比较，循环此过程。
如果新插入的节点值比“根节点”（不一定是最开始的根节点）的值要大，那么肯定要放在“根节点”的右边。如果“根节点”右节点为空，那么直接插入。如果右节点不为空，那么继续和右节点进行比较，循环此过程。
（2）二叉树的根节点
我们分析二叉树，一定要找到二叉树的入口，也就是根节点。获取根节点之后，才能对整棵二叉树进行各种操作。所以我们需要在Tree类中定义一个Node作为根节点：
|
1 2 |
// 知道根节点，就可以操作整棵树 Node root; |
在构造二叉树时，必须先设置根节点：
|
1 2 3 |
Tree tree = new Tree(); tree.root = null; |
之后各种方法（一般情况下）都需要使用根节点作为参数（获取二叉树的起始位置）。
（3）获取二叉树的高度
想要获取二叉树的高度，只需要获取、比较“根节点”的左右子树的高度，选取最大值，最后+1即可。这里需要用到递归的思想：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public static int getHeight(Node node) { if (node == null) { return 0; } else { // 求左右子树最大高度 int left_height = getHeight(node.left); int right_height = getHeight(node.right); int max = left_height; if (right_height > left_height) { max = right_height; } return max + 1; } } |
（4）获取二叉树中的最大值
想要获取二叉树中的最大值，需要同时比较根节点、左节点、右节点的值。需要用到递归的思想。
|
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 |
public static int getMax(Node node) { if (node == null) { return -1; } else { int m1 = getMax(node.left); int m2 = getMax(node.right); int n = node.data; int max = m1; if (m2 > max) { max = m2; } if (n > max) { max = n; } return max; } } |
我们着眼于局部。每次只需要比较三个节点的大小，获取Max值，递归此过程即可。
（5）二叉排序树的中序遍历
只要是二叉排序树，中序遍历出来的数据一定是按照从小到大的顺序排列。所以二叉排序树常用来排序（废话）。
四、总结
二叉树可以分出很多种类，比如B+、B、B-树，红黑树…均有其独立的实现方法，但是万变不离其宗，只要分析树的操作流程，再逐一实现即可。