樹的存儲結構

　　本節僅討論樹的三種常用表示法

雙親鏈表表示法
　　雙親鏈表表示法利用樹中每個結點的雙親唯一性在存儲結點信息的同時為每個結點附設一個指向其雙親的指針parent惟一地表示任何棵樹
（）雙親鏈表表示法的實現
　方法① 用動態鏈表實現
　方法② 用向量表示——更為方便

（）雙親鏈表向量表示的形式說明
  #define MaxTreeSize //向量空間的大小由用戶定義
  typedef char DataType //應由用戶定義
  typedef struct{
      DataType data//結點數據
      int parent //雙親指針指示結點的雙親在向量中的位置
    }PTreeNode
  typedef struct{
      PTreeNode nodes[MaxTreeSize];
      int n //結點總數
    }PTree
  PTree T //T是雙親鏈表
  注意
    　若Tnodes[i]parent=j則Tnodes[i]的雙親是Tnodes[j]

（）雙親鏈表表示實例
　【例】圖(a)的雙親鏈表表示如下面數組所示

 
　　分析
　　E和F所在結點的雙親域是它們的雙親結點在向量中的位置是即B是它們的雙親
　注意
　　① 根無雙親其parent域為
　　② 雙親鏈表表示法中指針parent向上鏈接適合求指定結點的雙親或祖先(包括根)求指定結點的孩子或其它後代時可能要遍歷整個數組

孩子鏈表表示法

（） 結點結構
　① 定長結點
　　即樹中每個結點均按樹的度k來設置指針
    　n個結點的樹一共有n*k個指針域而樹中只有n條邊故樹中的空指針數目為
         kn(n)=n(k)+（k越大浪費的空間越多）

　②不定長結點
　　即樹中每個結點按本結點的度來設置指針數並在結點中增設一個度數域degree指出該結點包含的指針數
　　各結點不等長雖然節省了空間但是給運算帶來不便

（）孩子鏈表表示法
　　孩子鏈表表示法是為樹中每個結點設置一個孩子鏈表並將這些結點及相應的孩子鏈表的頭指針存放在一個向量中
　①孩子鏈表表示法的類型說明
    //以下的DataType和MaxTreeSize由用戶定義
    typedef struct CNode{//子鏈表結點
        int child //孩子結點在向量中對應的序號
        struct CNode *next
      }CNode
    typedef struct{
        DataType data //存放樹中結點數據
        CNode *firstchild//孩子鏈表的頭指針
      }PTNode
    typedef struct{
        PTNode nodes[MaxTreeSize]
        Int nroot //n為結點總數root指出根在向量中的位置
      }CTree
    Ctree T //T為孩子鏈表表示
　注意
    當結點Tnodes[i]為葉子時其孩子鏈表為空即Tnodes[i]firstchild=NULL

　②孩子鏈表表示法實例
　【例】圖(a)所示樹的孩子鏈表表示T如下面(a)圖所示

　注意
　　① 孩子結點的數據域僅存放了它們在向量空間的序號
　　② 與雙親鏈表表示法相反孩子鏈表表示便於實現涉及孩子及其子孫的運算但不便於實現與雙親有關的運算
　　③ 將雙親鏈表表示法和孩子鏈表表示法結合起來可形成雙親孩子鏈表表示法
　【例】上面的(b)圖就是用雙親鏈表表示法來存儲圖(a)中的樹
         
孩子兄弟鏈表表示法
（）表示方法
　　在存儲結點信息的同時附加兩個分別指向該結點最左孩子和右鄰兄弟的指針域leftmostchild和rightsibling即可得樹的孩子兄弟鏈表表示

（）表示實例
　【例】圖．(a)中樹的孩子兄弟鏈表如下圖所示

 
　注意
　　這種存儲結構的最大優點是它和二叉樹的二叉鏈表表示完全一樣可利用二叉樹的算法來實現對樹的操作

 

From:http://tw.wingwit.com/Article/program/sjjg/201311/23211.html