实现一个简单的二叉树容器，并且实现中序、先序、后续遍历
实现一个简单的二叉树容器，并且实现中序、先序、后续遍历
二叉树定义：
是一种树形结构，他的特点是每个结点最多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的性质：
- 二叉树的第i层上最多有 2^(i-1) 个结点，（i>=1）；
- 深度为k的二叉树最多有 2^k – 1 个结点，（k >=1）；
- 对任何一颗二叉树，如果其终端结点数为N0，度为2的节点数为N2，那有N0 = N2 + 1;
介绍下满二叉树和完全二叉树：
满二叉树：深度为k且有2^k -1个结点的二叉树成为满二叉树。每一层上的结点的度都是2。
完全二叉树：深度为k的，有n个结点的二叉树，每一个结点都和深度为k的满二叉树中编号从1~n的结点一一对应，这样的二叉树称为完全二叉树。
如下图是满二叉树：
下面是完全二叉树，而上面的满二叉树结点序号一致：
上面介绍了些概念的东西，都是在大学的时候学习的，只可惜啊没认真学过，感觉浪费了大好青春。
在用代码实现二叉树时，我想可不可以封装成像List或者Map这类容器呢？所以在实现时我定义了内部类Node，用于表示每个结点，Node中分别定义了leftNode、rightNode表示结点的左右结点，还有个int类型的value，表示结点存储的内容。
定义的二叉树容器类中，还定义了add(int[] array)，用于将数组int[]转化成二叉树，使用Node firstNode记录二叉树的根节点。
在对二叉树进行中、先、后序的遍历。
代码如下：
1 package binarytree; 2 3 public class BinTree { 4 5 // 定义一个内部类，实现节点。 6 class Node{ 7 private Node leftNode; 8 private Node rightNode; 9 private int value; 10 11 public Node(){} 12 public Node(int value){ 13 this.value = value; 14 } 15 public Node getLeftNode() { 16 return leftNode; 17 } 18 19 public void setLeftNode(Node leftNode) { 20 this.leftNode = leftNode; 21 } 22 23 public Node getRightNode() { 24 return rightNode; 25 } 26 27 public void setRightNode(Node rightNode) { 28 this.rightNode = rightNode; 29 } 30 31 public int getValue() { 32 return value; 33 } 34 35 public void setValue(int value) { 36 this.value = value; 37 } 38 } 39 40 // 记录二叉树的根结点 41 private Node firstNode; 42 43 // 返回二叉树根结点 44 public Node getFirstNode() { 45 return firstNode; 46 } 47 48 // 根据int数组创建二叉树，构造函数 49 public BinTree(int[] values){ 50 Node node = null; 51 for (int i = 0; i < values.length; i++){ 52 if (i == 0){ 53 node = new Node(values[i]); 54 }else{ 55 add(node, values[i]); 56 } 57 } 58 firstNode = node; 59 } 60 61 // 向二叉树中添加元素 62 public void add(Node node, int value){ 63 if(node == null){ 64 return; 65 } 66 // 小于第一个节点的值，放入左边 67 if(value <= node.getValue()){ 68 if(node.getLeftNode() == null){ 69 Node tempNode = new Node(value); 70 node.setLeftNode(tempNode); 71 }else{ 72 node = node.getLeftNode(); 73 add(node, value); 74 } 75 } 76 // 值大于当前结点的值，放在右子树 77 if (value > node.getValue()){ 78 if(node.getRightNode() == null){ 79 Node tempNode = new Node(value); 80 node.setRightNode(tempNode); 81 }else{ 82 node = node.getRightNode(); 83 add(node, value); 84 } 85 } 86 } 87 // 中序遍历 88 public void zhongXu(Node node){ 89 if (node == null){ 90 return; 91 } 92 zhongXu(node.getLeftNode()); 93 System.out.print(node.getValue() + " "); 94 zhongXu(node.getRightNode()); 95 } 96 // 先序遍历 97 public void xianXu(Node node){ 98 if(node == null){ 99 return; 100 } 101 System.out.print(node.getValue() + " "); 102 xianXu(node.getLeftNode()); 103 xianXu(node.getRightNode()); 104 } 105 106 // 后序遍历 107 public void houXu(Node node){ 108 if (node == null){ 109 return; 110 } 111 houXu(node.getLeftNode()); 112 houXu(node.getRightNode()); 113 System.out.print(node.getValue() + " "); 114 } 115 }
下面进行测试，测试代码如下：
1 package binarytree; 2 3 public class BinaryTreeTest { 4 5 public static void main(String[] args){ 6 int[] values = new int[]{2, 1, 3};//中序：123 先序：213 后序：132 7 BinTree binTree = new BinTree(values); 8 binTree.zhongXu(binTree.getFirstNode()); 9 binTree.xianXu(binTree.getFirstNode()); 10 binTree.houXu(binTree.getFirstNode()); 11 12 } 13 }
运行结果：
总结：
二叉树的3中遍历方式，主要是针对根结点（或者说是父结点）来说，然后左边始终先于右边。
中序遍历即将根结点放在中间遍历：左结点 -> 根结点 -> 右结点
先序遍历即将根结点放在最先遍历：根结点 -> 左结点 -> 右结点
后序遍历即将根结点放在最后遍历：左结点 -> 右结点 -> 根结点
遍历代码，需要注意递归的停止条件是：if(node == null);
版权声明：本文为teiba原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。