数据结构——非线性结构（树与二叉树）

一. 非线性结构的概述

二. 树的基本概念

1. 树的定义

专业定义：

• 1）有且只有一个称为根的节点
• 2）有若干个互不相交的子树，这些子树本身也是一棵树（递归定义）

通俗定义：

• 1）树是由节点和边组成
• 2）每个节点只有一个父节点但可以有多个子节点
• 3）但有一个节点除外，该节点没有父节点，此节点称为根节点（n个节点的树中有n-1条边）

2. 专业术语

• 节点：一个个圈
• 父节点：和它紧挨着的上面的节点（只有一个）
• 子节点：父节点的下层节点
• 深度：从根节点（第一层）到最底层节点的最大层数
• 高度：从叶子节点开始自底向上逐层累加，数值等于深度
• 叶子节点：没有子节点的节点
• 非终端节点（分支节点）：实际就是非叶子节点
• 根节点：既可以是叶子结点，又可以是非叶子节点
• 节点的度：这个节点拥有子节点的个数
• 树的度：树内各节点度的最大值
• 子孙：他下面所有的节点
• 堂兄弟：父亲是兄弟，他们就是堂兄弟
• 有序树和无序树：树中节点每个子树从左到右有次序，不能互换，称此树为有序树，否则称为无序树
• 路径：两节点的路径由这两个节点之间所经过节点序列构成
• 路径长度：路径上经过边的个数
• 树的路径长度：树根到每个节点路径长度之和

3. 树的性质

三. 树的分类

1. 一般树

定义：任意一个节点的子节点的个数都不受限制

2. 二叉树（是有序树）

2.1 概念

定义：任意一个节点的节点个数最多两个，且子节点的位置不可更改（有左右之分）

2.2 分类

1. 一般二叉树

2. 满二叉树

定义：在不增加树的层数的前提下，无法再多添加一个节点的二叉树

3. 完全二叉树

定义：

• 如果只是删除了满二叉树最底层最右边的连续若干节点，这样形成的二叉树
  
  

性质：

• 完全二叉树的一个特例是满二叉树

目的：

• 为了解决树以数组方式的存储问题

2.3 二叉树的性质

2.3.1 二叉树的常考性质

2.3.2 完全二叉树的常考性质

3. 森林

定义：n(n≥0)个互不相交的树的集合

四. 树的存储

1. 来源

• 由于内存是一个线性一维的，想要用线性结构存储非线性结构比较困难
• 所以我们学习树这种存储，就是为了学会如何将树这种类型的数据结构存储到计算机上面

树的存储最核心的是：以二叉树存储
二叉树的算法比较成熟：
所以

2. 二叉树的存储

2.1 连续存储（必须转化为完全二叉树）

1）想要将一般的二叉树以数组方式存储的话，必须先将一般二叉树转化为完全二叉树再存储

为什么要添加无效节点（0表示空节点）？

• 因为若只存储有效节点，不添加额外无用的节点，就无法确定以前的树的构造形态（也就是无法还原树的形态）

存储有效节点方式？

• 因为树是非线性结构，而内存是线性结构来存储，所有只有将非线性结构转化为线性结构
• 所有人们造出了三种规定：先序、中序、后序遍历来转化为三种不同的线性结构。但若一个二叉树只存放有效节点，无论以哪一种遍历方式转化的线性结构来存储都无法还原到原来的二叉树形态（tip：这里系统一般只存储一种遍历方式，与后面已知两种遍历方式推出二叉树结构不同）

2）以完全二叉树来存储优缺点
优点：

• 知道了节点的个数就知道这棵树有几层
• 已知任何一个节点，就可知道它的父节点是谁，它的子节点是谁，以及它有没有子节点

缺点：

• 耗费内存

2.2 链式存储

2.2.1 二叉树链式存储结构描述

节点结构包含3个域：数据域 data、左指针域 lchild、右指针域 rchild

二叉树链式存储的优缺点：
缺点：

• 浪费一点空间，即空指针域
• 在含有n个节点的二叉链表中，含有n+1个空链域

优点：

• 求子节点很方便
• 空间利用率高
• 解决了在计算机中存储非连续结构的二叉树（通过用指针域链成一个有层次的树）

3. 一般树的存储（用线性来存储非线性结构方法）

3.1 双亲表示法（求父节点方便）

3.2 孩子表示法（求子节点方便）

3.3 双亲孩子表示法（求父节点和子节点都很方便）

• 操作较为复杂
• 不能使用子节点下标，必须使用子节点指针域
• 子节点可能为多个，也可能没有

3.4 孩子兄弟表示法（二叉树表示法）

把一个普通树转化成二叉树来存储具体转化方法：

• 设法保证任意一个节点的：左指针域指向它的第一个孩子、右指针域指向它的第一个兄弟

只要能满足此条件，就可以把一个普通树转化为二叉树

tip：一个普通树转化成的二叉树，一定没有右子树

4. 森林的存储

4.1 森林转化为二叉树

4.2 存储方法

先把森林转化为二叉树，再去存储二叉树

4.3 转化方法

把B和G当做A的兄弟，再用一般树转化为二叉树方法即可

五. 树的操作

人类造出三种规则：先序、中序、后序这三种遍历，都可以把一个非线性的树转化成一个线性序列

这样方便可以在我们硬件上存储（因为现实中很多问题是非线性的，但硬件的内存条存储是线性的，故想要在内存上存储必须先线性化）

1. 二叉树的遍历

1.1 先序遍历（先访问根节点）

• 先访问根节点
• 再先序访问左子树
• 再先序访问右子树

本质：递归访问

1.2 中序遍历（中间访问根节点）

• 中序遍历左子树
• 再访问根节点
• 再中序遍历右子树

1.3 后序遍历（最后访问根节点）

• 后序遍历左子树
• 后序遍历右子树
• 再访问根节点

---

三种遍历算法的总结：

• 递归遍历左右子树顺序是固定的，只是访问根的顺序不同。
• 时间复杂度O(n)：因为不管采用哪种遍历算法，每个节点都访问一次
• 空间复杂度：为递归工作栈的深度 = 树的深度，所以最坏情况下，二叉树n个节点的深度为n的单分支，那么空间复杂度为O(n)

1.4 层次遍历

按照1,2,3,4的层次顺序，对二叉树中的各个结点进行访问

层次遍历需要借助一个队列

• 先将根节点入队、再出队、再访问出队元素
• 若有左子树，将左子树根节点入队、在出队、再访问出队元素
• 若也有右子树，将右子树根节点入队、在出队、再访问出队元素
• …直到队列为空

1.5 已知两种遍历序列求原始二叉树

若我们已知一课二叉树的先序、中序、后序中的任何一种，都不能把原始二叉树给还原出来。

我们只有通过（先序和中序） 或 （中序和后序）可以还原出原始的二叉树，但是通过先序和后序是无法还原出原始的二叉树的。

1）已知先序和中序求后序

解释：
先看先序，第一个出现A即为根节点
然后看中序，找A的位置，来确定左、右子树

• 那么BDCE为左子树、FHG为右子树，但又不知道哪个是根，不知道左边第一个写啥
• 所以再看先序中BDCE哪个先出现，哪个就是根，可见B先出现为根，再看中序，再来确定B为根的话，那他两边左、右子树又是谁？
• 有因为B只有右边有数，可见B没有左子树，只有右子树DCE，再同理，继续确定B左子树的根

先序找根，中序找左右子树

2）已知中序和后序求先序

解释一下：
先看后序最后出现是根节点A
再看中序可知左、右子树，想确定左、右子树的根节点

• 所以看后序中左、右子树对应部分中哪个最后出现则为根

同理，再确定左、右子树

3）总结：

已知（中序+后序）或（中序+前序）或（中序+层序）可得一颗二叉树

• 其中中序只能确定大体的某根节点左右两侧节点的大致情况，除非左右两侧只有一个节点，否则不好确定左右两侧节点位置
• 通过：后/前/层序来确定每一个具体的根节点的位置

2. 森林的遍历

2.1 先序遍历森林

2.2 中序遍历森林

六. 树与二叉树的应用

1. 树是数据库中数据组织的一种重要形式

2. 操作系统子父进程关系本身就是一棵树

3. 面向对象语言中类的继承关系本身就是一棵树

4. 线索二叉树

4.1 线索二叉树的基本概念

1）线索二叉树的来源

• 传统的二叉树找前驱、后继很不方便，遍历操作必须从根开始
• 传统二叉链表只能体现父子关系，不能得到遍历中的节点的前驱和后继节点
• 且传统的含有n个节点的二叉链表有n+1个空指针
• 因此想利用这些空指针来存放指向前驱或后继的指针

2）引入线索二叉树的目的：

• 加快查找前驱节点和后继节点的速度

3）线索二叉树的节点结构

• 规定：若无左子树，令lchild指向其前驱节点；若无右子树，令rchild指向其后继节点，标志域指示节点的指向。

4）线索二叉树的存储结构

5）线索二叉树的分类

• 中序线索二叉树：按照中序遍历进行线索化
• 先序线索二叉树：按照先序遍历进行线索化
• 后序线索二叉树：按照后序遍历进行线索化

4.2 二叉树的基本操作

4.2.1 二叉树的线索化构造

定义：

• 将原始二叉链表中的空指针改为指向前驱或后继的线索。（由于想知道前驱和后继的信息，必须遍历一遍二叉树）。所以线索化的本质：遍历一次二叉树

一、中序线索二叉树

1）定义：

• 按照二叉树中序遍历序列画线索

2）构造中序线索二叉树

3）中序线索二叉树的存储

二、先序线索二叉树

1）定义：

• 按照先序序列，依次判断每个节点左右链域，若为空则将其改造为线索

2）构造先序线索二叉树

3）先序线索二叉树的存储

三、后序线索二叉树

1）定义：

• 按照后序序列，依次判断每个节点左右链域，若为空则将其改造为线索

2）构造后序线索二叉树

3）后序线索二叉树的存储

4.2.2 线索二叉树找前驱/后继

7. 哈夫曼树（最优二叉树）

7.1 基本概念

7.1.1 节点的权、带权路径长度

7.1.2 哈夫曼树的定义

7.2 哈夫曼树的构造

tip

• 左右孩子节点的顺序是任意的，所有构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优
• 但建议每一层编号按从小到大进行排序

7.3 哈夫曼编码

tip

• 利用哈夫曼树可以设计出总长度最短的二进制前缀编码
• 0/1究竟是表示左子树还是右子树没有明确规定

---

参考文献

• 郝斌<数据结构>
• 王道考研<数据结构>