资料结构–树tree.ppt

資料結構–樹(Tree) 2013.05 綠園 樹(Tree) Tree是一種特殊的資料結構，是由一個或一個以上的節點所組成的有限集合。 具有下列特質： 存在一個特殊的節點，稱為樹根(root)。 其餘的節點分為 n≥0 個互斥的集合，T1,T2, T3,...Tn，且每個集合稱為子樹。 樹(Tree) Tree是一種特殊的資料結構，是由一個或一個以上的節點所組成的有限集合。 具有下列特質： 存在一個特殊的節點，稱為樹根(root)。 其餘的節點分為 n≥0 個互斥的集合，T1,T2, T3,...Tn，且每個集合稱為子樹。 A B C D E A為根節點 Ｂ、Ｃ、Ｄ、Ｅ均為Ａ的子節點 樹(Tree)的專有名詞 樹由一個以上的節點（node)與將節點連接起來的分支（branch)所組成。 節點分支出來的節點稱為「子節點」，其上層的節點稱為「父節點」。 樹的最上面節點稱為「根」（root)。 底下沒有子節點的節點稱為葉子（leaf)。 樹(Tree)的專有名詞 樹由一個以上的節點（node)與將節點連接起來的分支（branch)所組成。 節點分支出來的節點稱為「子節點」，其上層的節點稱為「父節點」。 樹的最上面節點稱為「根」（root)。 底下沒有子節點的節點稱為葉子（leaf)。 A 為 root A B C D E F G H DEFGH 為 leaf * 範例 1 下列哪一種不是樹(Tree)？ (A)一個節點 (B)環狀串列 (C)一個沒有迴路的連通圖(Connected Graph) (D)一個邊數比點數少1的連通圖。 範例 2 下圖中樹(tree)有幾個樹葉節點(leaf node)？ (A)4 (B)5 (C)9 (D)11 二元樹(binary tree) 樹的各節點分支如在2個以下（含2個），則稱為二元樹（binary tree) 二元樹(binary tree) 樹的各節點分支如在2個以下（含2個），則稱為二元樹（binary tree) A B C F G D E A B C F G D E H 二元樹(binary tree) 樹的各節點分支如在2個以下（含2個），則稱為二元樹（binary tree) A B C F G D E A B C F G D E H 二元樹（binary tree) 樹的深度、階度與高度 Depth（深度）：由根到某個節點間所通過的分支數，稱為該節點的深度。 Level（階層或階度）：樹的層級，假設樹根A為階層1，BC節點即為階層2，FGH為階層4。 Height（高度）：樹的最大階度，稱為樹的高度。 問： 節點B、G、E的深度分別為？ 樹的高度為？ 節點A（根）的深度為？ A B C F G D E H 完全二元樹　v.s　完整二元樹 完滿二元樹(full binary tree) 完整二元樹(complete binary tree) 1 2 3 4 5 6 7 1 2 3 4 5 (full binary tree) (complete binary tree) * 二元樹串列表示法 所謂二元樹的串列表示法，就是利用鏈結串列來儲存二元樹。 也就是運用動態記憶體及指標的方式來建立二元樹。其節點結構如下： left *ptr data right *ptr 指向左子樹 節點值 指向右子樹 * 節點宣告方式如下： 可以把下圖二元樹表示成： class Node { public: int data; class Node *left; class Node *right; } typedef class Node TreeNode; typedef TreeNode *btree; * 二元樹的走訪 二元樹的走訪(Binary Tree Traversal)，最簡單的說法就是「拜訪樹中所有的節點各一次」，並且在走訪後，將樹中的資料轉化為線性關係。 如右圖，共可以有ABC、ACB、BAC、BCA、CAB、CBA 等6種走訪方法。 如果是依照二元樹特性，一律由左向右，那會只剩下三種走訪方式，分別是BAC、ABC、BCA三種。 * 中序走訪（inorder traversal) 中序走訪的順序為：左子樹→樹根→右子樹。就是沿樹的左子樹一直往下，直到無法前進後退回父節點，再往右子樹一直往下。 如果右子樹也走完了就退回上層，再重覆左、中、右的順序走訪。 如上例的中序走訪為：DBEACF * 遞迴演算法 void inorder (btree ptr) { 　if (ptr != NULL) 　{ 　　inorder(ptr-left);　 /* 走訪左子樹 */ 　　cout ptr-