《Java数据结构》这些树和二叉树的性质你还记得吗？

ゞ浴缸里的玫瑰 2024-04-23 15:39 5阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> 📒博客首页：[是小鱼儿哈][Link 1]
> 
> 🔥系列专栏：[Java数据结构][Java]
> 
> 🌻每日一句**：对轻易得到的东西需要心存戒心，真正有价值的东西都是需要付出代价的**
> 
> 💖博主也在学习阶段，如发现问题请告知，非常感谢💖

**目录**

一、树

树的概念

树的结点分类

结点之间的关系

树的存储结构

其他相关概念

二、 二叉树

📝二叉树的概念

📝特殊的二叉树

📝二叉树的性质

--------------------

## 一、树 ##

### 树的概念 ###

🍑这是现实世界的树

![f3ff9127a47fa54bd9768be456af283e.png][]

🍑**而我们这里所说的树，其实是一直特殊的数据结构**

之前我们学习的不管是顺序表还是链表、队列、栈，都是一对一的线性结构。但在数据生活中还有很多一对多的情况，所有我们就要用到这种一对多的数据结构——树

![66a4212588d94fa49a014d55464088ed.png][]

> 📝**树(Tree)是n（n≥0）个结点的有限集。n=0时称为空树。 在任意一颗非空树中**：  
> （1）有且仅有一个特定的**称为根（root）的结点**  
> （2）当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集 T 1 , T 2 , . . . , T m ，
> 
> **其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)**

有两个点需要注意一下：

1.  树是递归定义的——也就是说树的定义之中还用到了树的定义
2.  树形结构中，子树之间不能有交集，否则就不是树形结构

下面来解释一下这两点：

**🌰比如这是一个树**

![02cb06ce7f48474286eba2b905783ac5.png][]

下图的子树T1和T2就是根结点A的子树。当然，D,G,H,I组成的树又是B为结点的子树，E、J组成的树是C为结点的树的子树。

![5c7cf2239aef4f299e3c2b4e34cef9a2.png][]

**🌰一些非树的例子**

![81c983691b73427ebc17845dee53eaf2.png][]

上面三个就不是树结构，只有右下角的那个称为树型结构

--------------------

### 树的结点分类 ###

📝树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree） 。

📝度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

**🌰如下图，因为这棵树结点的度的最大值是结点D的度，为3，所以树的度为3.**  
![f57b39dce516474f84ed8387c9c0efb8.png][]

--------------------

### 结点之间的关系 ###

1.  **双亲节点或父节点：**若一个节点含有子节点，则这个节点称为其子节点的父节点
2.  **孩子结点或子结点：**一个结点含有的子树的根结点称为该结点的子结点
3.  **兄弟节点：**具有相同父节点的节点互称为兄弟节点

![9fa243cdfeaa4ac9bbe211e76be34763.png][]

**节点的祖先：**从根到该节点所经分支上的所有节点，如上图对于结点H来说，D、B、A都是他的祖先

**子孙：**以某节点为根的子树中任一节点都称为该节点的子孙。如上图：B的子孙有D、G、H、I

--------------------

### 树的存储结构 ###

📝树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：**双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法**等等。我们这里就简单的了解其中最常用的**孩子兄弟表示法**。（关于其他几种表示法，大话数据结构这本书里有详细的介绍）

![f5fff89a071642c9b5e06d4296d56866.png][]

> 我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的。因此，我们**设置两个结点引用，分别指向该结点的第一个孩子和该结点的右兄弟**。

**结点结构如表所示：**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>date</td> 
   <td>fristchild</td> 
   <td>rightbrother</td> 
  </tr> 
 </tbody> 
</table>

>  **class TreeNode \{** 
> 
>  **int date; // 数据域**
> 
>  **TreeNode firstchild; // 该结点的第一个孩子**
> 
>  **TreeNode rightbrother; // 该结点的右兄弟**
> 
> **\}**

**那么下面的树：**

![1084ca5d66fb4bd28143fa320d64c579.png][]

**就可以表示成：**

![1b56674147364990b201d5540ea3b24f.png][]

这种表示其实就是把一棵复杂的树变成了一棵二叉树

![a389a150063b48dc8820be878a244738.png][]

至于二叉树是什么？这也是咱们接下来要重点聊的内容😁

--------------------

### 其他相关概念 ###

**📝结点的层次**：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推

📝**树的高度或深度：**树中节点的最大层次

📝**堂兄弟节点：**双亲在同一层的节点互为堂兄弟

![e9099e85fdfc4cb6a57738e8d06e8107.png][]

> 🌻**森林：**由m（m>0）棵互不相交的树的集合称为森林；
> 
>  **🌻有序树和无序树**：如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。
> 
> 在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。

## 二、 二叉树 ##

### 二叉树的概念 ###

🌻简单地理解，满足以下两个条件的树就是二叉树：

1.  本身是有序树；
2.  树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

🌰例如，图 1a) 就是一棵二叉树，而图 1b) 则不是。

![85050f6c09995384a4828327c87fac93.gif][]

再深入的理解就是：

> 📝 一棵二叉树是结点的一个有限集合，该集合：  
> **1. 或者为空  
> 2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成**

![7dd52066a2724b619cdda3d01321e19c.png][]

> 🍑 从上图可以看出：  
> **1. 二叉树不存在度大于2的结点  
> 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树**

注意：对于任意的二叉树都是由以下几种情况复合而成的：

![c890e8ffe2074a13b25fede7e153bac4.png][]

**🍑 自然界的二叉树：**

![2d1c04a2274d4554bf1bed137b911591.png][]

**🍑我们数据结构要研究的二叉树：**

![0a67fddc65b04e3984f92c0c5720fcb1.png][]

### 📝特殊的二叉树 ###

🍑如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树

![b0b72b1d1d92438db25ff5eecc8d4178.png][]

**🍑如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树**

![bbc9be3d459b43fd88c73d83747de031.png][]

> **如图 3a) 所示是一棵完全二叉树，图 3b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。**

其实完全二叉树类似这下面这种情况

![20bd0a29fef74a91983c049afd925444.png][]

>  **从中我们也可以发现一些规律，如果一个完全二叉树的某一个结点没有右子树，那么该结点一定没有左子树，有右子树就一定得有左子树。它从左到右一定是连续的，中间不能出现空的。**

🔔同时我们需要注意一个慢二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。

--------------------

### 二叉树的性质 ###

**性质一、**若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

我们来观察下面的图形

![25b250c25e634112b272795034c59975.png][]

经过归纳分析，我们很容易得出这个结论

**性质2：**若规定根节点的层数为1，则深度为k的二叉树的最大结点数是2^k - 1 .（深度为k意思就是有k层的二叉树）

我们前面已经知道，一棵非空二叉树的第i层上2^(i-1) 个结点，那么k层的二叉树的结点树不就是首项是1、公比是2的等比数列求和吗？

**性质3：**对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1

![e218f83c63eb48c1a6712f9da2b13ce7.png][]

📝对于二叉树来说，我们会发现（除了根节点）对于每一个结点来说，都有其对应父结点分支指向它，假设树中**分枝数为 B**，那么**总的结点数就是B+1**

> 设总结点数为**n**，度为0的结点（即叶子结点）个数为**n0、**度为1的结点个数为**n1**、度为2的结点个数为**n2**，那么就有**n = n0 + n1 + n2**
> 
> 同时分支数**B = n1 + 2 \* n2，B + 1 == n**
> 
> 所以就有**n0 = n2 + 1**

下面我们就用这个性质来做几道题目练练手

**🌰第一题**

![ce7e3cca1d7e447b8c8bad8eacf69823.png][]

该二叉树的结点数是奇数，而对于结点数是奇数的二叉树，像这样：

![8b5c52d97cbf4eb3830d26894cb1161e.png][]

**你会发现，该二叉树中度为1的结点数一个都没有，这不是偶然，你观察其他的的二叉树，会发现也有这样一个规律。**

而对于结点数是偶数的二叉树呢？

![419f6037d1f6445c8b3eb15988842bd7.png][]

**你会发现结点数为偶数的二叉树，有且仅有一个度为1的结点**

>   
> 那么这样我们就可以开始算了： 设叶子结点即——**度为0的结点数为n0，度为1的结点数为n1（n1 == 0)，度为2的结点数为n2（n2 = n0 -1)**

> 即**399 = n0 + n1 + n2 = 2\* n0 - 1 --->n0 = 200**

**🌰第二题**

![3b5f7e80bd7b4250948ce30939b56cbe.png][]

> 2n说明结点数是偶数个，度为1的结点个数为1，**2n** = n0 + n1 + n2 = **1 + n0 + (n0 - 1)**
> 
> **即n0 == n，叶子结点个数为n**

**🌰第三题**

![6df0ccded21a42868a89c0d498c1f2e8.png][]

**答案是：B**

**🌰第四题**

![893d2f4a5a2d4f22a6ce2c9718c13b46.png][]

对于这个题目就要用到我们的性质四了

**性质四：**具有**n**个结点的完全二叉树的深度k为 log2(n+1)上取整

**2^9 == 512，即log2(531 + 1) == 9.xx**，**向上取整即为10，所以答案就是B**

**性质五：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：**

> **1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点  
> 2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子  
> 3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子**
> 
> ![b7ce40ffe07a4bce9caf112bda6b4a70.png][]

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[Java]: https://blog.csdn.net/weixin_61061381/category_11782224.html
[f3ff9127a47fa54bd9768be456af283e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4398f485fbab4f438a0b1a457f7427aa.png
[66a4212588d94fa49a014d55464088ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5cd169ef4269479c871043c943a6bc5e.png
[02cb06ce7f48474286eba2b905783ac5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/36aa6436b9754f358232854c78efc20d.png
[5c7cf2239aef4f299e3c2b4e34cef9a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e23f349d8ed2426488e7d681eadbf7bc.png
[81c983691b73427ebc17845dee53eaf2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/945219f2c7fa4f70a5e6d6c2897a27b8.png
[f57b39dce516474f84ed8387c9c0efb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/051bd5d4ecb04c47b5e4100a8afbe716.png
[9fa243cdfeaa4ac9bbe211e76be34763.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/819480fbbf6f4e4997013bfcc71263eb.png
[f5fff89a071642c9b5e06d4296d56866.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5422f1e3d7614fb28547be3d4033a884.png
[1084ca5d66fb4bd28143fa320d64c579.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b42a2902cd31497c8db90fbebf612c50.png
[1b56674147364990b201d5540ea3b24f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6c8fb145354b4a40aad604a1ad5f0400.png
[a389a150063b48dc8820be878a244738.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/79e6cda760584006a8446ea3591d39e1.png
[e9099e85fdfc4cb6a57738e8d06e8107.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2bc95c70dabd4aceb909d9d61f655be0.png
[85050f6c09995384a4828327c87fac93.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c8a8fe16e4e24c358956be8c2c839180.gif
[7dd52066a2724b619cdda3d01321e19c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/61cdfe6418fd432d8c32f90e45a22455.png
[c890e8ffe2074a13b25fede7e153bac4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/dd1c7220465c4804b051a0d8d4fa7392.png
[2d1c04a2274d4554bf1bed137b911591.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b07b4504b26b408c8442413ae47445de.png
[0a67fddc65b04e3984f92c0c5720fcb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9dc72c2fd7ea4cf1b5b857b37623072f.png
[b0b72b1d1d92438db25ff5eecc8d4178.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/af2b87c8c4854a658319071e31689735.png
[bbc9be3d459b43fd88c73d83747de031.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5520629975754ed0a3518dbc6a06702f.png
[20bd0a29fef74a91983c049afd925444.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/dea682e6f2cc4121a06bd0857efa73a3.png
[25b250c25e634112b272795034c59975.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/03b688134fad43d886bc37414c889caf.png
[e218f83c63eb48c1a6712f9da2b13ce7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/1b8f8f26048943b6a2b4c1025a7e3a71.png
[ce7e3cca1d7e447b8c8bad8eacf69823.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9ebb41c2a4ca4fd5b2b5a36a98ab8c38.png
[8b5c52d97cbf4eb3830d26894cb1161e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c0b9744f85564793968256255c7ff986.png
[419f6037d1f6445c8b3eb15988842bd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c00b5fbc87524da9b6398b9b66e2a2aa.png
[3b5f7e80bd7b4250948ce30939b56cbe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6da636eb2de74af6808e2d312fa4966f.png
[6df0ccded21a42868a89c0d498c1f2e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/331a52b46f49471c9e4f34b2500d2eb7.png
[893d2f4a5a2d4f22a6ce2c9718c13b46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5ec474622a3440bc96a233acc05615de.png
[b7ce40ffe07a4bce9caf112bda6b4a70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/a71d7b6972804eb5b9e07cb4a6a11bf7.png