二叉树

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

满二叉树

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

特点：

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

完全二叉树

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

特点：

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

二叉树

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

满二叉树

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

特点：

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

完全二叉树

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

特点：

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