iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 18

【第十八天 - Binary Tree介紹】

Q1. binary tree 是什麼

  • 二元樹 (binary tree) 是一種資料結構,應用非常廣泛,是資訊人必學的基礎概念
  • 二元樹是圖論中的一種樹,這種樹中的每一個節點,最多只能分支出兩個子節點。
    • 當然,也有二元樹、三元樹等,可將此概念推廣為 N-ary Tree,表示最多分支出 N 個節點的樹。
  • 二元樹的優勢是,容易實作,能快速找到任意節點的 parent 跟 child,可以利用二元樹的概念建構出二元搜尋樹 (Binary Search Tree),能夠有效進行插入、搜尋
  • 二元樹的架構/術語
    • 二元樹的架構

      • 節點 (node):圖中的點
        Node

        • 根節點 (root):最上層的節點,也是整棵樹第一個節點、唯一沒有父節點的節點。
          root

        • 葉節點 (leaf):最下層的節點,也就是沒有子節點的節點
          https://ithelp.ithome.com.tw/upload/images/20210918/20140592aeu9sc6oYP.png

        • 父節點 (parent) 與 子節點 (child):一個節點可以繼續往下層長出其他節點,此時對長出來的節點稱為子節點,而子節點的上層節點稱為父節點。

          • 在二元樹中,一個 parent 只會有 0 ~ 2 個 child,而每個 child 只會有一個 parent
          • 在 Tree 的概念 (非二元樹) 中,一個 parent 底下的 child 數目沒有限制
          • Binary Tree 可以推廣為 N-ary Tree,表示一個 parent 只會有不超過 N 個 child 的 tree。
            https://ithelp.ithome.com.tw/upload/images/20210918/20140592aAGzlzzTnV.png
        • 手足 (sibling):同一個父親底下的 child,他兩個互為 sibling

        https://ithelp.ithome.com.tw/upload/images/20210918/20140592EvThzXTUsQ.png

      • 分支 (branch):圖中的邊
        https://ithelp.ithome.com.tw/upload/images/20210918/20140592zXmdAZ1Zd5.png

    • 節點深度:一個節點位於這棵樹的第幾層 (level) 就稱為該節點的深度,或者說,從該節點到 root 途經的 edge 數量即為節點深度。

    • 樹的高度/深度:一顆樹目前最高長到第幾層,就稱為該樹的高度,又或者說,離根節點最遠的葉節點深度即為該樹的高度。

  • 二元樹種類
    • 完滿二元樹 (full binary tree) :除了 leaf 之外的所有節點,都有填滿兩個 child
      https://ithelp.ithome.com.tw/upload/images/20210918/20140592sbOO747s5g.png

    • 完整二元樹 (complete binary tree):除了最後一層,其他層的節點全部填滿,並且最後一層必須是從左向右填,中間沒有空缺。
      https://ithelp.ithome.com.tw/upload/images/20210918/20140592m7hRlGxC4R.png

    • perfect binary tree:每一層節點都滿的,同時滿足 full 和 complete。
      https://ithelp.ithome.com.tw/upload/images/20210918/201405920JhiAHeTkM.png

    • 歪斜樹 (Skewed Binary Tree)

      • 左歪斜樹:一顆樹完全都往左邊長,沒有任何 right child。
        https://ithelp.ithome.com.tw/upload/images/20210918/20140592779rogSlET.png

      • 右歪斜樹:一顆樹完全都往右邊長,沒有任何 left chil
        https://ithelp.ithome.com.tw/upload/images/20210918/20140592GS3E0grCzo.png

參考資料:https://web.ntnu.edu.tw/~algo/BinaryTree.html

參考資料:https://zh.wikipedia.org/wiki/二叉树

參考資料:https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

Q2. 學會 binary tree概念可以做什麼 ?

  • 二元搜尋樹 (Binary Search Tree) 是使用 binary tree 的結構達成
    • 改進版的二元搜尋樹:AVL樹、紅黑樹

Lab. 明天要解的題目:94. Binary Tree Inorder Traversal

  • 題目連結:https://leetcode.com/problems/binary-tree-inorder-traversal/

  • 題目敘述:

    • 題目會給一個二元樹結構的資料
      https://ithelp.ithome.com.tw/upload/images/20210918/201405922VRnMJ77Bg.png
  • 測資的 Input/Output

    • 會給一個指向 root 的資料
    • 回傳中序排列
      https://ithelp.ithome.com.tw/upload/images/20210918/20140592o4Zovi3UsW.png
  • 題目的條件

    • tree 的 node 數量為 0~100 之間
    • 每個 node 的值於 -100~100 之間
      https://ithelp.ithome.com.tw/upload/images/20210918/201405926MnaZMowNn.png

上一篇
【第十七天 - 動態規劃 題目分析】
下一篇
【第十九天 - Binary Tree題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言