有錯請指教。
Def:
- Tree
- m-way search Tree
- B tree
- Forest
- Binary Tree(BT)
- skewed BT
- Complete BT
- Full BT
- Heap
- strict BT
- Binary Search Tree(BST)
- AVL Tree
- Red-Black Tree
- Thread BT
- BT Traversal(追蹤)
- Preorder(DLR)
- Inorder(LDR)
- Postorder(LRD)
- level-order
Def(Representation):
- Tree表示方式
- Link list
- 化成Binary Tree(leftmost-child-next-right-sibling 左兒子,右兄弟)
- 給定 Tree，求 BT
給定 BT，求 Tree
- child-sibling
- 括號法
- Forest表示方式
- 化成Binary Tree
- BT表示方式
- Array
Ex:Heap
- Link list
Thm:
- Tree之基本定理
- if Tree's Degree = k
node數 = leaf數 + Degree-1之node數 + ... + Degree-k之node數
= Branch數 + 1
= (1*Degree-1之node數 + ... + k*Degree-k之node數) + 1
- BT之基本定理
- 給定 高度k，求 最多node數
- 第i個level上最多node數
- 給定 node數，求 最小高度
- leaf數 = Degree-2之node數 + 1
- 給定 node數，求 可能的BT個數
n個node可能的BT數 = sum(i個node可能的BT數 * n-1-i個node可能的BT數)
where i=0~n-1
- Complete BT之基本定理
- if n個node編號:1~n
給定 編號為i的node，求 左子點、右子點、父點
- BT Traversal(追蹤)
- 給定 BT，求 Traversal
- 給定 Traversal，求 BT
- 給定 Pre,Inorder或Post,Inorder或level,Inorder，求 BT
- 給定 Pre或Post或level或Inorder，求 Complete BT
- 給定 Pre或Post或level，求 BST
DS with Algo(要知道怎麼寫、時間複雜度):
- BT recursive algo
- BT Traversal
- Preorder(T:BT),Postorder(T:BT),Inorder(T:BT)
用Stack，O(N)
- Copy(orig:BT)
- Equal(S,T:BT)
- Count(T:BT),CountDegree1(T:BT),CountDegree2(T:BT),Leaf(T:BT)
- Height(T:BT)
- Swap(T:BT)
- Eval(T:expression BT)
- 給定 expression，求 BT
- Tree's sorting
- Heap sort
- Search Tree
- BST
Inorder可得小至大排序，RDL追蹤或stack可得大至小排序
- Insert
- Delete
- Search(T:BST,x:Data)
給定 BST及其Data range，求 平均比較次數
- Heap
可製作Priority Queue
- Insert
- Delete-max or min
- Search-max or min
- Search
- Build
- Top-Down(邊Insert邊排序)
- Bottom-up(全Insert再排序)
- Adjust(tree,i,n)
- CreateHeap(tree,n)
- Merge???
- Decrease key???