开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构7--树1 -> 正文阅读

[数据结构与算法]数据结构7--树1

笔记来源：懒猫老师.

树的逻辑结构

树的定义：

n (n≥0) 个结点的有限集合。当n=0时，称为空树，任意一棵非空树满足以下条件：

有且仅有一个特定的称为根的结点;
当 n > 1 时，除根结点之外的其余结点被分成 m （m>0）个互不相交的有限集合 T1, T2，…Tm，其中，每个集合又是一棵树，并称为这个根结点的子树。

树的定义采用递归方法

在这里插入图片描述

树的基本术语：

结点的度：结点所拥有的子树的个数。
树的度：树中各结点度的最大值。

在这里插入图片描述

叶子结点：度为 0 的结点，也称为终端结点。
分支结点：度不为 0 的结点，也称为非终端结点。

在这里插入图片描述

孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点
兄弟：具有同一个双亲的孩子结点互称为兄弟

在这里插入图片描述

路径：

在这里插入图片描述

祖先，子孙：在树中，如果有一条路径从结点 x 到结点 y ，则 x 称为 y 的祖先，而 y 称为 x 的子孙。
结点所在层数：根结点的层数为 1；对其余任何结点，若某结点在第 k 层，则其孩子结点在第 k+1 层。
树的深度：树中所有结点的最大层数，也称高度。

在这里插入图片描述

层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从 1 开始的连续自然数。

在这里插入图片描述

有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树;反之，称为无序树。

在这里插入图片描述

森林：m (m≥0) 棵互不相交的树的集合。

在这里插入图片描述

树结构和线性结构的比较
在这里插入图片描述

树的抽象数据类型定义：
在这里插入图片描述

树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。

在这里插入图片描述

前序遍历：（根结点最先被访问）

树的前序遍历操作定义为：

若树为空，则空操作返回;

否则：

访问根结点;
按照从左到右的顺序前序

遍历根结点的每一棵子树.

在这里插入图片描述

后序遍历：（根结点最后被访问）
树的后序遍历操作定义为：

若树为空，则空操作返回;

否则：

按照从左到右的顺序后序遍历根结点的每一棵子树;
访问根结点。

在这里插入图片描述

层序遍历：

从树的第一层 (即根结点) 开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

在这里插入图片描述

树的存储结构

双亲表示法

基本思想：用一维数组来存储树的各个结点(一般按层序存储) ，数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。

在这里插入图片描述

如何查找双亲结点？时间性能？

例如要查找 G ，它的双亲结点是 2 ， 2 下标对应的是 C 结点，则可以查到 G 的双亲是 C。时间复杂度为 O(1)。

如何查找孩子结点？时间性能？

例如查找结点 C 的孩子结点，C 对应的下标是 2，则需要使用循环，遍历整个数组才行，将序号为 2 的结点找到，复杂度为 O(n)。

改进查找孩子结点

在结构体中增加字段 firstChild，用来记录结点的第一个孩子，

在这里插入图片描述
对于 A 结点来说，它有两个孩子，最左边的是 B ，B 所对应的下标为 1 ，因此在 A 结点的 firstChild 这一栏置为 1 ；

对于结点 B ，它第一个孩子为 D，D 所对应的下标为 3，则 B 的 firstChild 处为 1。

但是此时只是记录了一个孩子，如何将所有的孩子全部记录？

如何查找兄弟结点？时间性能？

在这里插入图片描述
增加 rightSib(右同胞) 字段。例如，结点 B 的兄弟结点是 C ，C 对应的下标为 2 ，则 B 的 rightSib 为 2

孩子表示法

如何表示孩子？

链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。

方案 1：指针域的个数等于树的度

在这里插入图片描述
其中：

data：数据域，存放该结点的数据信息;
child1~childn：指针域，指向该结点的孩子。

在这里插入图片描述
缺点：浪费空间

方案 2：指针域的个数等于该结点的度

在这里插入图片描述

其中:

data：数据域，存放该结点的数据信息;
degree：度域，存放该结点的度;
child1~childn：指针域，指向该结点的孩子。

在这里插入图片描述

缺点：结点结构不一致

方法改进：

在这里插入图片描述

双亲孩子表示法

在这里插入图片描述

孩子兄弟表示法

在这里插入图片描述

data：数据域，存储该结点的数据信息;
firstChild：指针域，指向该结点第一个孩子;
rightSib：指针域，指向该结点的右兄弟结点。

在这里插入图片描述

二叉树的逻辑结构

二叉树的定义：

在这里插入图片描述

二叉树的特点：

每个结点最多有两棵子树；
二叉树是有序的，其次序不能任意颠倒

二叉树的基本形态：

在这里插入图片描述

具有三个结点的树和具有三个结点的二叉树的形态：
在这里插入图片描述
二叉树和树是两种树结构

特殊的二叉树：
1. 斜树：

所有的结点都只有左子树的二叉树称为左斜树
所有的结点都只有右子树的二叉树称为右斜树
左斜树和右斜树统称为斜树

斜树的特点：

在斜树中，每一层只有一个结点
斜树的结点的个数与其深度相同

2. 满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上

特点：
叶子结点只能出现在最下一层
只有度为 0 和度为 2 的结点

满二叉树在同样深度的二叉树中结点个数最多，满二叉树在同样深度的二叉树中叶子结点个数最多。

3. 完全二叉树

对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i (1 ≤ i ≤ n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同。

在这里插入图片描述

在满二叉树中，从最后一个结点开始，连续去掉任意一个结点，即是一棵完全二叉树

特点：

叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左面
完全二叉树中如果有度为 1 的结点，只可能有一个，且该结点只有左孩子。
深度为 k 的完全二叉树在 k-1 层上一定是满二叉树。
在同样结点个数的二叉树中，完全二叉树的深度最小。

二叉树的性质

在这里插入图片描述

二叉树的存储结构及其实现

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置(下标)应能体现
结点之间的逻辑关系—父子关系。

如何利用数组下标来反映结点之间的逻辑关系?

完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。

完全二叉树可以使用顺序存储的方法。

在这里插入图片描述

一棵斜树的顺序存储会怎样呢？

二叉链表

基本思想：

令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外,还要设置指示左右孩子的指针。

结点结构：

在这里插入图片描述

struct BiNode
{
	DataYype data;
	BiNode *lchild, *rchild;
}

在这里插入图片描述

具有 n 个结点的二叉链表中，有 n+1 个空指针
解释：n 个结点的二叉链表中，每个结点有两个指针域，共有 2n 个指针域，对于 n 个结点的二叉链表，只有根结点没有与边相连，故共有 n–1条边，每一条边其实就是占用了一个双亲结点的指针域，剩下的就是空指针，就是所有的指针域减去用到的指针域，也就是 2n – (n-1) = n+1 个空指针

在二叉链表中如何求某结点的双亲？

因为结点的指针域都指向孩子结点，无法通过孩子结点找到双亲结点。故需要采用三叉链表

三叉链表