(資料結構)樹
先瞭解的專有名詞
- node 節點
- degree 分歧度, the number of subtreesof the node
- leaf(terminal) 葉節點, the node with degree 0
- parent 父節點or母節點, 上一個節點
- children 子節點, 下一節點
- sibling 兄弟節點
- ancestor 祖先, all the nodes alongthe path from the root to the node
- degree 層, 根節點是第一層…
- depth 深度，樹的高度
可以用來表示樹的方式
- List representation 很少人在用的方法，因為很耗費記憶體
2. Left Child — Right Sibling 一個node只會有兩個節點，左節點是child，右節點是sibling，因為只有兩個節點，我們叫他Binarty trees。並且有一重要性質，Any tree can be transformed into a binary tree。
很明顯，binary tree比較多人使用，因此我們現在開始討論binary tree
一些小小的性質
- maximum of the binary tree = 2^i-1, which i is depth.
- 任意不空的binary tree，leaf node(葉節點) = the number of nodes of degree 2(第二層節點的數量) + 1
- complete binary tree 完全樹 除了葉節點以外，其他的地方都要滿的
- full binary tree 包括葉節點都要滿
Binary tree 實作方式
- 用array，缺點當樹不是很滿的時候，會浪費array記憶體空間以及insert and delete難，但還滿好實作的
用指標指向下一個節點，linked representation，缺點實作小麻煩，優點不浪費記憶體且insert and delete簡單
Binary tree traversals(走訪)
- inorder 中序，左節點→parent→右節點。可以當成infix expression。
- postorder 後序，左節點→右節點→parent。可以當成postfix expression
- preorder 前序，parent→左節點→右節點。可以當成prefix expression
就如同infix expression可以用stack幫忙實作，inorder traversal也可以用stack幫忙解決。
Lever order traversal(從上到下，左到右，一層一層的traversal)，可以用queue實作
特殊的樹
- Threaded Binary Trees(Inorder)，把葉節點沒用到的指標拿去指別的地方，左節點指向在inorder traversal時的上一個節點，右節點指向inorder traversal時的下一個節點。預設是inorder，當然也有其他排序的樹。
2. Heap，記憶體空間裏也有一個記憶體空間叫做heap，不過這邊講的是資料結構，分為max heap以及min heap，特性為所有子節點小於父節點or反之，並且規定是要complete binary tree。
ps, heap非常重要，並且也是用來實作另外一個資料結構priority queue的重要要素。
因為比較重要的data structure，這邊講一下他的優點，max and min value insert and delete is O(log n)，find max or min, O(1)。
inser實作是先放在葉節點，在一個一個往上(parent)比較，慢慢地找到正確的位置。
delete則是先把任意葉節點(通常是最後一個節點)拿去放在頭位置(因頭被刪掉了)，然後從上往下慢慢地比較，找到正確的位置。
3. Binary search tree，左小右大，左節點小於parent，右節點大於parent，沒規定要用complete binary tree。insert and delete比較麻煩，insert就從頭看到尾，最後一定會放在某個葉節點，而delete就要分三個case(0 subtree,1 subtree,2 subtree) delete了，這邊就不多談如何實作了。
4. Selection tree，有win tree 跟 lose tree兩種小子類，不過其實都差不多，只是lose tree多了一點點東西，目的是想讓時間複雜度變快，不過也沒快多少。Selection tree概念就是從底到頭，每兩個節點比賽，贏的就上去的概念
