数据结构树之切腹攻略

柔光的暖阳◎ 2022-05-09 09:08 466阅读 0赞

![70][]

树 —— 一种一对多的数据结构。

**目录**

1. 树的相关术语

2. 树形结构的各种表示法

2.1 树形表示法

2.2 形式语言表示法

2.3 文氏图表示法

2.4 嵌套括号表示法

2.5 凹入表表示法

2.6 图书目录，杜威表示法

3. 森林

3.1 树转化成二叉树

3.2 二叉树转化成树

3.3 森林转化成二叉树

3.4 二叉树转化成森林

4. 森林的遍历

4.1 先根深度优先遍历森林 = 前序法遍历二叉树（根左右）

4.2 后根深度优先遍历森林 = 按中序法遍历对应的二叉树（左根右）

4.3 宽度（广度）优先遍历森林

5 树的链式存储结构

5.1 “子结点表”表示方法

5.2 静态“左孩子/右兄弟”表示法

5.3 动态表示法

5.4 动态“左孩子/右兄弟”表示法

5.5 父指针表示法（应用于并查集）

6 并查集

6.1 等价关系

（1）定义

（2）例子

6.2 等价类(equivalence classes)

（1）定义

（2）用树来表示等价类的并查

6.3 路径压缩

7 树的顺序存储结构

7.1 带右链的先根次序表示（Stack）

7.2 带双标记的先根次序表示（Stack）

7.3 带双标记的层次次序表示（Queue）

7.4 带度数的后根次序表示（Stack）

8 K叉树

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

# 1. 树的相关术语 #

![70 1][]

![70 2][]

下面引入术语的专业解析（觉得烦死人的，可以略过）

<table> 
 <thead> 
 <tr> 
 <th>Root</th> 
 <th>The top node in a tree.</th> 
 <th>根</th> 
 <th>树的顶端结点</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>Child</td> 
 <td>A node directly connected to another node when moving away from the Root.</td> 
 <td>孩子</td> 
 <td>当远离根(Root)的时候，直接连接到另外一个结点的结点被称之为孩子(Child);</td> 
 </tr> 
 <tr> 
 <td>Parent</td> 
 <td>The converse notion of a child.</td> 
 <td>双亲</td> 
 <td>相应地，另外一个结点称为孩子(child)的双亲(parent)。</td> 
 </tr> 
 <tr> 
 <td>Siblings</td> 
 <td>A group of nodes with the same parent.</td> 
 <td>兄弟</td> 
 <td>具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。</td> 
 </tr> 
 <tr> 
 <td>Ancestor</td> 
 <td>A node reachable by repeated proceeding from child to parent.</td> 
 <td>祖先</td> 
 <td>结点的祖先(Ancestor)是从根（Root）到该结点所经分支(Branch)上的所有结点。</td> 
 </tr> 
 <tr> 
 <td>Descendant</td> 
 <td>A node reachable by repeated proceeding from parent to child.</td> 
 <td>子孙</td> 
 <td>反之，以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor)。</td> 
 </tr> 
 <tr> 
 <td>Leaf</td> 
 <td>A node with no children.</td> 
 <td>叶子（终端结点）</td> 
 <td>没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。</td> 
 </tr> 
 <tr> 
 <td>Branch</td> 
 <td>A node with at least one child.</td> 
 <td>分支(非终端结点)</td> 
 <td>至少有一个孩子的结点称为分支(Branch)或非终端结点。</td> 
 </tr> 
 <tr> 
 <td>Degree</td> 
 <td>The number of sub trees of a node.</td> 
 <td>度</td> 
 <td>结点所拥有的子树个数称为结点的度(Degree)。</td> 
 </tr> 
 <tr> 
 <td>Edge</td> 
 <td>The connection between one node and another.</td> 
 <td>边</td> 
 <td>一个结点和另一个结点之间的连接被称之为边(Edge)。</td> 
 </tr> 
 <tr> 
 <td>Path</td> 
 <td>A sequence of nodes and edges connecting a node with a descendant.</td> 
 <td>路径</td> 
 <td>连接结点和其后代的结点之间的(结点,边)的序列。</td> 
 </tr> 
 <tr> 
 <td>Level</td> 
 <td>The level of a node is defined by ０ + (the number of connections between the node and the root).</td> 
 <td>层次</td> 
 <td>结点的层次(Level)从根(Root)开始定义起，根为第0层，根的孩子为第1层。以此类推，若某结点在第i层，那么其子树的根就在第i+1层。</td> 
 </tr> 
 <tr> 
 <td>Height of node</td> 
 <td>The height of a node is the number of edges on the longest path between that node and a leaf.</td> 
 <td>结点的高度</td> 
 <td>结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。</td> 
 </tr> 
 <tr> 
 <td>Depth of node</td> 
 <td>The depth of a node is the number of edges from the tree’s root node to the node.</td> 
 <td>结点的深度</td> 
 <td>结点的深度是从树的根结点到该结点的边的个数。 （注：树的深度指的是树中结点的最大层次。）</td> 
 </tr> 
 <tr> 
 <td>Forest</td> 
 <td>A forest is a set of n ≥ 0 disjoint trees.</td> 
 <td>森林</td> 
 <td>森林是n(&gt;=0)棵互不相交的树的集合。</td> 
 </tr> 
 </tbody> 
</table>

# 2. 树形结构的各种表示法 #

## 2.1 树形表示法 ##

## ![70 3][] ##

## 2.2 形式语言表示法 ##

![70 3][]

## ![70 4][] ##

## 2.3 文氏图表示法 ##

## ![70 5][] ##

## 2.4 嵌套括号表示法 ##

## ![70 6][] ##

## 2.5 凹入表表示法 ##

## ![70 7][] ##

## 2.6 图书目录，杜威表示法 ##

![70 8][]

# 3. 森林 #

![70 9][]

> **森林(forest)**：零棵或多棵不相交的树的集合（通常是有序）  
> **树与森林的对应**  
> （1）一棵树，删除树根，其子树就组成了森林  
> （2）加入一个结点作为根，森林就转化成了一棵树

## 3.1 树转化成二叉树 ##

## ![70 10][] ##

## 3.2 二叉树转化成树 ##

![70 11][]

## 3.3 森林转化成二叉树 ##

## ![70 12][] ##

## 3.4 二叉树转化成森林 ##

## ![70 13][] ##

# 4. 森林的遍历 #

![70 14][]

## 4.1 先根深度优先遍历森林 = 前序法遍历二叉树（根左右） ##

**先根序列 A B C K D E H F J G**

## ![70 15][] ##

## 4.2 后根深度优先遍历森林 = 按中序法遍历对应的二叉树（左根右） ##

**后根序列 B K C A H E J F G D**

![70 16][]

## 4.3 宽度（广度）优先遍历森林 ##

## ![70 17][] ##

## ![70 18][] ##

森林广度优先：A D B C E F G K H J

二叉树根据二叉链存储结构的右斜线（优先访问右子树）

![70 19][]

# 5 树的链式存储结构 #

## 5.1 “子结点表”表示方法 ##

list of children,就是图的邻接表

![70 20][]

## ![70 21][]   5.2 静态“左孩子/右兄弟”表示法 ##

## ![70 22][]   5.3 动态表示法 ##

每个结点分配可变的存储空间

\- 子节点数目发生变化，需要重新分配存储空间

## ![70 23][]   5.4 动态“左孩子/右兄弟”表示法 ##

## ![70 24][]   5.5 父指针表示法（应用于并查集） ##

**父指针(parent pointer)表示法**：只需要保存一个指向其父结点的指针域

![70 25][]

**涉及算法:**

![70 26][]

# 6 并查集 #

**并查集：**一种特殊的集合，由一些不相交子集构成。

——Find：查询结点所在集合

——Union：归并两个集合

## **6.1 等价关系** ##

### **（1）定义** ###

设 R 是集合 A 上的一个二元关系，若R满足：

自反性：∀ a ∈A, => (a, a) ∈ R

对称性：(a, b) ∈R∧ a ≠ b => (b, a)∈R

传递性：(a, b)∈R,(b, c)∈R =>(a, c)∈R

则称R是定义在A上的一个等价关系。设R是一个等价关系，若(a, b) ∈ R，则称a等价于b，记作 a ~ b

### **（2）例子** ###

同班同学关系、同乡关系是等价关系。

平面几何中三角形间的相似关系、全等关系都是等价关系。

平面几何中直线间的平行关系是等价关系。

## **6.2 等价类(equivalence classes)** ##

### **（1）定义** ###

**等价类：**相互等价的元素所组成的最大集合。

江湖上散落着各式各样的大侠，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？

![70 27][]

我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物。这样，每个圈子就可以这样命名“华山派”，“峨眉派”等，两人只要互相比对一下自己的队长是不是同一个人，就可以确定敌友关系了。

但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”想打一架得先问个几十年，饿都饿死了。这样不仅效率低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否是一个帮派的，至于他们是如何通过朋友关系相关联的，以及每个圈子内部的结构是怎样的，甚至队长是谁，都不重要了。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。

（参考自：超有爱的并查集~[超有爱的并查集~][Link 1]）

### **（2）**用树来表示等价类的并查 ###

![70 28][]

**UNION/FIND算法示例****（门派合并）**

**（1）**

![70 29][]

**（2）**

![70 30][]

**（3）**

F的父节点为D，再依据**加权合并规则**，以F为根的树结点个数少，故将F指向D。

![70 31][]

## 6.3 路径压缩 ##

查找时最理想的情况就是所有人的直接上级都是掌门，一共就两级结构，只要找一次就找到掌门了。哪怕不能完全做到，也最好尽量接近。这样就产生了路径压缩算法。

![70 32][]

两个互不相识的大侠碰面了，想知道能不能干一场。 于是赶紧打电话问自己的上级：“你是不是掌门？” 上级说：“我不是呀，我的上级是谁谁谁，你问问他看看。” 一路问下去，原来两人的最终boss都是东厂曹公公。 “哎呀呀，原来是自己人，有礼有礼，在下三营六组白面葫芦娃!” “幸会幸会，在下九营十八组仙子狗尾巴花！” 两人高高兴兴地手拉手喝酒去了。 “等等等等，两位大侠请留步，还有事情没完成呢！”我叫住他俩。 “哦，对了，还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长：“组长啊，我查过了，其实偶们的掌门是曹公公。不如偶们一起结拜在曹公公手下吧，省得级别太低，以后查找掌门麻烦。” “唔，有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样，查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理，所以整个门派树的层数都会维持在比较低的水平上。

![70 33][]

# 7 树的顺序存储结构 #

## 7.1 带右链的先根次序表示（Stack） ##

结点按先根次序顺序存储在一片连续的存储单元中

## ![70 34][] ##

## ![70 35][]   7.2 带双标记的先根次序表示（Stack） ##

结点按先根次序顺序存储在一片连续的存储单元中

## ![70 36][] ##

**有0无1**

![70 37][]

## 7.3 带双标记的层次次序表示（Queue） ##

结点按层次次序顺序存储在一片连续的存储单元中

![70 38][]

## 7.4 带度数的后根次序表示（Stack） ##

结点按后根次序顺序存储在一片连续的存储单元中

![70 39][]

![70 40][]

# 8 K叉树 #

**K叉树：**每个父节点最多有K个子节点。

二叉树的许多性质可以推广到 K 叉树

![70 41][]

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

话说，这篇文章跟切腹有啥关系？当然是木有。

![70 42][]

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

本文主要参考自

张铭《数据结构与算法》

程杰《大话数据结构》

《超有爱并查集~》

[70]: /images/20220509/0ab240922e77455eae16aa2fbca418c8.png
[70 1]: /images/20220509/791daeb5b46a43d2abf9fe10179b9495.png
[70 2]: /images/20220509/7b6f16b5c48346ce8d438209ca5af515.png
[70 3]: /images/20220509/b8b3ba6841644c8aacdd2dab6a63b3f3.png
[70 4]: /images/20220509/e6f05e7e149e47aea74c753ec1cfc119.png
[70 5]: /images/20220509/a9e17afb9cf747aab759d26166389990.png
[70 6]: /images/20220509/0488c46cd9b84d58820d6141dd9900b3.png
[70 7]: /images/20220509/875bde20204144fa9d02228d003a70e8.png
[70 8]: /images/20220509/8647245bba824848bc966060f18806c8.png
[70 9]: /images/20220509/e6b27463eec14177b3247b65875c7af6.png
[70 10]: /images/20220509/bc86fa35da6b4e668cb8d90733eb4f74.png
[70 11]: /images/20220509/197029cedc77463ebfaf098511246cd2.png
[70 12]: /images/20220509/05a9a06c9ee945feb4b1ded1f9a7d414.png
[70 13]: /images/20220509/5597b2b4196546c7bd8f2e55d1f984a3.png
[70 14]: /images/20220509/2b9f166b9db6462badfeefce145f8c09.png
[70 15]: /images/20220509/a081d607c3144970a46d889d9293b652.png
[70 16]: /images/20220509/82b1bd14ed8943c682783436cd806be5.png
[70 17]: /images/20220509/e23b41cbecf748a2b3e1b2f32dd0d558.png
[70 18]: /images/20220509/e545a888f9314bab9eae91fbb736fa11.png
[70 19]: /images/20220509/ed157b5cd30e47f5b5a46428e6761556.png
[70 20]: /images/20220509/d73b901e17554b61ab5fbc72e1d76900.png
[70 21]: /images/20220509/f89b49589afb443a8c20f6894b12087b.png
[70 22]: /images/20220509/fc6195cbf46b47eba00f4973f35c6c46.png
[70 23]: /images/20220509/542367591d204283a8b1528303cd6dd7.png
[70 24]: /images/20220509/eeca70d19a8d4bf781747fcb906502ce.png
[70 25]: /images/20220509/8f8c5e906f124587b715e48727b91779.png
[70 26]: /images/20220509/e3cb00afb09d4612bd9ace417b70abc4.png
[70 27]: /images/20220509/82f852a21bbe409e9a36c6f84d47cf86.png
[Link 1]: https://blog.csdn.net/niushuai666/article/details/6662911
[70 28]: /images/20220509/54ce02b84b1343f3bfdfd155fe20b10c.png
[70 29]: /images/20220509/e49174f1424d457ca39710f827358f7a.png
[70 30]: /images/20220509/00e22a24afc945d68d582ca8eb6cb5a6.png
[70 31]: /images/20220509/d8fe020a52ee440f87a9e3d2efec0b21.png
[70 32]: /images/20220509/b15d49c0bb764397801cd70398cab7bb.png
[70 33]: /images/20220509/7ff7881ec6b5457db0c961babb07ac4c.png
[70 34]: /images/20220509/467e58e12fbc4cd78181be0bdc28f19a.png
[70 35]: /images/20220509/0981363cf712404bb81d666d642f8303.png
[70 36]: /images/20220509/c1f1f07dbf864f40bd9547ad8103deca.png
[70 37]: /images/20220509/6ea8622c9be140fea1bc675ecfc182f3.png
[70 38]: /images/20220509/0bade64e27684dafa5b6d23a2caaf7b5.png
[70 39]: /images/20220509/4c595d37841241fdaead1d4f9e49aae1.png
[70 40]: /images/20220509/9f4a6ca5db214a2daa42920b641fff40.png
[70 41]: /images/20220509/a196aa837ae14d7d97f964c95cd5922c.png
[70 42]: /images/20220509/40edbcb92673494babdb770a5d90cabf.png