“树的基本性质”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
第28行： 第28行：
 
=== 3）二叉树的特性 ===
 
=== 3）二叉树的特性 ===
 
1）在二叉树的第 i 层上最多有2<sup>i-1</sup>个结点（i≥1）；
 
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）；
 
2）深度为k的二叉树最多有2<sup>k-1</sup>个结点（k≥1）；

2022年9月19日 (一) 02:15的版本

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

1）树的基本概念

树的基本概念.png

父结点：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。

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

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


2）二叉树的划分

二叉树的划分.png

满二叉树：每一层都不能再添加结点，都是满了的状态的二叉树

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


3）二叉树的特性

1）在二叉树的第 i 层上最多有2i-1个结点（i≥1）；

完全二叉树.png
层数 1 2 3 4 5 ...
结点数 1 2 4 8 16 ...
比 1:2
1:2
1:2
1:2

层与层之间的结点数是等比数列

2）深度为k的二叉树最多有2k-1个结点（k≥1）；

3）叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。

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

如果 i = 1，则结点 i 无父结点，是二叉树的根；如果i>1，则父结点是i/2；

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

如果2i+1

取自“https://www.jihongchang.top/index.php?title=树的基本性质&oldid=2073”