二叉树的特点总结

非空二叉树的特点：

1、每一层的结点个数: 最多是2^{i-1} （i>=1） 

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

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)

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容