為自己Coding

YO~~ 剛跨入AI人工智慧領域的小小工程師, 熱愛自學, 熱愛分享, 下班後的我想為自己Coding, 積極撰寫教學文, 想將自學的程式知識分享給大家, 不斷追求進步的自己, 希望有一天能回饋社會,幫助需要幫助的人, 如果您有什麼很酷的想法,也覺得我還行,歡迎您找我合作~~

LeetCode學習筆記 - Binary Tree 二元樹 - 觀念介紹

發布於

Github連結

攝影師:Ákos Szabó,連結:Pexels




1. 樹的基本介紹


  • 為一種抽象的資料類型(ADT)或是實作這一種抽象資料類型的資料結構,用來描述具有樹狀結構性質的資料結構
  • 樹的節點個數為一或多個有限的集合,且必須存在一個根節點,根節點會分枝成n個不會交集的子節點,而這些子節點各自都為一個子集合,而一個子集合也為一顆子樹


名詞介紹

  • 根節點(Root): 第一個節點,它不具有復節點,像是圖中的節點A
  • 葉節點(Leaf): 此節點已經是最後的分支了,不再具有子節點,像是圖中的G、D、H、I、J
  • 祖先節點(Ancenstors): 指某個節點到根節點之間所經過的所有節點,都為這個節點的祖先節點
  • n元樹; 表示這個樹的節點最多有n個分支子節點
  • 分支度(Degree): 美個節點分支的子節點數量,像是E的分支度為2
  • 階層(Level): 由根節點開始計算,隨著子節點不斷往下計算階層數,如果右側的階層樹
  • 樹高(Height): 又稱為深度(Depth),表示為此樹的最大階層樹,像圖中的樹高就是3
  • 非終端節點(Noterminal Nodes): 只要還有子節點就算非終端節點




2. 什麼是BInary Tree?


  • 二元樹指的就是每個節點最多只有兩個分支(也就是子節點樹量只會有小於兩個)的樹狀結構,由根節點分支成左右子樹(稱為左子樹和右子樹),且其分支具有左右順序不能顛倒
  • 二元樹用在資料結構上,通常會是對節點定義一個標記函式,將一些值和每個節點建立相關聯,這樣標記的二元樹就能夠實現二元搜尋樹和二元堆積,目的是可以應用於高效率的搜尋和排序


實用算法


  • 二元樹中的第i層,最多可以具有2的i - 1次方個節點數量
  • 樹高度為k的二元樹,最多可以擁有2的k+1次方減1的節點數量,而節點數量與此公式結果計算出來的相等,稱為完滿二元樹



提醒: 當節點並沒有左右兩邊的都具有節點,沒有的那一邊會連接到空節點NIL(None/null)



3. 二元樹種類 - 完滿二元樹、完整二元樹、歪斜樹


完滿二元樹 Fully Binary Tree

指的就是沒有任何一個節點會只有單獨連接的左或右節點,而計算節點數量就可以透過公式來達成





完整二元樹 Complete Binary Tree

如果高度為h,其節點的數量會小於等於公式


須符合從上到下,從左到右的規則,也就是可以只有左節點,但不能只有右節點



歪斜樹 Skewed Binary Tree

只有一邊的節點,只有左邊節點就為左歪斜樹,右邊就為右歪斜樹






4. 二元樹 適用範圍?


  • 樹狀結構下分支最多只有兩個方向的時候(超過兩個方向: 字典樹,全部都只有一個方向: Linked List)
  • 當為二元樹的前置狀況時
  • 當我們不在乎節點值大小的關係時,也就是非二元搜尋樹的狀況


補充: 二元搜尋樹用在當我們需要快速在樹狀結構下搜尋某個節點的值,因為它規定右邊的節點會比自己小,左邊的節點會比自己大




Reference

https://zh.wikipedia.org/wiki/二叉树

https://zh.wikipedia.org/wiki/线索二叉树

http://wayne.cif.takming.edu.tw/datastru/tree.pdf


喜歡我的文章嗎?
別忘了給點支持與讚賞,讓我知道創作的路上有你陪伴。

CC BY-NC-ND 2.0 版權聲明

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區