数据结构（六）：树

客官°小女子只卖身不卖艺 2021-10-01 10:00 361阅读 0赞

## 树的定义 ##

**1. 树的定义**

*  树是 n ( n >= 0 ) 个结点的有限集，n = 0 时称为空树
 *  任意一棵非空树中，有且仅有一个根结点
 *  当 n > 1 时，其余结点分为 m（m > 0）个互不相交的有限集

![9434708-ad9198448cab961b.png][]

P6Z2d.png

**2. 结点概念**

*  结点：树的结点包含一个数据元素及若干个指向子树的分支
 *  结点的度：结点拥有的子树
 *  叶子结点：度为 0 的结点
 *  分支结点：度不为 0 的结点
 *  内部结点：除根结点以外，分支结点也称为内部结点
 *  树的度：树内各结点的度的最大值
 *  树的深度：树中结点最大层次称为树的深度

**3. 结点之间的关系**

*  结点的父结点称为双亲（Parent）
 *  同一个父结点的子结点之间称为兄弟结点（sibling）
 *  无序树和有序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该数为有序树，否则为无序树

**4. 树的抽象数据类型**

*  Data（数据元素）：树是由一个根结点和若干棵子树构成，树中结点具有相同的数据类型及层次关系
 *  基本操作

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">方法</th> 
   <th style="text-align:center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">InitTree(*T)</td> 
   <td style="text-align:center">构造空树 T</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">DestoryTree(*T)</td> 
   <td style="text-align:center">销毁树 T</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">ClearTree(*T，definition)</td> 
   <td style="text-align:center">按 definition 中给出的树定义来构造树</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">ClearTree(*T)</td> 
   <td style="text-align:center">若树 T 存在，则将树 T 清为空树</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">TreeEmpty(T)</td> 
   <td style="text-align:center">若 T 为空树返回 true，否则 false</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">TreeDepth(T)</td> 
   <td style="text-align:center">返回 T 的深度</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">Root(T)</td> 
   <td style="text-align:center">返回 T 的根结点</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">Value(T,cur_e)</td> 
   <td style="text-align:center">cur_e 是树 T 中一个结点，返回此结点的值</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">Assign(T,cur_e,value)</td> 
   <td style="text-align:center">给树 T 的结点 cure_e 赋值为 value</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">Parent（T,cur_e）</td> 
   <td style="text-align:center">若 cur_e 是树 T 的非根结点，则返回它的双亲，否则返回空</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">LeftChild(T,cur_e)</td> 
   <td style="text-align:center">若 cur_e 是树 T 的非叶结点，则返回它最左的子结点，否则返回空</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">RightSibling(T,cur_e)</td> 
   <td style="text-align:center">若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">InsertChild(<em>T,</em>p,i,c)</td> 
   <td style="text-align:center">其中 p 指向树 T 的某个结点，i 为所指结点 p 的度加上 1，非空树 c 与 T 不想交，操作结果为插入 c 为 树 T 中 p 指结点的第 i 棵子树</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">DeleteChild(<em>T,</em>p,i)</td> 
   <td style="text-align:center">其中 p 指向树 T 的某个结点，i 为所指结点 p 的度，操作结果为删除 T 中 p 所指结点的第 i 棵子树</td> 
  </tr> 
 </tbody> 
</table>

## 树的顺序存储 ##

> **简单的顺序存储结构是不能满足树的实现要求的，需要充分利用顺序存储和链式存储结构的特点**，如何表示树与其子树之间的关系，主要有三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法

### 1.双亲表示法 ###

每个结点除了知道自己是谁以外，还要知道其双亲结点（Parent），通过结点的 parent 找到其父结点，时间复杂度为 O(1)，直到 parent 为 -1 时，表示找到了树的根，根结点没有双亲，所以根结点的位置域为 -1

#### 双亲表示法结构 ####

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">data（数据域）</th> 
   <th style="text-align:center">parent（指针域）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">存储结点的数据信息</td> 
   <td style="text-align:center">存储该结点的双亲所在数组中的下标</td> 
  </tr> 
 </tbody> 
</table>

![9434708-f57f4c6107a24e03.png][]

P6p1A.png

#### 双亲表示法的子结点与兄弟结点 ####

*  **要知道结点的子结点，可以增加一个长子域，它指向结点最左边的子结点**

![9434708-f732f1c94fcaa106.png][]

[长子域][Link 1]

*  **要知道结点的兄弟结点，可以增加一个右兄弟域，它指向某子结点右边的结点，若右兄弟不存在，则赋值为 -1**

![9434708-b8ae21c1d2521a75.png][]

[兄弟域][Link 2]

### 2.孩子表示法 ###

把每个结点的子结点排列起来，以单链表作为存储结构，n 个结点有 n 个子结点链表，如果是叶子结点则此单链表为空，然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中

#### 孩子表示法结构 ####

*  子结点链表的子结点

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">child（数据域）</th> 
   <th style="text-align:center">next（指针域）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">存储某个结点在表头数组中的下标</td> 
   <td style="text-align:center">存储指向某结点的下一个孩子结点的指针</td> 
  </tr> 
 </tbody> 
</table>

*  表头数组的表头结点

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">data（数据域）</th> 
   <th style="text-align:center">firstchild（头指针域）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">存储某个结点的数据信息</td> 
   <td style="text-align:center">存储该结点的孩子链表的头指针</td> 
  </tr> 
 </tbody> 
</table>

![3738156-0e3083ea5c66492c.png][]

### 3.孩子兄弟表示法 ###

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此我们设置两个指针，分别指向该结点的第一个子结点和此结点的右兄弟

#### 孩子兄弟表示法结构 ####

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">data（数据域）</th> 
   <th style="text-align:center">firstchild（指针域）</th> 
   <th style="text-align:center">rightchild（指针域）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">存储结点的数据信息</td> 
   <td style="text-align:center">存储该结点的第一个孩子的存储地址</td> 
   <td style="text-align:center">存储该结点的右兄弟结点的存储地址</td> 
  </tr> 
 </tbody> 
</table>

![9434708-cd7a712e76398e99.png][]

PlWM9.png

[9434708-ad9198448cab961b.png]: /images/20210811/5d3a1582957d466f9d2230d591250394.png
[9434708-f57f4c6107a24e03.png]: /images/20210811/3dc1198d28084de996cac55c52bb3ee9.png
[9434708-f732f1c94fcaa106.png]: /images/20210811/0cb8fe1151504919b1676b55fa9a73f8.png
[Link 1]: https://link.jianshu.com?t=https%3A%2F%2Fsimimg.com%2Fi%2FPtCWz
[9434708-b8ae21c1d2521a75.png]: /images/20210811/5d7e392efe4d46448e4b766229c89522.png
[Link 2]: https://link.jianshu.com?t=https%3A%2F%2Fsimimg.com%2Fi%2FPtcna
[3738156-0e3083ea5c66492c.png]: /images/20210811/fc305668b0514a40ae54accecb2f0321.png
[9434708-cd7a712e76398e99.png]: /images/20210811/ad585aaa80e249289e1af9479b3a1b9d.png