記錄學習內容。
主要是看網路上的文章和影片，做些紀錄。
內容可能有錯誤。

讀:

Tree(樹): Intro(簡介)

筆記:

1 height 高度 : 葉子(最底部的節點) 算是0 高度 。 是從0開始算高度 ，不是1 。

2 depth 深度 : 某個點 到 root (頂點) 走過的邊 有幾條

3 level：定義root的level為1，每往下跑一層，+1。
跟height相反 ， height 是從最下面(0)往上跑(+1) 。
Level 是 從 最上面(1)往下跑(+1) 。

4 descendant leaf = leaf node = NIL = external node (葉節點)

讀:

Binary Tree: Intro(簡介)

筆記:
1
Full Binary Tree (Perfect Binary Tree) 滿足 :
1 每個 父母 都要有 兩個 小孩
2 每個小孩都要同一層
反正就是這個樹全部都要填滿，就叫Full 或 Perfect

2
Complete Binary Tree
不用填滿，但是要照著順序，從左到右，一個一個的節點

3
最後有講到Binary Tree的應用 。
看一下Huffman Coding Tree 是什麼:
[Data Structure][Tree] - Huffman tree

接著來讀，來看樹的走訪:
裡面有圖表示樹的走訪順序，可以練習:

Binary Tree: Traversal(尋訪)

筆記:

1

三種Preorder、Inorder、Postorder:

Preorder (這種走法就是DFS (Depth-First Search(DFS，深度優先搜尋)) ) :
印節點、往左走(遞迴)、往右走(遞迴)

Inorder: 往左走(遞迴)、印節點、往右走(遞迴)

(在BST中，照著inorder順序印出node，就會得到「排好序」的資料。)

Postorder: 往左走(遞迴)、往右走(遞迴) 、印節點

之前有紀錄:
https://ithelp.ithome.com.tw/articles/10221443

2

接著講了Level-Order Traversal :
實作方式是用queue push 左 右 子節點 。pop再從top出來。

3

接著講了，要怎麼用迴圈 去跑inorder走訪
1 先找到整棵樹的最左邊節點
2 從 最左邊 節點 就開始 進到: InorderSuccessor 方法裡 ，不斷找下一個走訪的節點，以迴圈的方式。
3 Successor 中文是 接班人 ，下一步的意思

4

接著 講了 inorder 怎麼找上一個節點。
叫做Predecessor 方法
Predecessor 中文意思是 前任，上一步的意思