二叉树-满二叉树、完全二叉树

二叉树-满二叉树、完全二叉树

引用

CSDN

1.

https://blog.csdn.net/qq_36944952/article/details/122194249

二叉树-满二叉树、完全二叉树

满二叉树

一棵高度为h，并且含有2^h - 1个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点。满二叉树的叶子节点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。（二叉树结点的度即为结点的孩子个数）

特点：

1. 只有最后一层有叶子结点。
2. 不存在度为1的结点。
3. 按层序从1开始编号，自上而下，自左向右。这样每个结点对应一个编号，对于编号为i的结点，如果有双亲，其双亲为⌊ i / 2 ⌋，如果有左孩子，则左孩子为2i，如果有右孩子，则有孩子为2i+1。

完全二叉树

设一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号为1...n的节点一一对应时，称为完全二叉树。

特点：

1. 只有最后两层可能有叶子结点。
2. 最多只有一个度为1的结点，且该节点只有左孩子没有右孩子。
3. 若i <= ⌊ n / 2 ⌋，则节点i为分支结点，否则为叶子节点。
4. 按层序编号之后，一旦出现某节点（其编号为i）为叶子结点或只有左孩子，那么编号大于i的节点均为叶子结点。
5. 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子没有右孩子，其余分支结点左右孩子都有。