前文
什么是二叉树？
在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒
二叉树的定义
- 任何一个节点的子节点数量都不超过 2
- 有左节点和右节点（不能随意颠倒）
左边树的左节点为 B，右节点为 C
右边数的左节点为 C，右节点为 B
满二叉树
什么是满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树
在上面那幅图的基础上加多一个节点，那么这棵树就变成满二叉树了
定义
- 所有叶子节点都在最后一层
- 节点的总数为： 2 的 n 次方 - 1（n 是树的高度）
这怎么理解呢？比如上面这幅图有三层，所以 n 就等于 3，那么 2 的 3 次方 - 1 就是 7个节点，那么说明这就是一颗完全二叉树
完全二叉树
什么是完全二叉树？
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从1至 n 的结点一一对应时称之为完全二叉树
这里为什么说不是完全二叉树？因为这图中最后一层左边并没有连续，直接从右边连续了，所以这并不是完全二叉树
通俗地来说完全二叉树的所有子节点都在最后一层或者倒数第二层，并且最后一层的叶子节点在左边连续（且左节点必须在前），倒数第二节点叶子节点在右边连续，依次按顺序能数完的才是完全二叉树
转载：https://blog.csdn.net/Woo_home/article/details/104693216
查看评论