2016年4月12日 星期二

Binary Tree



http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html

Binary Tree
「二元樹」是計算機科學最重要的概念,甚至可以說:二元樹開創了計算機科學。
像是資料結構 Binary Search Tree 與 Heap ,交換式排序演算法的 Decision Tree 、資料壓縮的 Huffman Tree 、 3D 繪圖的 BSP Tree 、編譯器的 Parse Tree…… ,這一大堆稀奇古怪的術語,通通都是二元樹。總之,二元樹的應用相當廣泛,是資工系學生必學的基礎概念。
「二元樹」與「樹」,儘管名稱相近,但是概念不相近,至於用途更是天差地遠,兩者可以分別獨立學習。二元樹:資料結構課程的二元搜尋樹章節,會順便引出二元樹的概念;樹:演算法課程的圖論章節,一開始就會介紹樹的定義。
言歸正傳。「二元樹」就是分兩岔的樹,每個節點可以有左小孩和右小孩,每個節點可以有零個、一個、兩個小孩。
順便介紹幾個特殊的二元樹:
full binary tree :除了樹葉以外,每個節點都有兩個小孩。
complete binary tree :各層節點全滿,除了最後一層,最後一層節點全部靠左。
perfect binary tree :各層節點全滿。同時也是 full binary tree 和 complete binary tree 。
Binary Tree 資料結構
第一種方法,是建立節點,運用指標串接各個節點。
 
  1. struct Node
  2. {
  3.     Nodeparent;
  4.     Nodeleft;
  5.     Noderight;
  6.     int data;
  7. };
  8.  
  9. Noderoot = 0;
第二種方法,是讓二進位數字一一對應到二元樹的節點。
建立一個陣列,運用陣列索引值就能得到各個節點:樹根的索引值固定是一,索引值乘上兩倍就得到左小孩,索引值乘上兩倍再加一就得到右小孩,索引值除以二就得到父親。
優點是程式碼簡潔,效率高。
缺點是浪費記憶體空間。如果不是 complete binary tree ,那麼陣列就有很多閒置空格。
另一個缺點是樹的高度受限制。 1024 = 2^10 格的陣列,樹的高度只有 10 ,不能更高了。
 
  1. int tree[5 + 1];    // tree[0]不使用,只有五個節點。
  2. int left_child(int index) {return index * 2;}
  3. int right_child(int index) {return index * 2 + 1;}
  4.  
  5. void binary_tree()
  6. {
  7.     cout << "根為" << tree[1];
  8.     cout << "根的左邊小孩是" << tree[left_child(1)];
  9.     cout << "根的右邊小孩是" << tree[right_child(1)];
  10. }
UVa 112 122
Binary Tree Traversal
二元樹的遍歷順序,理論上總共四種──但是事實上還是只有 DFS 與 BFS 兩種,只不過更動了節點的輸出順序。
注意樹根的位置,就能輕鬆解讀這四種序。
Preorder Traversal 前序遍歷
理論上的遍歷順序是:根、左子樹、右子樹。根排在前面。
即是Depth-first Search。

Inorder Traversal 中序遍歷
理論上的遍歷順序是:左子樹、根、右子樹。根排在中間。
實際上是採用Depth-first Search,只不過更動了節點的輸出順序。

Postorder Traversal 後序遍歷
理論上的遍歷順序是:左子樹、右子樹、根。根排在後面。
實際上是採用Depth-first Search,只不過更動了節點的輸出順序。

Level-order Traversal 層序遍歷
即是Breath-first Search。
 
  1. struct Node
  2. {
  3.     Nodeleft;
  4.     Noderight;
  5.     int data;
  6. };
  7.  
  8. Noderoot = ...;   // 假設已經建立二元樹了
  9.  
  10. // preorder traversal
  11. void traversal(Nodep)
  12. {
  13.     if (!preturn;
  14.     cout << p->data;    // 先輸出樹根
  15.     traversal(p->left); // 次輸出左子樹
  16.     traversal(p->right);// 後輸出右子樹
  17. }
  18.  
  19. // inorder traversal
  20. void traversal(Nodep)
  21. {
  22.     if (!preturn;
  23.     traversal(p->left);
  24.     cout << p->data;    // 挪到中間,改變輸出順序。
  25.     traversal(p->right);
  26. }
  27.  
  28. // postorder traversal
  29. void traversal(Nodep)
  30. {
  31.     if (!preturn;
  32.     traversal(p->left);
  33.     traversal(p->right);
  34.     cout << p->data;    // 挪到後面,改變輸出順序。
  35. }
  36.  
  37. // level-order traversal
  38. void traversal(Noderoot)
  39. {
  40.     queue<Node*> q;
  41.     q.push(root);
  42.     while (!q.empty())
  43.     {
  44.         Nodep = q.front(); q.pop();
  45.         cout << p->data;    // 這行往下挪,結果仍相同。
  46.         if (p->left)  q.push(p->left);
  47.         if (p->rightq.push(p->right);
  48.     }
  49. }
  50.  
  51. // preorder traversal
  52. void traversal(Noderoot)
  53. {
  54.     stack<Node*> s;
  55.     s.push(root);
  56.     while (!s.empty())
  57.     {
  58.         Nodep = s.front(); s.pop();
  59.         cout << p->data;    // 這行往下挪,結果仍相同。
  60.         if (p->rights.push(p->right);
  61.         if (p->left)  s.push(p->left);
  62.         // 堆疊先進後出、顛倒順序,故先放右小孩、再放左小孩。
  63.     }
  64. }
UVa 112 699
Binary Tree Reconstruction
以一棵二元樹能得到前序、中序、後序、層序,那麼以前序、中序、後序、層序能得到一棵二元樹嗎?
只有一種序,是無法還原出一棵二元樹的,有很多可能性。
有兩種序,就有機會還原出唯一一棵二元樹。比方說,只知道 preorder 和 inorder ,求出原本的二元樹。
運用 Divide and Conquer 可以巧妙解決。在 preorder 之中,最左邊的元素就是 root ;在 inorder 之中, root 的兩邊分別為左子樹和右子樹──利用 root 便可區分左子樹和右子樹。子樹也是樹,可以用相同手法繼續分割,最後便可求出整棵樹的架構。
但是只有 preorder 和 postorder 的話,是做不出答案的。因為無法確定樹根的位置。
那麼 level-order 呢?大家就自己想想吧。
UVa 10701 536 548 10410 12347
Polish Notation / Reverse Polish Notation
凡是談到二元樹的前序、中序、後序,總是順便談到四則運算的前序、中序、後序表示法。
我們可以將一道四則運算式子,換成二元樹。
然後列出此二元樹的前序、中序、後序。其中前序就是波蘭表示法,又稱作 prefix ;中序就是原來的四則運算式子、需要括號,又稱作 infix ;後序就是逆波蘭表示法,又稱作 postfix 。
然而,建立二元樹是很麻煩的。能不能略過二元樹,直接把四則運算式子換成波蘭表示法(逆波蘭表示法)呢?當然能!只要運用 stack ,就可以做到這件事情。
 
  1. 通常這是學校作業,所以就不提供程式碼了。
一道四則運算式子,改成波蘭表示法(逆波蘭表示法)之後,計算過程變成由左往右計算,不必顧慮先乘除後加減、不必顧慮括號,只需要一個額外的 stack 作為輔助。
程式語言的四則運算式子,事實上都會被編譯器轉換成波蘭表示法(逆波蘭表示法),以利電腦計算。
 
  1. 通常這是學校作業,所以就不提供程式碼了。
UVa 372 727 11234 172 10700 10847
N-ary Tree
N-ary Tree ( k-way Tree )
「多元樹」就是分 N 岔的樹,每個節點可以有零個、一個、兩個、 …… 、 N 個小孩。
注意到:多元樹,節點只有一個小孩時,沒有左小孩、右小孩的差別;二元樹,節點只有一個小孩時,有左小孩、右小孩的差別。
Left Child/Right Sibling Representation
一棵多元樹,可以改用二元樹表示:多元樹的左小孩,是二元樹的左小孩;多元樹的其餘小孩(左小孩的兄弟),是二元樹的右小孩、右右小孩、 …… 。
芸芸多元樹,皆得簡化成二元樹;區區二元樹,便可描述出多元樹。萬流歸宗、一以貫之。
有興趣的讀者,可以觀察多元樹與轉化過的二元樹的前序、中序、後序、層序。也可以計算一下多元樹的節點數目、樹葉數目、高度。

沒有留言: