【第十八天 - 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

<<:  Day05:工程师必学的 Markdown 笔记语法

>>:  Day18 用CSS做出动画效果

未来狂想:工业制造

人的科技文明发展始终来自於人性 在现阶段的科技发展和工业发展当中,人们的技术和水平越来越好,而且也有...

Mysql的资料目录

我们知道,像InnoDB、MyISAM这样的储存引擎都是把资料存在磁碟里,而作业系统是使用档案系统管...

[Day19] 在 Codecademy 学 React ~ 恍然大悟!原来那些好用的语法都是来自 JSX

前言 今天来到第 19 天, 预计 Codecademy 学习文系列会在这几天结束, 先直接进入正题...

DAY11 资料前处理-资料不平衡处理方法

试想一下,如果有个模型号称有99%的准确率,那这个模型好不好呢?答案是不一定,在处理分类问题时,我们...

[Day15] Tableau 轻松学 - 地图工作表

前言 我们已经学会使用长条图来做资料探索。然而,Tableau Desktop 除了长条图外,还有其...