二叉树定义:
是一种树形结构,他的特点是每个结点最多只有两颗子树(即二叉树中不存在度大于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);