數據結構整理(二) 樹

一、前言

　　項目源碼及其他聲明等參見數據結構（一）線性結構篇。

二、相關概念

　　樹作為一種應用廣泛的一對多非線性數據結構，不僅有數據間的指向關係，還有層級關係，示例見圖一。因樹的結構比較複雜，為了簡化操作及存儲，我們一般將樹轉換為二叉樹處理，因此本文主要討論二叉樹。

1. 二叉樹
   　　二叉樹是每個節點最多擁有兩個子節點的樹結構，若移除根節點則其餘節點會被分成兩個互不相交的子樹，分別稱為左子樹和右子樹。二叉樹是有序樹，左右子樹有嚴格的次序，若顛倒則成為一棵不一樣的二叉樹。
2. 滿二叉樹
   　　滿二叉樹，顧名思義除葉子節點外所有節點都擁有兩個孩子，且葉子節點在同一層的二叉樹，示例見圖二。
   
3. 完全二叉樹
   　　完全二叉樹，移除最後一層節點後是滿二叉樹，且最後一層的節點都連續集中在最左面，示例見圖三。

三、二叉樹存儲結構

1. 順序存儲
   　　根據完全二叉樹的特性，可以計算出任意節點n的雙親節點及左右孩子節點的序號，因此完全二叉樹的節點可以按照從上到下從左到右的順序依次存儲到一維數組中。非完全二叉樹存儲時應先將其改造為完全二叉樹，以空替代不存在的節點，比較浪費存儲空間，存儲示意圖見圖四。
   
2. 鏈式存儲
   　　樹結構鏈式存儲類似線性結構鏈式存儲，先定義包含數據域和引用域的節點(Node)，然後通過引用域存儲節點之間的關係。根據二叉樹的結構來看，節點Node至少包含數據域(Data)，引用域(左孩子LChild、右孩子RChild)，為了方便通過孩子節點查找父節點，引用域中可以考慮添加父節點引用(Parent)，存儲示意圖見圖五。
   

    

四、樹與二叉樹的轉換

1. 樹轉二叉樹

   加線，所有兄弟結點之間加一條連線。
   抹線，對樹中的每個結點，只保留他與第一個孩子結點之間的連線，刪除它與其它孩子結點之間的連線。
   整理，整理前兩步得到的樹，使之結構層次分明。

   
2. 二叉樹轉樹
   

   加線，若某結點的左孩子結點存在，將左孩子結點的右孩子結點、右孩子結點的右孩子結點……都作為該結點的孩子結點，將該結點與這些右孩子結點用線連接起來。
   抹線，刪除原二叉樹中所有結點與其右孩子結點的連線。
   整理，整理前兩步得到的樹，使之結構層次分明。
   

五、樹遍歷實現

 1 /// <summary>
 2 /// 先序遍歷（DLR）
 3 /// </summary>
 4 /// <![CDATA[首先訪問跟節點，然後遍歷左子樹，最後右子樹]]>
 5 static void PreOrder(Node<char> root)
 6 {
 7     if (root == null)
 8     {
 9         return;
10     }
11 
12     Print(root);
13     PreOrder(root.LChild);
14     PreOrder(root.RChild);
15 }
16 
17 /// <summary>
18 /// 中序遍歷（LDR）
19 /// </summary>
20 /// <![CDATA[先遍歷左子樹，然後根節點，最後遍歷右子樹]]>
21 static void InOrder(Node<char> root)
22 {
23     if (root == null)
24     {
25         return;
26     }
27 
28     InOrder(root.LChild);
29     Print(root);
30     InOrder(root.RChild);
31 }
32 
33 /// <summary>
34 /// 後序遍歷（LRD）
35 /// </summary>
36 /// <![CDATA[先遍歷左子樹，然後遍歷右子樹，最後遍歷根節點]]>
37 static void PostOrder(Node<char> root)
38 {
39     if (root == null)
40     {
41         return;
42     }
43 
44     PostOrder(root.LChild);
45     PostOrder(root.RChild);
46     Print(root);
47 }
48 
49 /// <summary>
50 /// 層序遍歷
51 /// </summary>
52 /// <![CDATA[從上向下從左到右]]>
53 static void LevelOrder(Node<char> root)
54 {
55     if (root == null)
56     {
57         return;
58     }
59     CSeqQueue<Node<char>> sq = new CSeqQueue<Node<char>>(50);
60     sq.In(root);
61     while (!sq.IsEmpty())
62     {
63         Node<char> tmp = sq.Out();
64         Print(tmp);
65 
66         if (tmp.LChild != null)
67         {
68             sq.In(tmp.LChild);
69         }
70 
71         if (tmp.RChild != null)
72         {
73             sq.In(tmp.RChild);
74         }
75     }
76 }