Chap4 Tree.

Presentation on theme: "Chap4 Tree."— Presentation transcript:

1 Chap4 Tree

2 Tree 「樹」（tree）是由一個或一個以上的節點（node）組成 有一個特殊的節點稱為「節點」（root） (一定要有的 )
其餘的節點分為  n  ≧  0個不同的集合，T1,T2,T3,...Tn，則每一個集合稱它的子樹

3 Tree

4 Tree 分支度（degree）：每個節點所有的子樹個數。例如像B的分支度為 2, D的分支度為3，F、K、I、J…等為0。
樹的分支度（degree of a tree）：樹中所有節點的最大分支度。節點中最大分支度為3，所以樹的分支度也為3。 樹葉(Leaf)或稱終端節點（terminal nodes）：分支度為零的節點。 非終端節點（nonterminal nodes）：樹葉以外的節點。 如A、B、C、D、E、H等。 子點(Child)：某節點所有子樹的樹根。例如：A的子點為B、C、D，B的子點為E、F。 父點(Parent)：若X節點為Y節點的子點，則Y節點為X節點的父點。例如：B的父點為A，G的父點為C。

5 Tree 兄弟(Brother)：同一個父點的所有子點互稱兄弟。例如：B、C、D為兄弟，H、J、I也為兄弟。
階度（level）：令樹根的階度1，若某節點的階度為L，則其子點的階度為L+1。 例如：K位於階度4，E、F、G、H、I、J位於階度3。 高度(height)：樹的最大階度。例如：上圖樹的高度為4 樹林(Forest) ：是由n個互斥樹(disjoint trees)所組合成的，移去樹根即為樹林。

6 Binary Tree 二元樹 Binary Tree
二元樹是一棵空樹(Empty Tree)或是由一個樹以及兩個互相階離(disjoint trees)的二元樹(稱為左子樹(Left child tree)和右子樹(Right child tree)）所組成。 Binary Tree又稱為有序樹(Ordered  Tree) 二元樹可以是空集合，而非空集合的樹至少要有一個樹根(Root)。

7 Binary  Tree

8 Samples of Trees Complete Binary Tree A A A 1 B B 2 B C C
Skewed Binary Tree 3 D E F G D 4 H I E 5

9 Binary Tree 二元樹的特性如下： 第 i 階層的總節點數小於等於 2^i - 1， i ≧ 1。
二元樹的節點總數少於2^k， k 為二元樹的深度，k ≧ 1。 樹葉節點總數等於分支度為 2 的節點總數加  1 。

10 二元樹的建立 二元搜尋樹(Binary search tree)採用遞迴定義 Binary search tree為二元樹，具下列性質：
左子樹節點的值小於（≦）根節點的值。 右子樹節點的值大於（≧）根節點的值。 左、右子樹仍為二元搜尋樹。

11 二元樹的建立 二元搜尋樹採用遞迴建立 演算法如下： 找到正確的位置，建立一節點，其左右子樹皆為空樹，再將此節點插入此二元搜尋樹。
若輸入值小於節點值，則遞迴呼叫建立二元搜尋樹的程序，繼續往左子樹建樹。 若輸入值大於節點值，則遞迴呼叫建立二元搜尋樹的程序，往右子樹建樹。

12

13 Insert Node in Binary Search Tree
30 30 30 40 40 5 40 5 5 2 80 2 35 80 2 Insert 80 Insert 35

14 Sequential Representation
[1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I (1) waste space (2) insertion/deletion problem A [1] [2] [3] [4] [5] [6] [7] [8] [9] . [16] A B -- C D . E B A C B C D D E F G E H I

15 Linked Representation
typedef struct node *tree_pointer; typedef struct node { int data; tree_pointer left_child, right_child; }; data left_child data right_child left_child right_child

16 node structure left_child data value right_child typedef emun {not, and, or, true, false } logical; typedef struct node *tree_pointer; typedef struct node { tree_pointer list_child; logical data; short int value; tree_pointer right_child; } ;

17 Binary Tree Traversal 二元樹追蹤（Binary Tree Traversal）
二元樹的追蹤系利用某種順序，到二元樹的每個節點(Node)去拜訪一次，也就將二元樹化為線性關係。 前序追蹤（Preorder  Traversal,  depth - first  order,  NLR） 拜訪樹根 用前序追蹤左子樹 用前序追蹤右子樹

18 Binary Tree Traversal + inorder traversal A / B * C * D + E
infix expression preorder traversal + * * / A B C D E prefix expression postorder traversal A B / C * D * E + postfix expression level order traversal + * E * D / C A B * E * D / C A B

19 Binary Tree Traversal 中序追蹤 (Inorder Traversal, symmetric order, LRN)
用中序追蹤左子樹 拜訪樹根 用中序追蹤右子樹 後序追蹤(Postorder  Traversal,  LRN） 用後序追蹤左子樹 用後序追蹤右子樹

20 Inorder Traversal (recursive version)
void inorder(tree_pointer ptr) /* inorder tree traversal */ { if (ptr) { inorder(ptr->left_child); printf(“%d”, ptr->data); indorder(ptr->right_child); } A / B * C * D + E

21 Preorder Traversal (recursive version)
void preorder(tree_pointer ptr) /* preorder tree traversal */ { if (ptr) { printf(“%d”, ptr->data); preorder(ptr->left_child); predorder(ptr->right_child); } + * * / A B C D E

22 Postorder Traversal (recursive version)
void postorder(tree_pointer ptr) /* postorder tree traversal */ { if (ptr) { postorder(ptr->left_child); postdorder(ptr->right_child); printf(“%d”, ptr->data); } A B / C * D * E +

23 樹林(Forest) A forest is a set of n >= 0 disjoint trees A Forest G A
B E F H I B C D C F G D H I