二叉樹的性質以及二叉查找樹的基本操作

1、基本概念

樹（Tree）是n（n≥0）個結點的有限集。在任意一棵非空樹中：（1）有且僅有一個特定的被稱為根（Root）的結點；（2）當n>1時，其余結點可分為m（m>0）個互不相交的有限集T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。

度：結點擁有的子樹數稱為結點的度（Degree）。度為0的結點稱為葉子（Leaf）或終端結點。度不為0的結點稱為非終端結點或分支結點。樹的度是樹內各結點的度的最大值。

孩子及雙親：結點的子樹的根稱為該結點的孩子（Child），相應地，該結點稱為孩子的雙親（Parent）。

層次“結點的層次（Level）是從根結點開始計算起，根為第一層，根的孩子為第二層，依次類推。樹中結點的最大層次稱為樹的深度（Depth）或高度。

如果將樹中結點的各子樹看成從左至右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。

2、二叉樹的基本性質：

二叉樹（Binary Tree）的特點是每個結點至多具有兩棵子樹（即在二叉樹中不存在度大于2的結點），并且子樹之間有左右之分。

二叉樹的性質：

（1）、在二叉樹的第i層上至多有2i-1個結點（i≥1）。

（2）、深度為k的二叉樹至多有2k-1個結點（k≥1）。

（3）、對任何一棵二叉樹，如果其葉子結點數為n0，度為2的結點數為n2，則n0=n2+1。

一棵深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹。

可以對滿二叉樹的結點進行連續編號，約定編號從根結點起，自上而下，自左至右，則由此可引出完全二叉樹的定義。深度為k且有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱之為完全二叉樹。

（4）、具有n個結點的完全二叉樹的深度為不大于log2n的最大整數加1。

    （5）、如果對一棵有n個結點的完全二叉樹的結點按層序編號（從第1層到最后一層，每層從左到右），則對任一結點i（1≤i≤n）,有

    a、如果i=1,則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是結點x（其中x是不大于i/2的最大整數）。

    b、如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點2i。

    c、如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1。

3、二叉查找樹基本操作
查找：
 在二叉查找樹中查找x的過程如下：
1、若二叉樹是空樹，則查找失敗。
2、若x等于根結點的數據，則查找成功，否則。
3、若x小于根結點的數據，則遞歸查找其左子樹，否則。
4、遞歸查找其右子樹。

/**
     * 二叉查找樹的查找
     * @param node
     * @param x
     */  
    public TreeNode Find(TreeNode node,int x){  
        if(node == null)  
            return null;  
        if(x<node.val)  
            Find(node.left);  
        else if(x>node.val)  
            Find(node.right);  
        else if(x == node.val)  
            return node;  
    }  
    /**
     * 查找最小值(遞歸實現)
     * 一直查找左子樹，最后一個節點即為最小值
     * @param node
     */  
    public TreeNode FindMin(TreeNode node){  
        if(node == null)  
            return null;  
        else if(node.left == null)  
            return node;  
        else {  
            return FindMin(node.left);  
        }  
    }  
    /**
     * 查找最大值（循環實現）
     * 一直查找右子樹
     * @param node
     */  
    public TreeNode FindMax(TreeNode node){  
        if(node != null)  
            while(node.right != null)  
                node = node.right;  
        return node;      
    } 
插入：
二叉樹查找樹b插入操作x的過程如下：
1、若b是空樹，則直接將插入的結點作為根結點插入。
2、x等于b的根結點的數據的值，則直接返回，否則。
3、若x小于b的根結點的數據的值，則將x要插入的結點的位置改變為b的左子樹，否則。
4、將x要出入的結點的位置改變為b的右子樹。

/**
     * 添加
     * @param x
     * @param root
     * @return
     */  
    public TreeNode Insert(int x,TreeNode root){  
        if(root == null){ //找到要插入的位置，新建一個節點  
            TreeNode node = new TreeNode(x);  
            node.left = null;  
            node.right = null;  
        }  
        else if(x<root.val) //如果插入值小于當前值，則應插入左子樹  
            root.left = Insert(x, root.left);  
        else if(x>root.val) //...  
            root.right = Insert(x, root.right);  
        return root;  
          
    } 
刪除：
對于二叉查找樹的刪除操作（這里根據值刪除，而非結點）分三種情況：
不過在此之前，我們應該確保根據給定的值找到了要刪除的結點，如若沒找到該結點
不會執行刪除操作！
下面三種情況假設已經找到了要刪除的結點。
1、如果結點為葉子結點（沒有左、右子樹），此時刪除該結點不會?；瘶涞慕Y構
直接刪除即可，并修改其父結點指向它的引用為null.如下圖:

2、如果其結點只包含左子樹，或者右子樹的話，此時直接刪除該結點，并將其左子樹
或者右子樹設置為其父結點的左子樹或者右子樹即可，此操作不會破壞樹結構。

3、 當結點的左右子樹都不空的時候，一般的刪除策略是用其右子樹的最小數據
（容易找到）代替要刪除的結點數據并遞歸刪除該結點（此時為null），因為
右子樹的最小結點不可能有左孩子，所以第二次刪除較為容易。
z的左子樹和右子樹均不空。找到z的后繼y，因為y一定沒有左子樹，所以可以刪除y，
并讓y的父親節點成為y的右子樹的父親節點，并用y的值代替z的值.如圖：