BST的定义

在二叉查找树中:

  • 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 任意节点的左、右子树也分别为二叉查找树。
  • 没有键值相等的节点。

image.png
动画效果请参考 BST。
著作权归https://pdai.tech所有。 链接：https://www.pdai.tech/md/algorithm/alg-basic-tree-search.html

BST的实现

节点

BSTree是二叉树，它保护了二叉树的根节点mRoot；mRoot是BSTNode类型，而BSTNode是二叉查找树的节点，它是BSTree的内部类。BSTNode包含二叉查找树的几个基本信息:

  • key — 它是关键字，是用来对二叉查找树的节点进行排序的。
  • left — 它指向当前节点的左孩子。
  • right — 它指向当前节点的右孩子。

  • parent — 它指向当前节点的父结点。 ```java public class BSTree> {

    private BSTNode mRoot; // 根结点

    public class BSTNode> {

    1.   T key;                // 关键字(键值)
    2.   BSTNode<T> left;      // 左孩子
    3.   BSTNode<T> right;     // 右孩子
    4.   BSTNode<T> parent;    // 父结点
    6.   public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
    7.       this.key = key;
    8.       this.parent = parent;
    9.       this.left = left;
    10.       this.right = right;
    11.   }

    }

    …… }

  1. <a name="IFyf9"></a>
  2. ### 遍历
  3. 这里讲解前序遍历、中序遍历、后序遍历3种方式。
  4. <a name="iVqHq"></a>
  5. #### 前序遍历
  6. 若二叉树非空，则执行以下操作:
  8. - 访问根结点；
  9. - 先序遍历左子树；
  10. - 先序遍历右子树。
  11. ```java
  12. private void preOrder(BSTNode<T> tree) {
  13.     if(tree != null) {
  14.         System.out.print(tree.key+" ");
  15.         preOrder(tree.left);
  16.         preOrder(tree.right);
  17.     }
  18. }
  20. public void preOrder() {
  21.     preOrder(mRoot);
  22. }

中序遍历

若二叉树非空，则执行以下操作:

  • 中序遍历左子树；
  • 访问根结点；
  • 中序遍历右子树。 ```java private void inOrder(BSTNode tree) { if(tree != null) {
    1.   inOrder(tree.left);
    2.   System.out.print(tree.key+" ");
    3.   inOrder(tree.right);
    } }

public void inOrder() { inOrder(mRoot); }

  1. <a name="b2AWu"></a>
  2. #### 后序遍历
  3. 若二叉树非空，则执行以下操作:
  5. - 后序遍历左子树；
  6. - 后序遍历右子树；
  7. - 访问根结点。
  8. ```java
  9. private void postOrder(BSTNode<T> tree) {
  10.     if(tree != null)
  11.     {
  12.         postOrder(tree.left);
  13.         postOrder(tree.right);
  14.         System.out.print(tree.key+" ");
  15.     }
  16. }
  18. public void postOrder() {
  19.     postOrder(mRoot);
  20. }

看看下面这颗树的各种遍历方式:
image.png
对于上面的二叉树而言，

  • 前序遍历结果: 8 3 1 6 4 7 10 14 13
  • 中序遍历结果: 1 3 4 6 7 8 10 13 14

  • 后序遍历结果: 1 4 7 6 3 13 14 10 8

    查找

  • 递归版本的代码 ```java /*

    • (递归实现)查找”二叉树x”中键值为key的节点 */ private BSTNode search(BSTNode x, T key) { if (x==null)

      1. return x;

      int cmp = key.compareTo(x.key); if (cmp < 0)

      1. return search(x.left, key);

      else if (cmp > 0)

      1. return search(x.right, key);

      else

      1. return x;

      }

public BSTNode search(T key) { return search(mRoot, key); }

  2. - 非递归版本的代码
  3. ```java
  4. /*
  5.  * (非递归实现)查找"二叉树x"中键值为key的节点
  6.  */
  7. private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
  8.     while (x!=null) {
  9.         int cmp = key.compareTo(x.key);
  11.         if (cmp < 0) 
  12.             x = x.left;
  13.         else if (cmp > 0) 
  14.             x = x.right;
  15.         else
  16.             return x;
  17.     }
  19.     return x;
  20. }
  22. public BSTNode<T> iterativeSearch(T key) {
  23.     return iterativeSearch(mRoot, key);
  24. }


最大值和最小值

image.png

  • 查找最大结点 ```java /*

    • 查找最大结点: 返回tree为根结点的二叉树的最大结点。 */ private BSTNode maximum(BSTNode tree) { if (tree == null)

      1. return null;

      while(tree.right != null)

      1. tree = tree.right;

      return tree; }

public T maximum() { BSTNode p = maximum(mRoot); if (p != null) return p.key;

  1. return null;

}

  2. - 查找最小结点
  3. ```java
  4. /* 
  5.  * 查找最小结点: 返回tree为根结点的二叉树的最小结点。
  6.  */
  7. private BSTNode<T> minimum(BSTNode<T> tree) {
  8.     if (tree == null)
  9.         return null;
  11.     while(tree.left != null)
  12.         tree = tree.left;
  13.     return tree;
  14. }
  16. public T minimum() {
  17.     BSTNode<T> p = minimum(mRoot);
  18.     if (p != null)
  19.         return p.key;
  21.     return null;
  22. }

前驱和后继

节点的前驱: 是该节点的左子树中的最大节点。 节点的后继: 是该节点的右子树中的最小节点。

  • 查找前驱节点 ```java /*

    • 找结点(x)的前驱结点。即，查找”二叉树中数据值小于该结点”的”最大结点”。 */ public BSTNode predecessor(BSTNode x) { // 如果x存在左孩子，则”x的前驱结点”为 “以其左孩子为根的子树的最大结点”。 if (x.left != null)

      1. return maximum(x.left);

      // 如果x没有左孩子。则x有以下两种可能: // (01) x是”一个右孩子”，则”x的前驱结点”为 “它的父结点”。 // (01) x是”一个左孩子”，则查找”x的最低的父结点，并且该父结点要具有右孩子”，找到的这个”最低的父结点”就是”x的前驱结点”。 BSTNode y = x.parent; while ((y!=null) && (x==y.left)) {

      1. x = y;
      2. y = y.parent;

      }

      return y; }

  1. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22016332/1652717955501-45791730-9fde-4807-9f9c-0a08d01f228c.png#clientId=u6f6655c3-1b96-4&from=paste&height=439&id=uc94896fa&originHeight=549&originWidth=680&originalType=binary&ratio=1&rotation=0&showTitle=false&size=154003&status=done&style=none&taskId=uf5440235-3323-49ba-971d-7538e50aa93&title=&width=544)
  3. - 查找后继节点
  4. ```java
  5. /* 
  6.  * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
  7.  */
  8. public BSTNode<T> successor(BSTNode<T> x) {
  9.     // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
  10.     if (x.right != null)
  11.         return minimum(x.right);
  13.     // 如果x没有右孩子。则x有以下两种可能: 
  14.     // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
  15.     // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
  16.     BSTNode<T> y = x.parent;
  17.     while ((y!=null) && (x==y.right)) {
  18.         x = y;
  19.         y = y.parent;
  20.     }
  22.     return y;
  23. }

image.png

插入

image.png

  1. /* 
  2.  * 将结点插入到二叉树中
  3.  *
  4.  * 参数说明: 
  5.  *     tree 二叉树的
  6.  *     z 插入的结点
  7.  */
  8. private void insert(BSTree<T> bst, BSTNode<T> z) {
  9.     int cmp;
  10.     BSTNode<T> y = null;
  11.     BSTNode<T> x = bst.mRoot;
  13.     // 查找z的插入位置
  14.     while (x != null) {
  15.         y = x;
  16.         cmp = z.key.compareTo(x.key);
  17.         if (cmp < 0)
  18.             x = x.left;
  19.         else
  20.             x = x.right;
  21.     }
  23.     z.parent = y;
  24.     if (y==null)
  25.         bst.mRoot = z;
  26.     else {
  27.         cmp = z.key.compareTo(y.key);
  28.         if (cmp < 0)
  29.             y.left = z;
  30.         else
  31.             y.right = z;
  32.     }
  33. }
  35. /* 
  36.  * 新建结点(key)，并将其插入到二叉树中
  37.  *
  38.  * 参数说明: 
  39.  *     tree 二叉树的根结点
  40.  *     key 插入结点的键值
  41.  */
  42. public void insert(T key) {
  43.     BSTNode<T> z=new BSTNode<T>(key,null,null,null);
  45.     // 如果新建结点失败，则返回。
  46.     if (z != null)
  47.         insert(this, z);
  48. }

删除

image.png
image.png

  1. /* 
  2.  * 删除结点(z)，并返回被删除的结点
  3.  *
  4.  * 参数说明: 
  5.  *     bst 二叉树
  6.  *     z 删除的结点
  7.  */
  8. private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
  9.     BSTNode<T> x=null;
  10.     BSTNode<T> y=null;
  12.     if ((z.left == null) || (z.right == null) )
  13.         y = z;
  14.     else
  15.         y = successor(z);
  17.     if (y.left != null)
  18.         x = y.left;
  19.     else
  20.         x = y.right;
  22.     if (x != null)
  23.         x.parent = y.parent;
  25.     if (y.parent == null)
  26.         bst.mRoot = x;
  27.     else if (y == y.parent.left)
  28.         y.parent.left = x;
  29.     else
  30.         y.parent.right = x;
  32.     if (y != z) 
  33.         z.key = y.key;
  35.     return y;
  36. }
  38. /* 
  39.  * 删除结点(z)，并返回被删除的结点
  40.  *
  41.  * 参数说明: 
  42.  *     tree 二叉树的根结点
  43.  *     z 删除的结点
  44.  */
  45. public void remove(T key) {
  46.     BSTNode<T> z, node; 
  48.     if ((z = search(mRoot, key)) != null)
  49.         if ( (node = remove(this, z)) != null)
  50.             node = null;
  51. }

打印

  1. /*
  2.  * 打印"二叉查找树"
  3.  *
  4.  * key        -- 节点的键值 
  5.  * direction  --  0，表示该节点是根节点;
  6.  *               -1，表示该节点是它的父结点的左孩子;
  7.  *                1，表示该节点是它的父结点的右孩子。
  8.  */
  9. private void print(BSTNode<T> tree, T key, int direction) {
  11.     if(tree != null) {
  13.         if(direction==0)    // tree是根节点
  14.             System.out.printf("%2d is root\n", tree.key);
  15.         else                // tree是分支节点
  16.             System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
  18.         print(tree.left, tree.key, -1);
  19.         print(tree.right,tree.key,  1);
  20.     }
  21. }
  23. public void print() {
  24.     if (mRoot != null)
  25.         print(mRoot, mRoot.key, 0);
  26. }

销毁

  1. /*
  2.  * 销毁二叉树
  3.  */
  4. private void destroy(BSTNode<T> tree) {
  5.     if (tree==null)
  6.         return ;
  8.     if (tree.left != null)
  9.         destroy(tree.left);
  10.     if (tree.right != null)
  11.         destroy(tree.right);
  13.     tree=null;
  14. }
  16. public void clear() {
  17.     destroy(mRoot);
  18.     mRoot = null;
  19. }

测试程序

下面对测试程序的流程进行分析！

  • 新建”二叉查找树”root。
  • 向二叉查找树中依次插入1,5,4,3,2,6 。如下图所示:

image.png

  • 遍历和查找

插入1,5,4,3,2,6之后，得到的二叉查找树如下:
image.png

  1. 前序遍历结果: 1 5 4 3 2 6 
  2. 中序遍历结果: 1 2 3 4 5 6 
  3. 后序遍历结果: 2 3 4 6 5 1 
  4. 最小值是1，而最大值是6。
  • 删除节点4。如下图所示:

image.png

  • 重新遍历该二叉查找树。

中序遍历结果: 1 2 4 5 6

代码和测试代码

代码实现

  1. /**
  2.  * Java 语言: 二叉查找树
  3.  *
  4.  * @author skywang
  5.  * @date 2013/11/07
  6.  */
  8. public class BSTree<T extends Comparable<T>> {
  10.     private BSTNode<T> mRoot;    // 根结点
  12.     public class BSTNode<T extends Comparable<T>> {
  13.         T key;                // 关键字(键值)
  14.         BSTNode<T> left;    // 左孩子
  15.         BSTNode<T> right;    // 右孩子
  16.         BSTNode<T> parent;    // 父结点
  18.         public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
  19.             this.key = key;
  20.             this.parent = parent;
  21.             this.left = left;
  22.             this.right = right;
  23.         }
  25.         public T getKey() {
  26.             return key;
  27.         }
  29.         public String toString() {
  30.             return "key:"+key;
  31.         }
  32.     }
  34.     public BSTree() {
  35.         mRoot=null;
  36.     }
  38.     /*
  39.      * 前序遍历"二叉树"
  40.      */
  41.     private void preOrder(BSTNode<T> tree) {
  42.         if(tree != null) {
  43.             System.out.print(tree.key+" ");
  44.             preOrder(tree.left);
  45.             preOrder(tree.right);
  46.         }
  47.     }
  49.     public void preOrder() {
  50.         preOrder(mRoot);
  51.     }
  53.     /*
  54.      * 中序遍历"二叉树"
  55.      */
  56.     private void inOrder(BSTNode<T> tree) {
  57.         if(tree != null) {
  58.             inOrder(tree.left);
  59.             System.out.print(tree.key+" ");
  60.             inOrder(tree.right);
  61.         }
  62.     }
  64.     public void inOrder() {
  65.         inOrder(mRoot);
  66.     }
  69.     /*
  70.      * 后序遍历"二叉树"
  71.      */
  72.     private void postOrder(BSTNode<T> tree) {
  73.         if(tree != null)
  74.         {
  75.             postOrder(tree.left);
  76.             postOrder(tree.right);
  77.             System.out.print(tree.key+" ");
  78.         }
  79.     }
  81.     public void postOrder() {
  82.         postOrder(mRoot);
  83.     }
  86.     /*
  87.      * (递归实现)查找"二叉树x"中键值为key的节点
  88.      */
  89.     private BSTNode<T> search(BSTNode<T> x, T key) {
  90.         if (x==null)
  91.             return x;
  93.         int cmp = key.compareTo(x.key);
  94.         if (cmp < 0)
  95.             return search(x.left, key);
  96.         else if (cmp > 0)
  97.             return search(x.right, key);
  98.         else
  99.             return x;
  100.     }
  102.     public BSTNode<T> search(T key) {
  103.         return search(mRoot, key);
  104.     }
  106.     /*
  107.      * (非递归实现)查找"二叉树x"中键值为key的节点
  108.      */
  109.     private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
  110.         while (x!=null) {
  111.             int cmp = key.compareTo(x.key);
  113.             if (cmp < 0) 
  114.                 x = x.left;
  115.             else if (cmp > 0) 
  116.                 x = x.right;
  117.             else
  118.                 return x;
  119.         }
  121.         return x;
  122.     }
  124.     public BSTNode<T> iterativeSearch(T key) {
  125.         return iterativeSearch(mRoot, key);
  126.     }
  128.     /* 
  129.      * 查找最小结点: 返回tree为根结点的二叉树的最小结点。
  130.      */
  131.     private BSTNode<T> minimum(BSTNode<T> tree) {
  132.         if (tree == null)
  133.             return null;
  135.         while(tree.left != null)
  136.             tree = tree.left;
  137.         return tree;
  138.     }
  140.     public T minimum() {
  141.         BSTNode<T> p = minimum(mRoot);
  142.         if (p != null)
  143.             return p.key;
  145.         return null;
  146.     }
  148.     /* 
  149.      * 查找最大结点: 返回tree为根结点的二叉树的最大结点。
  150.      */
  151.     private BSTNode<T> maximum(BSTNode<T> tree) {
  152.         if (tree == null)
  153.             return null;
  155.         while(tree.right != null)
  156.             tree = tree.right;
  157.         return tree;
  158.     }
  160.     public T maximum() {
  161.         BSTNode<T> p = maximum(mRoot);
  162.         if (p != null)
  163.             return p.key;
  165.         return null;
  166.     }
  168.     /* 
  169.      * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
  170.      */
  171.     public BSTNode<T> successor(BSTNode<T> x) {
  172.         // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
  173.         if (x.right != null)
  174.             return minimum(x.right);
  176.         // 如果x没有右孩子。则x有以下两种可能: 
  177.         // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
  178.         // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
  179.         BSTNode<T> y = x.parent;
  180.         while ((y!=null) && (x==y.right)) {
  181.             x = y;
  182.             y = y.parent;
  183.         }
  185.         return y;
  186.     }
  188.     /* 
  189.      * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
  190.      */
  191.     public BSTNode<T> predecessor(BSTNode<T> x) {
  192.         // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
  193.         if (x.left != null)
  194.             return maximum(x.left);
  196.         // 如果x没有左孩子。则x有以下两种可能: 
  197.         // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
  198.         // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
  199.         BSTNode<T> y = x.parent;
  200.         while ((y!=null) && (x==y.left)) {
  201.             x = y;
  202.             y = y.parent;
  203.         }
  205.         return y;
  206.     }
  208.     /* 
  209.      * 将结点插入到二叉树中
  210.      *
  211.      * 参数说明: 
  212.      *     tree 二叉树的
  213.      *     z 插入的结点
  214.      */
  215.     private void insert(BSTree<T> bst, BSTNode<T> z) {
  216.         int cmp;
  217.         BSTNode<T> y = null;
  218.         BSTNode<T> x = bst.mRoot;
  220.         // 查找z的插入位置
  221.         while (x != null) {
  222.             y = x;
  223.             cmp = z.key.compareTo(x.key);
  224.             if (cmp < 0)
  225.                 x = x.left;
  226.             else
  227.                 x = x.right;
  228.         }
  230.         z.parent = y;
  231.         if (y==null)
  232.             bst.mRoot = z;
  233.         else {
  234.             cmp = z.key.compareTo(y.key);
  235.             if (cmp < 0)
  236.                 y.left = z;
  237.             else
  238.                 y.right = z;
  239.         }
  240.     }
  242.     /* 
  243.      * 新建结点(key)，并将其插入到二叉树中
  244.      *
  245.      * 参数说明: 
  246.      *     tree 二叉树的根结点
  247.      *     key 插入结点的键值
  248.      */
  249.     public void insert(T key) {
  250.         BSTNode<T> z=new BSTNode<T>(key,null,null,null);
  252.         // 如果新建结点失败，则返回。
  253.         if (z != null)
  254.             insert(this, z);
  255.     }
  257.     /* 
  258.      * 删除结点(z)，并返回被删除的结点
  259.      *
  260.      * 参数说明: 
  261.      *     bst 二叉树
  262.      *     z 删除的结点
  263.      */
  264.     private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
  265.         BSTNode<T> x=null;
  266.         BSTNode<T> y=null;
  268.         if ((z.left == null) || (z.right == null) )
  269.             y = z;
  270.         else
  271.             y = successor(z);
  273.         if (y.left != null)
  274.             x = y.left;
  275.         else
  276.             x = y.right;
  278.         if (x != null)
  279.             x.parent = y.parent;
  281.         if (y.parent == null)
  282.             bst.mRoot = x;
  283.         else if (y == y.parent.left)
  284.             y.parent.left = x;
  285.         else
  286.             y.parent.right = x;
  288.         if (y != z) 
  289.             z.key = y.key;
  291.         return y;
  292.     }
  294.     /* 
  295.      * 删除结点(z)，并返回被删除的结点
  296.      *
  297.      * 参数说明: 
  298.      *     tree 二叉树的根结点
  299.      *     z 删除的结点
  300.      */
  301.     public void remove(T key) {
  302.         BSTNode<T> z, node; 
  304.         if ((z = search(mRoot, key)) != null)
  305.             if ( (node = remove(this, z)) != null)
  306.                 node = null;
  307.     }
  309.     /*
  310.      * 销毁二叉树
  311.      */
  312.     private void destroy(BSTNode<T> tree) {
  313.         if (tree==null)
  314.             return ;
  316.         if (tree.left != null)
  317.             destroy(tree.left);
  318.         if (tree.right != null)
  319.             destroy(tree.right);
  321.         tree=null;
  322.     }
  324.     public void clear() {
  325.         destroy(mRoot);
  326.         mRoot = null;
  327.     }
  329.     /*
  330.      * 打印"二叉查找树"
  331.      *
  332.      * key        -- 节点的键值 
  333.      * direction  --  0，表示该节点是根节点;
  334.      *               -1，表示该节点是它的父结点的左孩子;
  335.      *                1，表示该节点是它的父结点的右孩子。
  336.      */
  337.     private void print(BSTNode<T> tree, T key, int direction) {
  339.         if(tree != null) {
  341.             if(direction==0)    // tree是根节点
  342.                 System.out.printf("%2d is root\n", tree.key);
  343.             else                // tree是分支节点
  344.                 System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
  346.             print(tree.left, tree.key, -1);
  347.             print(tree.right,tree.key,  1);
  348.         }
  349.     }
  351.     public void print() {
  352.         if (mRoot != null)
  353.             print(mRoot, mRoot.key, 0);
  354.     }
  355. }

测试代码

  1. /**
  2.  * Java 语言: 二叉查找树
  3.  *
  4.  * @author skywang
  5.  * @date 2013/11/07
  6.  */
  7. public class BSTreeTest {
  9.     private static final int arr[] = {1,5,4,3,2,6};
  11.     public static void main(String[] args) {
  12.         int i, ilen;
  13.         BSTree<Integer> tree=new BSTree<Integer>();
  15.         System.out.print("== 依次添加: ");
  16.         ilen = arr.length;
  17.         for(i=0; i<ilen; i++) {
  18.             System.out.print(arr[i]+" ");
  19.             tree.insert(arr[i]);
  20.         }
  22.         System.out.print("\n== 前序遍历: ");
  23.         tree.preOrder();
  25.         System.out.print("\n== 中序遍历: ");
  26.         tree.inOrder();
  28.         System.out.print("\n== 后序遍历: ");
  29.         tree.postOrder();
  30.         System.out.println();
  32.         System.out.println("== 最小值: "+ tree.minimum());
  33.         System.out.println("== 最大值: "+ tree.maximum());
  34.         System.out.println("== 树的详细信息: ");
  35.         tree.print();
  37.         System.out.print("\n== 删除根节点: "+ arr[3]);
  38.         tree.remove(arr[3]);
  40.         System.out.print("\n== 中序遍历: ");
  41.         tree.inOrder();
  42.         System.out.println();
  44.         // 销毁二叉树
  45.         tree.clear();
  46.     }
  47. }

测试结果

  1. == 依次添加: 1 5 4 3 2 6 
  2. == 前序遍历: 1 5 4 3 2 6 
  3. == 中序遍历: 1 2 3 4 5 6 
  4. == 后序遍历: 2 3 4 6 5 1 
  5. == 最小值: 1
  6. == 最大值: 6
  7. == 树的详细信息: 
  8. is root
  9. is  1's  right child
  10. is  5's   left child
  11. is  4's   left child
  12. is  3's   left child
  13. is  5's  right child
  15. == 删除根节点: 3
  16. == 中序遍历: 1 2 4 5 6