数据结构之树的定义及操作

Dear 丶 2022-05-30 20:30 287阅读 0赞

**树的定义**

树是一种非线性的数据结构  
树是由 n ( n ≥0 ) 个结点组成的有限集合  
如果 n = 0，称为空树（如下图a）；  
如果 n > 0，则：

1.有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；

2. 除根以外的其它结点划分为 m (m ≥0)0) 个互不相交的有限集合T0,T1,***…***,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。

![70][]

**树家族中的概念(基本术语)**:

树的**结点**包含一个数据及若干指向子树的分支，结点拥有的子树数称为**结点的度**。度为0的结点称为**叶结点**或**终端节点**，度不为0的结点称为**分支结点**或**非终端节点**。除根节点外，分支节点也称为内部节点。**树的度**定义为所有结点中的度的最大值。

![70 1][]

结点的直接后继（节点的子树的根）称为该结点的**孩子**，相应的，该结点称为孩子的**双亲**。结点的孩子的孩子的……称为该结点的**子孙。**相应的，该结点称为子孙的祖先，同一个双亲的孩子之间互称**兄弟。**

![70 2][]

**结点的层次：**根为第1层，根的孩子为第2层，……。双亲在同一层的结点互为**堂兄弟（如上图中的F和G）**。树中结点的最大层次称为树的**深度**或**高度。**

![70 3][]

如果树中结点的各子树从左向右是有次序的，子树间不能互换位置，则称该树为有序树，否则为无序树。

![70 4][]

**森林**是由 n ( n ≥0 ) 棵互不相交的树组成的集合。对于树中每个结点而言，其子树的集合即为森林。就逻辑结构而言，任何一棵树是一个二元组Tree = (root, F),其中，root是数据元素，称做树的根节点；F是m(m>=0)棵树的森林，F=（T1,T2,…Tm），其中Ti = (ri,Fi)称做根root的第i棵子树；当m≠0时，在树根和其子树森林之间存在下列关系：RF = \{<root,ri>|i = 1,2,…,m,m>0\}。这个定义将有助于得到森林和树与二叉树之间转换的递归定义。

![70 5][]

**树的一些常用操作**：

1. 创建树；

2. 销毁树；

3. 清空树；

4. 插入结点；

5. 删除结点；

6. 获取结点；

7. 获取根结点；

8. 获取树的结点数；

9. 获取树的高度；

10. 获取树的度。

树在程序中表现为一种特殊的数据类型。

树的操作在程序中的表现为一组函数。

![70 6][]

本节简单讲一下树的定义及操作方式，下一节将讲一下这些操作的C实现方式。

[70]: /images/20220531/3b300b966b544521abb97ea95fb8c603.png
[70 1]: /images/20220531/27d78c124eb54ebbb45ea04cec967487.png
[70 2]: /images/20220531/8821b0f6ccfa4715953006c3d542eb21.png
[70 3]: /images/20220531/73f93426ff1f445d87e0ef6237bea0e4.png
[70 4]: /images/20220531/7916e7cf542b4d4aaed784d863236a65.png
[70 5]: /images/20220531/1053a2602f0447fe952d79b896457dde.png
[70 6]: /images/20220531/1c8f87fffdb3422a96d32de634cce5f8.png