• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

二叉树前奏

开发技术 开发技术 2周前 (09-14) 19次浏览
目录
  • 前言
    • 回顾
    • 树形结构
      • 树的概念
      • 有序树,无序树,森林
      • 二叉树(Binary Tree)
      • 真二叉树(Proper Binary Tree)
      • 满二叉树(Full Binary Tree)
      • 完全二叉树(Complete Binary Tree)
    • 小结
    • 声明

前言

回顾

在前面的数据结构学习中,无论是以顺序结构存储的 数组 还是链式存储结构的 链表、栈与队列 等(没有阅读过之前的随笔,可以点击对应的名词跳转) 。实际上都可以归类成线性结构。

今天复习另外一种数据结构,树形结构,没错,就是生活中的那种树,要倒过来的那种。

二叉树前奏

以树干的分支数量为准,可以将树分为二叉树与多叉树,二叉树是我们要研究的重点

二叉树前奏

生活中的树形结构也有很多,例如公司的股权图,文件目录等等,使用树形结构可以大大提高效率,同时树形结构也是被广泛应用于底层结构,例如数据库索引

树形结构

树的概念

节点:根节点、父节点、子节点、兄弟节点

空树:一棵树可以没有任何节点

一棵树可以只有1个节点,也就是只有根节点

子树:左子树、右子树

节点的度(degree):子树的个数

树的度:所有节点度中的最大值

叶子节点(leaf):度为 0 的节点

非叶子节点:度不为 0 的节点

层数(level):根节点在第1层,根节点的子节点在第2层,以此类推(有些教程也从第0层开始计算)

节点的深度(depth):从根节点到当前节点的唯一路径上的节点总数

节点的高度(height):从当前节点到最远叶子节点的路径上的节点总数

树的深度:所有节点深度中的最大值

树的高度:所有节点高度中的最大值

树的深度等于树的高度

有序树,无序树,森林

有序树

  • 树中任意节点的子节点之间有顺序关系

无序树

  • 树中任意节点的子节点之间没有顺序关系,也称为“自由树”

森林

  • 由m(m≥0)棵互不相交的树组成的集合

二叉树(Binary Tree)

1、二叉树的特点

  • 每个节点的度最大为2(最多拥有2棵子树)
  • 左子树和右子树是有顺序的(有序树)
  • 即使某节点只有一棵子树,也要区分左右子树

2、二叉树图解

二叉树前奏

3、二叉树的性质

  • 非空二叉树的第 i 层,最多有 $2^{i-1}$ 个节点(i ≥ 1)
  • 在高度为 h 的二叉树上最多有$2^{h-1}$个结点(h ≥ 1)
  • 对于任何一棵非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2,则有: n0 = n2 + 1
    • 假设度为1的节点个数为n1,那么二叉树的节点总数n= n0 + n1 + n2
    • 二叉树的边数T = n1 + 2 * n2 = n–1 = n0 + n1 + n2–1
    • 因此n0 = n2 + 1

真二叉树(Proper Binary Tree)

概念:所有节点的度都要么为 0,要么为 2

二叉树前奏

满二叉树(Full Binary Tree)

概念:最后一层节点的度都为0,其他节点的度都为2

性质

  • 假设满二叉树的高度为h(h≥1),那么有:
    • 第i层的节点数量: $2^{i-1}$
    • 叶子节点数量: $2^{h-1}$
    • 总节点数量 n,则 n = $2^h-1$ = $2^0$ + $2^1$ + $2^2$ + … + $2^{h-1}$
    • h = $log_2n+1$
  • 同样高度的二叉树中,满二叉树的叶子节点数量最多、总节点数量最多
  • 满二叉树一定是真二叉树,真二叉树不一定是满二叉树

图解

二叉树前奏

完全二叉树(Complete Binary Tree)

概念:叶子节点只会出现最后 2 层,且最后 1 层的叶子结点都靠左对齐

完全二叉树与满二叉树是很相似的,所以也可以这么定义,完全二叉树:对节点从上至下、左至右开始编号,其所有编号都能与相同高度的满二叉树中的编号对应

二叉树前奏

小结论:1、完全二叉树从根结点至倒数第2层是一棵满二叉树,2、满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

性质

  • 度为 1 的节点只有左子树,度为1的节点要么是 1 个,要么是 0 个

  • 同样节点数量的二叉树,完全二叉树的高度最小(从上往下,从左往右满排布)

  • 假设完全二叉树的高度为h(h ≥ 1),那么有:

    • 至少有$2^{h−1}$个节点, $2^0$ + $2^1$ + $2^2$ + … + $2^{h-2}$ + 1
    • 最多有$2^h−1$个节点( 满二叉树 ), $2^0$ + $2^1$ + $2^2$ + … + $2^{h-1}$
  • 假设总节点数量为 n

    • $2^{h−1}$ <= $2^h$
    • $h-1$ <= $log_2n$ < $h$
    • $h$ = foor $(log_2n) + 1$
    • floor是向下取整,另外,ceiling是向上取整
  • 二叉树前奏

  • 二叉树前奏

例题巩固:如果一棵完全二叉树有768个节点,求叶子节点的个数

求解:

  • 假设叶子节点个数为n0,度为1的节点个数为n1,度为2的节点个数为n2,总结点个数为n。则n = n0 + n1 + n2,且n0 = n2 + 1
  • 等式替换:n = 2n0 + n1 – 1
  • 完全二叉树的 n1 要么为 0,要么为 1
    • (1) n1为1时,n = 2n0,n必然是偶数,叶子节点个数n0 = n / 2,非叶子节点个数n1 + n2 = n / 2
    • (2) n1为0时,n = 2n0–1,n必然是奇数,叶子节点个数n0 = (n + 1) / 2,非叶子节点个数n1 + n2 = (n–1) / 2

结论:

  • 叶子节点个数n0 = floor((n + 1) / 2) = ceiling(n / 2)
  • 非叶子节点个数n1 + n2 = floor(n / 2) = ceiling((n–1) / 2)
  • 因此叶子节点个数n0 = 384

小结

1、对于树的一些基本概念要牢记,否则,你连笔试题目都看不懂

2、一些树的性质是要记住的,不要觉得公式没用,不然,代码都敲不出来

3、对着目录过一遍,树的概念,以此作为笔记写下,好记性不如烂笔头

声明

个人能力有限,有不正确的地方,还请指正

文章为原创,欢迎转载,注明出处即可

文章有代码的会上传github,欢迎star

GitHub地址


程序员灯塔 , 版权所有
转载请注明原文链接:https://www.wangt.cc/2020/09/%e4%ba%8c%e5%8f%89%e6%a0%91%e5%89%8d%e5%a5%8f/
喜欢 (0)