二叉樹

   
二叉樹的定義：
        二叉樹是n（n>=0）個有限結點構成的集合。n=0的樹
   稱為空二叉樹；n>0的二叉樹由一個根結點和兩個互不相交
   的、分別稱作左子樹和右子樹的子二叉樹構成。

一.數據集合
       二叉樹的數據集合即二叉樹的結點集合，每個結點由數
   據元素和構造數據元素之間關系的指針組成。 
二.操作集合
   (1)初始化Initiate(T)：初始化二叉樹T。
   (2)左插入結點InsertLeftNode(curr，x)：若當前結點curr
      非空，在curr的左子樹插入元素值為x的新結點，原curr
      所指結點的左子樹成為新插入結點的左子樹，若插入成功
      返回新插入結點的指針，否則返回空指針。
   (3)右插入結點InsertRightNode(curr，x)：若當前結點curr
      非空，在curr的右子樹插入元素值為x的新結點，原curr
      所指結點的右子樹成為新插入結點的右子樹，若插入成功
      返回新插入結點的指針，否則返回空指針。
   (4)左刪除子樹DeleteLeftTree(curr)：若當前結點curr非空，
      刪除curr所指結點的左子樹，若刪除成功返回刪除結點的
      雙親結點指針，否則返回空指針。
   (5)右刪除子樹DeleteRightTree(curr)：若當前結點curr非
      空，刪除curr所指結點的右子樹，若刪除成功返回刪除結
      點的雙親結點指針，否則返回空指針。
   (6)遍歷二叉樹Traverse(T，Visit())：若二叉樹T存在則按
      某種次序訪問二叉樹T的每個結點，且每個結點只訪問一
      次，訪問結點時調用函數Visit()。二叉樹的遍歷次序主
      要有先序遍歷次序、中序遍歷次序、后序遍歷次序和層序
      遍歷次序四種。
   (7)撤消二叉樹Destroy(T)：釋放二叉樹T的所有動態存儲空間。
   實際上，撒消二叉樹操作是遍歷二叉樹操作的一個具體應用。
   上面給出的操作集合只是其主要部分，實際使用的二叉樹操作
集合中還包括如左刪除結點、右刪除結點等操作，為簡潔起見，
這里未做介紹。

三.二叉樹的性質
   性質1  若規定根結點的層次為0，則一棵非空二叉樹的第i層
          上最多有2^i(i>=0)個結點。 
          
   性質2  若規定空樹的深度為-1，則深度為k的二叉樹的最大結
          點數是2^(k+1)-1(k≥-1)個。
 
   性質3  具有n個結點的完全二叉樹的深度k為不超過lb(n+1)-1
          的最大整數。
          
   性質4  對于具有n個結點的完全二叉樹，如果按照從上至下和
          從左至右的順序對所有結點從0開始順序編號，則對于
          序號為i的結點，有：
          (1)如果i>O，則序號為i的結點的雙親結點的序號為
             (i-1)／2(“／”表示整除)，如果i=0，則序號為i
             的結點為根結點，無雙親結點。
          (2)如果2i+l<n，則序號為i的結點的左孩子結點的序
             號為2i+1;如果2i+1≥n，則序號為i的結點無左孩子。
          (3)如果2i+2<n，則序號為i的結點的右孩子結點的序號
             為2i+2；如果2i+2≥n,則序號為i的結點無右孩子。
   
          性質4告訴我們，如果我們把完全二叉樹按照從上至下
      和從左至右的順序對所有結點順序編號，則可以用一維數
      組存儲完全二叉樹。此時完全二叉樹中任意結點的雙親結點
      序號、左孩子結點序號和右孩子結點序號均可以根據該結點
      的序號計算得出。
  
四.二叉樹的設計和實現
    二叉樹的存儲結構主要有三種：順序存儲結構、鏈式存儲結構
                                和仿真指針存儲結構。
    1.二叉樹的順序存儲結構
          由性質4可知，對于完全二叉樹中任意結點i的雙親結點
      序號、左孩子結點序號和右孩子結點序號都可由公式計算得
      到。因此完全二叉樹的結點可按從上至下和從左至右的次序
      存儲在一維數組中，其結點之間的關系可由公式計算得到，
      這就是二叉樹的順序存儲結構。
          但是，對于一般的非完全二叉樹，如果仍按從上至下和
      從左至右的次序存儲在一維數組中，則數組下標之間的關系
      不能反映二叉樹中結點之間的邏輯關系。此時我們可首先在
      非完全二叉樹中增添一些并不存在的空結點使之變成完全二
      叉樹的形態，然后再用順序存儲結構存儲。
          顯然，對于完全二叉樹，用順序存儲結構存儲時既能節
      省存儲空間，又能使二叉樹的操作實現簡單。但對于非完全
      二叉樹，如果它接近于完全二叉樹，即需要增加的空結點數
      目不多時，可采用順序存儲結構存儲，但如果需要增加的空
      結點數太多時就不宜采用順序存儲結構存儲。最壞的情況是
      右單支樹，若右單支樹采用順序存儲結構方法存儲，則一棵
      深度為k的右單支樹只有k個結點，卻需分配2^k-1個存儲單元。
      另外，使用中還需要識別數據域為空的情況。
    2.二叉樹的鏈式存儲結構
          二叉樹的鏈式存儲結構是用指針建立二叉樹中結點之間
      的關系的。二叉樹最常用的鏈式存儲結構是二叉鏈。二叉鏈
      存儲結構的每個結點包含三個域，分別是數據域data、左孩
      子指針leftChild和右孩子指針域rightChild。二叉鏈存儲
      結構中每個結點的圖示結構為：
                   leftChild  |  data  |  rightChild
    3.二叉樹的仿真指針
          在使用數組存儲數據元素時，我們可在存儲數據元素的
      數組中增加一個或幾個數組下標域，這些數組下標域的值表
      示了該數組中某個數據元素的下標。由于在數組中增加的數
      組下標域仿真了鏈式存儲結構中的指針域，所以這種存儲結
      構也稱作仿真指針。
          二叉樹的仿真指針存儲結構是用數組存儲二叉樹中的結
      點，數組中每個結點除數據域外，在增加仿真指針域用于仿
      真常規指針建立二叉樹結點之間的關系。