树的基本概念

红太狼 2022-08-22 13:26 194阅读 0赞

特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）

**树结构和线性结构的比较**

线性结构

第一个数据元素（无前驱）

最后一个数据元素（无后继）

其它数据元素（一个前驱、一个后继）

树结构

根结点（无前驱）

多个叶子结点（无后继）

树中其它结点（一个前驱、多个后继）

**树的定义：**

由0个或多个(n>0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。

注：树的定义具有递归性，即树中还有树。

![20160529173132085][]

![20160529173157992][]

广义表表示法：

( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边

**基本操作：**

![20160529173223710][]

![20160529173241547][]

![20160529173304031][]

![20160529173330079][]

![20160529173346829][]

**树的逻辑结构**

(特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。

讨论1：树是非线性结构，该怎样存储？ ————仍然有顺序存储、链式存储等方式。

讨论2：树的顺序存储方案应该怎样制定？

可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。

讨论3：树的链式存储方案应该怎样制定？

可用多重链表：一个前趋指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。

解决思路：

先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。

**树的运算**

要明确：

1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。

2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。

[20160529173132085]: /images/20220722/4e862dd32ffc40c7b11492a4da2d5525.png
[20160529173157992]: /images/20220722/e2a25e76cbd54dae9b8bf9f9eb367ec3.png
[20160529173223710]: /images/20220722/ed4e78c45fc8432c9928653ae38b95a5.png
[20160529173241547]: /images/20220722/919a012ec0d1479288632ab9bdde32b1.png
[20160529173304031]: /images/20220722/84e7fd8e818a47faad994c9033d7a0f4.png
[20160529173330079]: /images/20220722/0dd57d47b89743b39ef2a51d7dabbb07.png
[20160529173346829]: /images/20220722/3a130d3e5b4c478b95fc34559db4c64e.png