有错请指教。
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???