数据结构中的树基础知识讲解

蔚落 2022-12-29 14:23 149阅读 0赞

## 引言 ##

原文链接：[树的基本概念][Link 1] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

这篇文章讲的是树的基本概念，二叉树在下一篇文章中讲。

树这种数据结构在生活中很常见，比如公司的组织结构图、文件系统等。当有大量数据时，链表的线性访问速度是最慢的，因此树这种结构有着极其重要的地位。

## 1、树的定义 ##

线性结构属于一对一的结构，而树属于一对多的结构。

树是n(n>=0)个结点的有限集，n=0称为空树；并且在任意一颗非空树中：

*  有且仅有一个根结点
 *  当n>1时，又能分为m个(m>0)个子树

下图就不满足树的定义，因为子树间存在交叉。

![图片][93ceed134503512d2cdfee85909eef98.png]

## 2、结点 ##

**结点的一些概念：**

*  树的结点=1个数据元素+若干个指向子树的指针。
 *  结点的度：结点拥有的子树个数，度=0为叶子结点。除根结点外度!=0的结点为分支结点或内部结点。
 *  树的度：最大的结点的度。比如有三个结点，度分别为4,、5、6，那么树的度就是6。
 *  孩子结点：一个结点有多个孩子结点
 *  双亲结点：为什么不叫父或母？因为一个结点只有一个父结点，索性叫双亲结点。
 *  兄弟结点：即两个结点有同一双亲。
 *  祖先和子孙：这个就不解释了

结点的层次、堂兄弟(这个概念不怎么重要)如下图所示。最大层次称为树的深度（或高度）。

![图片][7c00711b2467b44ab39f7d14c593326b.png]

线性结构和树结构的区别：

![图片][3f94ce41d035720be0009c9984a18fb4.png]

## 3、树的存储结构 ##

前面已经了解了树和结点的一些基本概念，并且已经知道了树是一对多的结果，那么这种一对多如何在计算机中存储呢？有如下表示法：

*  双亲表示法
 *  孩子表示法
 *  孩子兄弟表示法

### **3.1、双亲表示法** ###

假设现在有这样一棵树，如下图所示。

![图片][cf9a876852fb8a64dbba09f90f49fbf6.png]

那么根据双亲表示法，可以用如下数据表示这棵树的逻辑关系。

<table style="width:584px;"> 
 <tbody> 
  <tr> 
   <th style="width:191px;">下标</th> 
   <th style="width:195px;">data</th> 
   <th style="width:195px;">parent</th> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>0</p> </td> 
   <td style="vertical-align:top;width:195px;">A&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">-1</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>1</p> </td> 
   <td style="vertical-align:top;width:195px;">B&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">0</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>2</p> </td> 
   <td style="vertical-align:top;width:195px;">C&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">0</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>3&nbsp;</p> </td> 
   <td style="vertical-align:top;width:195px;">D&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">1</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>4&nbsp;</p> </td> 
   <td style="vertical-align:top;width:195px;">E&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">2</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>5&nbsp;</p> </td> 
   <td style="vertical-align:top;width:195px;">F&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">2</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>6&nbsp;</p> </td> 
   <td style="vertical-align:top;width:195px;">G&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">3</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>7&nbsp;</p> </td> 
   <td style="vertical-align:top;width:195px;">H&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">3</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;"> <p>8&nbsp;</p> </td> 
   <td style="vertical-align:top;width:195px;">I&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">3</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:191px;">9&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">J&nbsp;</td> 
   <td style="vertical-align:top;width:195px;">4</td> 
  </tr> 
 </tbody> 
</table>

该表可以采用顺序存储结构，每一行对应一个结点，该结点存储两部分内容：结点值和双亲结点指针。

这种存储方式很容易找到某一结点的双亲结点，其时间复杂度为O(1)，但是要找某一结点的所有孩子结点，必须要遍历整个表才行！

### **3.2、孩子表示法** ###

即每个结点存储结点的数据和指向孩子的指针。

但是每个结点的度是不同的，那么孩子指针设置多少个合适呢？有以下几种方案：

*  统一设成最大值，即树的度，但这样会造成空间浪费，特别是树中的结点的度差别很大的时候。
 *  孩子指针个数等于结点的度，但需要一个额外位置来存储该结点的孩子指针个数，但这种方案虽然避免了空间浪费，但需要额外维护一个数值。

上述两种方案都有缺点，根本原因在于每个结点的孩子指针是固定的，那将孩子指针设计成动态扩展的不就行了，因此可以采用数组+链表的设计方式，如下图所示。

![图片][01ffdd80083773d48582f67d7befd192.png]

当有n个结点时，数组的长度为n，并且每个数组元素都延伸了一条单向链表来存储它的孩子。

但是这种结构需要遍历整棵树才能知道某个结点的双亲，因此可以在每个数组元素中存储该结点的双亲，如下图所示。

![图片][b92e4a61a9c954347f2262d2f100815d.png]

### **3.3、孩子-兄弟表示法** ###

前面两种表示法的思路是：要么存储结点的孩子，要么存储结点的双亲。而孩子-兄弟表示法，则存储的是结点的第一个孩子和结点右边的兄弟。

如果想查找某个结点的所有孩子，则首先可以迅速查找它的第一个孩子，然后根据第一个孩子，可以找到这个孩子右边的兄弟，依次类推，就可以找到该结点所有的孩子。

但是，如果想找到某个结点的双亲呢？如果有必要的话，可以对某个结点增加一个parent指针。

孩子-兄弟表示法如下图所示。

![图片][eaba3fec029037001ded449dc9cafdf1.png]

这种表示法有一个好处就是，因为每个结点除了数据之外，只存储孩子和兄弟两个指针，因此很容易将上图转化为一颗二叉树，如下图所示。即使是再复杂的树也能转化为二叉树。这样就可以利用二叉树的特性和算法来处理这棵树了。

![图片][ea4a397f6166dba275d933d28ead02be.png]

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&tempkey=MTA5Ml9wejhES0NjYXdQdlF4cGtoNVRPdWZWbzk3T3AxSUJlOHpzbnZmTVR4WDlNbVk4TDJnczN0UHBMUjZYdjMyOHpSUERrMTVsMkdGd1BSb1VScHRWZ3VtTFZNbk1hNDZOM050MWV2TlpFNi1sNXl3OWFCNDNOczNTd1BlWUppR1hmdmlFc2VjazdHb3YzMzkzeTBoN2JfMnB0OTlySnpqMW1pWEd2WWNBfn4%3D&chksm=6a307a3a5d47f32c9d4cff448a5ba2ce6b30a734b11b93989054b77525cd697aed763def2d42&__mpa_temp_link_flag=1&token=869464904#rd
[93ceed134503512d2cdfee85909eef98.png]: /images/20221120/407bb81f9699400380a24aaacb790c7e.png
[7c00711b2467b44ab39f7d14c593326b.png]: /images/20221120/2a60dfc5b8e84cfc8fa6baf391be527b.png
[3f94ce41d035720be0009c9984a18fb4.png]: /images/20221120/aba01ee9c5914370a01f68b1204b59dd.png
[cf9a876852fb8a64dbba09f90f49fbf6.png]: /images/20221120/bd4cac44651f4163bbcd4e3203e78ec5.png
[01ffdd80083773d48582f67d7befd192.png]: /images/20221120/d3c800f14f1b49919401d4d9d8f30fee.png
[b92e4a61a9c954347f2262d2f100815d.png]: /images/20221120/2bf566977ee34d6d9d60ac552ba08d76.png
[eaba3fec029037001ded449dc9cafdf1.png]: /images/20221120/01058f80d6574b8eb359a81e6a47032f.png
[ea4a397f6166dba275d933d28ead02be.png]: /images/20221120/65df0b580065485ca8198347f98a227f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201222130032214.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM=,size_16,color_FFFFFF,t_70