引入
我们介绍了什么是二叉树、以及二叉树一些与众不同的特点,例如只能有两个孩子,两个孩子还分为左子树和右子树,那么今天我们来看看特殊的二叉树。
斜树
¡¡™
顾名思义,斜树一定要倾斜。也就是说,一棵树
- 只有左子树
- 只有右子树
这样就不是斜树了。
满二叉树
如果有一棵树
- 所有分支的结点
都存在左子树和右子树
- 并且所有
叶子都在同一层上
- 我们就称之为
满二叉树
满二叉树的特点
叶子只能出现在最下一层
,如果最下一层不是叶子,那证明所有叶子并不是在同一层上,不符合满二叉树条件非叶子结点的度一定是 2
,度是每个结点的子树数量,既然是二叉树,不是叶子结点度一定是2在同样深度的二叉树中,满二叉树的结点一定最多
,这基本是废话,层数相同,满二叉树的每个结点都有左子树和右子树,结点一定是满二叉树最多。
完全二叉树
如果存在一棵树
- 具有 n 个结点的二叉树按层序编号。
- 编号为 i ($1 \leq i \leq n$) 的结点,与同样深度的满二叉树中的 i 结点
- 如果 i 和 i 位置完全相同,我们就称这棵二叉树为完全二叉树
我们来看看
完全二叉树 | 满二叉树 |
---|---|
![]() |
![]() |
你可以这么理解
- 完全二叉树的结点可能不如满二叉树多
- 但是完全二叉树的所有结点序号一定能在满二叉树中找到
- 完全二叉树是即将完成的满二叉树…中间『停止施工』了而已…
完全二叉树的特点
叶子结点只能出现在最下两层
,因为每个结点的编号是一层一层的写,要满足完全二叉树的所有编号跟满二叉树编号相同,必然不能突破两层,因为超过两层,第三层的哪几个结点的序号,肯定就找不到了。最下层的叶子一定集中在左侧连续位置
,必须的啊,因为新的一层是从左向右编号,也在一定是在左侧连续位置啊,右边还没编号呢…倒数第二层,如果有叶子结点,一定都在右部连续位置
,也是必须的啊,倒数第二层的叶子,肯定是最后一层叶子没占的那些地方啊!如果结点的度为1,那该结点只有左孩子
,也是废话,从左向右编号,结点只有1个孩子,那肯定是左孩子啊….同样结点的二叉树,完全二叉树深度最小
,必须的啊,深度是层数,完全二叉树必须补完一层再来下一层,肯定是完全二叉树深度最小。
注意:满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
一些反例
图示 | 原因 |
---|---|
![]() |
5号结点没有左子树,竟然出现了右子树,错误! |
![]() |
6号7号应该是3号的左右子树,第三层没有补全就写了第四层,错误! |
![]() |
5号下面的左右子树没有,就直接蹦到后面去了,这不是完全二叉树,错误! |
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。