5.2.1.2 二叉树的性质

教材导航 · 第5章

原书定位

印刷页P131起,对应PDF第143页。下文为目视整理的知识提要;完整内容见原书对照。

非空二叉树有 n0=n2+1n_0=n_2+1;第 kk 层最多 2k−12^{k-1} 个结点,高 hh 最多 2h−12^h-1 个。

完全二叉树按层序从 1 编号:双亲为 ⌊i/2⌋\lfloor i/2\rfloor,左右孩子为 2i2i、2i+12i+1(不超过 nn 才存在),深度为 ⌊log⁡2i⌋+1\lfloor\log_2 i\rfloor+1。

h=⌊log⁡2n⌋+1=⌈log⁡2(n+1)⌉h=\lfloor\log_2 n\rfloor+1=\lceil\log_2(n+1)\rceil

最后一个分支结点为 ⌊n/2⌋\lfloor n/2\rfloor,叶结点数 ⌈n/2⌉\lceil n/2\rceil。度为 1 的结点至多一个,若存在只能有左孩子;nn 为偶数时恰有一个,nn 为奇数时没有。

对应练习

5.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P131,PDF第143页

原书对照,原书P132,PDF第144页