线性结构

二叉树结构

至多2个分叉,如果有3个或以上,叫多叉树

生活上的树形结构

使用树形结构可以大大提高效率,也是面试中的重点。

树的基本概念

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

  • 节点:1、2、3、4、。。。
  • 根节点:1
  • 父节点:1是2、3、4、5、6的父节点,2是21、22的父节点
  • 兄弟节点:2、3、4、5、6互为兄弟节点

一棵树可以没有任何节点,称为空树。

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

子树:例如2-21就是一颗子树

左子树右子树:21是2的左子树,22是2的右子树

节点的度:子树的个数。2的度为2,6的度为1,61的度为0

树的度:所有节点度中最大的值。如图中最大的度为5,也就是1的度。

叶子节点:度为0的节点

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

层数:根节点在第1层,跟节点的子 节点在第2层,以此类推

节点的深度:根节点到当前节点的唯一路径上的节点总数。2的深度为2,31的深度为3

节点的高度:当前节点到最远叶子节点路径上的节点总数。2的高度为3

树的深度:所有节点深度中的最大值,图的深度为4

树的高度:所有节点中高度的最大值,图的高度为4

树的深度等于树的高度

有序树、无序树、森林

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

无序树:树中任意节点的子节点之间是没有顺序关系的

森林: 由 m 颗互不相交的树组成的集合

二叉树

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

二叉树是有序树,因为左右子树是严格区分的。

非空二叉树的第 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

真二叉树

所有节点的度要么为0,要么为2

满二叉树

所有节点的度要么为0,要么为2。且所有的叶子节点都在最后一层。

在同样高度的二叉树中,满二叉树的叶子节点数量最多、总节点数量最多

满二叉树一定是真二叉树,真二叉树不一定是满二叉树。

假设满二叉树的高度为 h(h>=1)

  • 第 i 层的节点数量:2^(i-1)
  • 叶子节点数量:2^(h-1)
  • 总节点:2^h-1

完全二叉树

叶子节点只会出现在最后2层,且最后1层的叶子节点都靠左对齐。

image-20210420114234983

更简单的说:完全二叉树 从上往下,从左往右 依次排布

完全二叉树从根节点倒数第2层是一棵满二叉树

满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

性质

  • 度为 1 的节点 -> 只有左子树
  • 度为 1 的节点要么 1 个,要么是 0 个
  • 同样节点数量的二叉树,完全二叉树的高度最小
  • 假设完全二叉树的高度为 h(h>=1),那么

    • 至少有 2^(h-1) 个节点
    • 至多有 2^h -1 个节点
    • 若总节点数量为 n,则 2^(h-1) <= n < 2^hh-1 <= log2^n < hh = floor(log2^n) + 1floor() 是向下取整,ceiling() 是向上取整。

还有两个关于二叉树的重要性质,在后面二叉堆会用到。如下图

面试题

老外教材的说法:



腾讯云社区邀请各位技术博主加入,福利多多噢!
Last modification:April 30th, 2021 at 11:30 pm
如果觉得我的文章对你有用,请随意赞赏