iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 21
0
自我挑戰組

學習資料結構30天系列 第 21

[Data Structure][Tree] - Binary Search Tree &Heap

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

排序

  1. 先第一個數值當成Binary Tree的Root。
  2. 接下來的資料,以遞迴的方式跟Root的數值比較以後,將小於或等於root放在Left subtree,而大於root的放在Right subtree。
  • 以30、26、15、40、29為例子
    • https://ithelp.ithome.com.tw/upload/images/20181104/20112438jifLvzIrbO.jpg
    • https://ithelp.ithome.com.tw/upload/images/20181104/20112438tynMZF8KH0.jpg
    • https://ithelp.ithome.com.tw/upload/images/20181104/20112438m7aLS4KHOc.jpg
    • https://ithelp.ithome.com.tw/upload/images/20181104/20112438ybVxTVtfb4.jpg

二元搜尋樹 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. Map heap : 任何一個node會大於它的所有child node,Map heap中最大的node一定會是root。
  3. Min heap : 任何一個node會小於它的所有child node,Min heap中最小的node一定會是root。
  • Map heap :
    https://ithelp.ithome.com.tw/upload/images/20181104/20112438zj6MYVSHx7.jpg

參考

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


上一篇
[Data Structure][Tree] - Binary Tree Traversal
下一篇
[Data Structure][Tree] - Balanced Search Tree
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言