數據結構整理(二) 樹，數據結構整理
一、前言
項目源碼及其他聲明等參見數據結構（一）線性結構篇。
二、相關概念
樹作為一種應用廣泛的一對多非線性數據結構，不僅有數據間的指向關系，還有層級關系，示例見圖一。因樹的結構比較復雜，為了簡化操作及存儲，我們一般將樹轉換為二叉樹處理，因此本文主要討論二叉樹。
- 二叉樹
二叉樹是每個節點最多擁有兩個子節點的樹結構，若移除根節點則其余節點會被分成兩個互不相交的子樹，分別稱為左子樹和右子樹。二叉樹是有序樹，左右子樹有嚴格的次序，若顛倒則成為一棵不一樣的二叉樹。
- 滿二叉樹
滿二叉樹，顧名思義除葉子節點外所有節點都擁有兩個孩子，且葉子節點在同一層的二叉樹，示例見圖二。
- 完全二叉樹
完全二叉樹，移除最後一層節點後是滿二叉樹，且最後一層的節點都連續集中在最左面，示例見圖三。![]()
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 }
