二叉树的一些概念

做了几套试卷发现,对二叉树的了解尚有欠缺,趁着现在还有时间,赶紧来复习一下

  • 二叉树的几种形态
  • 二叉树的几种类型
    • 完全二叉树
    • 满二叉树
    • 平衡二叉树(不做了解)
  • 相关术语
    • 结点
    • 深度
    • 高度
    • 根结点
    • 叶结点
  • 几个性质

形态

类型

满二叉树

设层数为n,则有2n – 1个结点,如下图就是当n = 3的例子

其实就是除了最后一行外每个结点都有左右子树,都是满的

满二叉树

实际上上图左边是满二叉树,右边是完全二叉树

完全二叉树

设层数为n,则除最后一行外每行的结点都达到最大个数,既最后一行外是满二叉树

或者可以说,1 ~ (n – 1)层结点个数共有2n – 1 – 1个

如下图就是当n = 3的例子,注意红框圈起来的部分

完全二叉树

不难推出:具有n个结点的完全二叉树的深度为floor(log2n) + 1

似乎满二叉树也适用于这个↑理论

术语

注:一下几个名词的含义根据我的理解得出来的,不是最权威的定义,如需权威定义,可参考度娘百科

名词含义
结点node,一个包含数据元素 + 若干指向子树的分支的点
根结点root,最头上的那个结点,没有上一级
叶结点尾巴上的点,度数为0的结点,没有下一级
分枝结点度数不为0的结点,有上下级
深度第几层
高度有几层
此结点的分支数目

文章似乎存在有问题,欢迎指出

本站遵循「CC BY 4.0」创作共享协议,转载请注明出处