数据结构之二叉树的定义和性质

分手后的思念是犯贱 2022-05-31 09:17 232阅读 0赞

通过上一节讲解，我们知道通用树结构是采用**双亲孩子表示法模型**建立的。每个结点都有一个指向其双亲的指针，每个结点都有

若干个指向其孩子的指针。如下图：

![70][]

整体实现起来比较复杂，今天我们来讲一下另一种树结构模型：孩子兄弟表示法模型。每个结点都有一个指向其第一个孩子的指

针，每个结点都有一个指向其第一个右兄弟的指针。如下图：

![70 1][]

**孩子兄弟表示法:**每个结点包含一个数据指针和两个结点指针。

1. 数据指针：指向保存于树中的数据；

2. 孩子结点指针：指向第一个孩子；

3. 兄弟结点指针：指向第一个右兄弟。

如下图：

![70 2][]

**孩子兄弟表示法的特点：**

1.能够表示任意的树形结构；

2. 每个结点中有且仅有三个指针域，数据指针，孩子结点指针，兄弟结点指针；

3. 每个结点的结构简单，只有孩子结点指针和兄弟结点指针构成了“树杈”。

孩子兄弟表示法的本质是将通用树转化为二叉树，二叉树是最多只有两个孩子的树。

二叉树的定义：二叉树是由 n ( n ≥0 ) 个结点组成的有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树

和右子树的、互不相交的二叉树组成。

二叉树有如下不同的5中状态：空二叉树、仅有根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树以及左、右子树均

非空的二叉树。如下图：

![70 3][]

当然二叉树还有比较特殊的二叉树，比如满二叉树和完全二叉树。

满二叉树 (FullBinary Tree)：如果二叉树中所有分支结点的度数都为2，且叶子结点都在同一层次上（即一颗深度为k且有2k\-1个

结点的二叉树），则称这类二叉树为满二叉树。满二叉树的特点就是每一层的结点数都是最大节点数。

完全二叉树(Complete Binary Tree)：如果一棵具有n个结点的高度为k的二叉树，它的每一个结点都与高度为k的满二叉树中编

号为1—n的结点一一对应，则称这棵二叉树为完全二叉树。（从上到下从左到右编号）。

![70 4][]

完全二叉树的叶结点仅出现在最下面两层：

1.最下层的叶结点一定出现在左边；

2.倒数第二层的叶结点一定出现在右边。

完全二叉树中度为1的结点只有左孩子，同样结点数的二叉树，完全二叉树的高度最小。

上面我们总结了二叉树的定义，接下来我们说一说二叉树的性质。

**二叉树的深层性质：**

性质1： 在二叉树的第 i层最多有 **2i-1**个结点(i ≥ 1)。

• 第一层最多有 **21-1=1**个结点。

• 第二层最多有 **22-1=2**个结点。

• 第三层最多有 **23-1=4**个结点。

• **……**

性质2: 深度为 k的二叉树最多有 **2k\-1**个结点(k ≥ 0)。

• 如果有一层，最多有 **1=21\-1=1**个结点。

• 如果有两层，最多有 **1+2=22\-1=3** 个结点。

• 如果有三层，最多有 **1+2+4=23\-1=7** 个结点。

• **……**

性质3:对任何一棵二叉树，如果其叶结点有n0个，度为2的非叶结点有 n2个，则有 **n0＝n2＋1**。

证明：假设二叉树中度1的结点有 n1个且总结点为n个，则：**n=n0\+n1\+n2。**

假设二叉树中连接父结点与子结点间的边为 e条，则：**e=n1\+2n2 = n – 1。**

所以：**n0＝n2＋1。**

性质4：具有 n个结点的完全二叉树的高度为

[70]: /images/20220531/d29c194bf3ae4023961b12109c1b55fb.png
[70 1]: /images/20220531/0d1b70809fff48a9becb14af93fdb21d.png
[70 2]: /images/20220531/b90ba2bc2c4249b8be79de84035d167f.png
[70 3]: /images/20220531/22df8981c30541efb276b4de20738d47.png
[70 4]: /images/20220531/bbf8cc4b4a0541519cebeaae5cdbb5da.png

发表评论取消回复

表情：

评论列表（有 0 条评论，232人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】二叉树性质巩固

在学习完二叉树以后，我们需要通过一些选择题来验收自己的学习成果。本篇博客将通过一些经典选择题带你巩固二叉树的相关性质。

ゝ一纸荒年。/ 2024年04月26日 10:58/ 0 赞/ 87 阅读

相关数据结构--二叉树的性质

二叉树二叉树的性质性质1 性质2 性质3 性质4 性质5 二叉树的性质性质1

旧城等待，/ 2023年02月22日 10:43/ 0 赞/ 43 阅读

相关【数据结构】之二叉树的5个性质

文章目录二叉树性质1 二叉树性质2 二叉树性质3 二叉树性质4 二叉树性质5 二叉树性质1

拼搏现实的明天。/ 2023年02月19日 08:25/ 0 赞/ 23 阅读

相关数据结构——二叉树——特点及性质

数据结构——二叉树——特点及性质二叉树(Binary Tree）是n(n=0)个结点的有限集合，该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别

悠悠/ 2023年01月08日 12:27/ 0 赞/ 139 阅读

相关 “树”和“二叉树”的基本定义和性质

文章目录一、树 1.1 树的概念 1.2 基本术语 1.3 树的性质二、二叉树 2.1 二叉树的定义

- 日理万妓/ 2022年11月03日 05:43/ 0 赞/ 225 阅读

相关数据结构-二叉树的性质(三)

二叉树的一些性质： ①在二叉树的第i层上最多有2i-1个结点(i>=1) ②深度为k的二叉树最多有2k\-1个结点(k>=1) ③对于任何一棵二叉树T,如果其终端结点数

忘是亡心i/ 2022年09月29日 10:57/ 0 赞/ 232 阅读

相关《数据结构》—— 二叉树的定义、种类、性质与存储结构

二叉树一、二叉树的定义二、特殊的二叉树 2.1 满二叉树 2.2 完全二叉树

谁借莪１个温暖的怀抱￠/ 2022年09月12日 06:45/ 0 赞/ 207 阅读

相关数据结构之二叉树的定义和性质

通过上一节讲解，我们知道通用树结构是采用双亲孩子表示法模型建立的。每个结点都有一个指向其双亲的指针，每个结点都有若干个指向其孩子的指针。如下图： ![70][]

分手后的思念是犯贱/ 2022年05月31日 09:17/ 0 赞/ 233 阅读

相关数据结构之二叉树的定义

二叉树定义及其逻辑表示定义逻辑表示性质定义及其逻辑表示定义一个二叉树是一个有

冷不防/ 2022年02月12日 10:53/ 0 赞/ 346 阅读

相关数据结构(8) 树[二]（二叉树以及性质）

二叉树定义二叉树：是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

拼搏现实的明天。/ 2022年02月03日 06:55/ 0 赞/ 297 阅读