Question

完全二叉树和满二叉树有什么区别

Answer 1

完全二叉树和满二叉树的区别：

1、含义不同

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

2、表示不同

对于满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的性质：

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。

性质2：深度为h的二叉树中至多含有2h-1个节点。

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0＝n2＋1。

性质4：具有n个节点的满二叉树深为log2n＋1。

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i＝1时，该节点为根，它无双亲节点。

当i＞1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i＋1≤n，则有编号为2i＋1的右节点，否则没有右节点。