前兩天介紹了Binary Tree的定義跟走訪，今天就把Binary Tree的建立規則運用來存放資料。

排序

1. 先第一個數值當成Binary Tree的Root。
2. 接下來的資料，以遞迴的方式跟Root的數值比較以後，將小於或等於root放在Left subtree，而大於root的放在Right subtree。

• 以30、26、15、40、29為例子
  • 
  • 
  • 
  • 

二元搜尋樹 Binary Search Tree

1. Binary Search Tree 不是Complete Binary tree，不需要每一層node都滿，但如果有node的話，一個node就必須要有一個數值。
2. Binary tree 的每一個node的值都不相同。
3. 每一個node的資料大於左邊child node的資料，但是小於右邊 child node的資料。
4. Left subtree 和 Right subtree也都是 Binary Search Tree。

• 搜尋規則
  在binary tree中比較root和要搜尋的數值，比root大就往Right subtree找，比root小就往Left subtree找，直到找到要搜尋的值。

堆積 Heap

1. heap 是 完整二元樹 Complete Binary tree。
2. Max heap : 任何一個node會大於它的所有child node，Max heap中最大的node一定會是root。
3. Min heap : 任何一個node會小於它的所有child node，Min heap中最小的node一定會是root。

• Max heap :
  

參考

細談資料結構 第六版
ISBN 978-986-312-014-8