查看“树的基本性质”的源代码

https://www.bilibili.com/video/BV1hg411V7Bm?p=59

=== 1）树的基本概念 ===
[[文件:树的基本概念.png|无|缩略图|600x600像素]]
父结点：1是2、3的父结点，2是4、5的父结点，3是6的父结点，6是7、8的父结点

子结点：2、3是1的子结点，4、5是2的子结点，6是3的子结点，7、8是6的子结点

兄弟结点：有同一个父结点的结点互为兄弟结点。4、5互为兄弟结点，7、8互为兄弟结点，2、3互为兄弟结点

叶子结点：没有子结点的结点。4、5、7、8是叶子结点。

结点的度：结点有几个子结点。6的度是2（7、8），2的度是2（4、5），1的度是2（2、3），3的度是1（6）

树的度：树的所有结点中度最大的结点的度就是树的度。这棵树度最大的结点（1、2、6）的度是2，所以这个树的度就是2。

'''<big>如果树的度不超过2，那么就是二叉树，换一种说法：每一个结点最多有2个子结点，就是二叉树</big>'''

层（深度、高度）：如图，这个树的高度是4。


=== 2）二叉树的划分 ===
[[文件:二叉树的划分.png|无|缩略图|900x900像素]]满二叉树：每一层都不能再添加结点，都是满了的状态的二叉树

完全二叉树：除最后一层（此图是4、5那一层）外都是满结点的状态，最后一层有缺失且左到右连续有，右到左连续无的二叉树（第一行图2和图3都是完全二叉树）


=== 3）二叉树的特性 ===

==== 1）在二叉树的第 i 层上最多有2<sup>i-1</sup>个结点（i≥1）； ====
[[文件:完全二叉树.png|无|缩略图|600x600像素]]
{| class="wikitable"
!层数
|1
|2
|3
|4
|5
|...
|-
|结点数
|1
|2
|4
|8
|16
|...
|-
! rowspan="4" |比
! colspan="2" |1:2
|
|
|
|
|-
|
! colspan="2" |1:2
|
|
|
|-
|
|
! colspan="2" |1:2
|
|
|-
|
|
|
! colspan="2" |1:2
|
|}
层与层之间的结点数是等比数列



==== 2）深度为k的二叉树最多有2<sup>k-1</sup>个结点（k≥1）； ====
等比数列求和公式



==== 3）叶子结点数为n<sub>0</sub>，度为2的结点数为n<sub>2</sub>，则n<sub>0</sub>=n<sub>2</sub>+1。 ====
每增加有一个度为2的结点，叶子结点就+1



==== 4）如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到 log<sub>2</sub>n+1 层，每层从左到右），则对任一结点 i (1≤i≤n)，有： ====

* 如果 i = 1，则结点 i 无父结点，是二叉树的根；如果i>1，则父结点是⌊i/2⌋（“⌊⌋”是向下取整符号）；

解释：'''<big>对于一个父结点，它编号为i的话，那么它左子结点的编号是2i，右子节点的编号是2i+1</big>'''

* 如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i;

解释：n是完全二叉树的总结点数，2i>n，那么i一定是完全二叉树最后一层结点的编号，最后一层结点就没有子结点，是叶子结点；

* 如果2i+1>n，则结点i无右子结点，否则，其右子结点的编号是2i+1。


提问：一个二叉树如果共有65个结点，问至少有多少层？最多有多少层？

求“至少有多少层”那就是满二叉树，2<sup>k</sup>-1>=65，7层；

求“最多有多少层”那就是一层一个结点，最多65层；


=== 考点1：结点编号关系 ===
对下图所示的二叉树进行顺序存储（根结点编号为1，对于编号为i的结点，其左孩子结点为2i，右孩子结点为2i+1）并用一维数组BT来表示。

已知结点X、E和D在数组BT中的下标为1、2、3，可推出结点G、K和H在数组BT中的下标分别为（）。
[[文件:考点1 结点编号关系.png|无|缩略图|239x239像素]]
A、10、11、12

B、12、24、25

C、11、12、13

D、11、22、23  √

解：

求G，G是F的右孩子结点，就有G=2F+1;F是E的右孩子结点，就有F=2E+1，E在数组BT中的下标为2，则F=2×2+1=5，G=2×5+1=11；

求K，K是G的左孩子结点，则K=2G，G=11，K=2×11=22

求H，H是G右孩子结点，则H=2G+1，G=11，H=2×11+1=23。



=== 考点2：层数的判断 ===
完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度（即层数）为（）。

A、3

B、4

C、5  √

D、6

解：
{| class="wikitable"
!层
|1
|2
|3
|4
|5
|-
!结点数
|1
|3
|7
|15
|31
|}
或者根据“若完全二叉树的层数为k，则最大结点数为2<sup>k</sup>-1”推，

假设4层，则结点数最多为2<sup>4</sup>-1=16-1=15，不足25个结点

假设5层，则结点数最多为2<sup>5</sup>-1=32-1=31，31≥25