实现一个简单的二叉树容器,并且实现中序、先序、后续遍历

时间:2021-06-29 11:22:20

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