Skip to content
第4章

4.6 二叉树的性质 ​

第i层最多几个结点 ​

4.5节那棵二叉树,高度是3,有5个结点。图里还有两个虚线框空着。

第1层第2层第3层ABDCG
本节问题
高度不变,这棵树里最多还能放几个结点?

要回答它,先一层一层看,每层最多能放几个。二叉树的每个结点最多两个孩子,所以下一层最多是这一层的两倍:

第1层:1个。第1层只有根。

第1层A

第2层:2个。根最多两个孩子。

第1层第2层ABC

第3层:4个。第2层的B、C,各自最多两个孩子,2 × 2 = 4。

第1层第2层第3层ABDECFG

每往下一层,最多的个数翻一倍:1、2、4、8……第i层是i − 1个2相乘,写作2ⁱ⁻¹。

这是二叉树的第一个性质:第i层最多有2ⁱ⁻¹个结点。第3层最多2²,也就是4个。

选中正文里的任意文字,就可以针对它发表评论