真二叉树是什么?是满二叉树嘛？真二叉树有什么特点？

发布网友 发布时间：2022-04-20 10:29

我来回答

共1个回答

热心网友 时间：2023-06-30 17:40

非空二叉树的特点：

1、每一层的结点个数: 最多是 （i>=1） 

2、高度是h的二叉树总结点个数：最多 

3、设度为0的结点个数是n0，度为2的结点个数是n2，则有 n0 = n2 + 1

n = n0 + n1 + n2

边数 = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1

n1 + 2*n2 = n0 + n1 + n2 -1

n0 = n2 + 1

1、真二叉树

定义：所有结点的度都是0或2的二叉树

2、满二叉树

定义：满足所有叶子结点都在最后一层的真二叉树叫满二叉树

性质：

a.同样高度的二叉树中，满二叉树的叶子结点数最多，总结点数也是最多的

b.满二叉树一定是真二叉树，真二叉树不一定是慢二叉树

c.高度为h(>=1)的满二叉树的第i层节点数是 2的(i-1)次方，总结点数是2的h次方-1

3、完全二叉树

定义1：叶子结点只会出现在最后2层，且最后一层的叶子结点靠左对齐

定义2：将满二叉树的叶子结点从右向左依次移除x个，得到完全二叉树

性质：

a.满二叉树一定是完全二叉树

b.完全二叉树度为1的结点，最多有一个，且一定是左子树

c. h = ceiling(log2n)