第五章：树

标签：左子结点遍历中序右子第五章二叉树

观看青岛大学-王卓老师的网课，根据每一章做如下总结：
青岛大学-王卓老师B站上的网课

5 树

5.1 树和二叉树的定义

树是一种非线性的数据结构，树（Tree）是n个结点的有限集。

若n=0，称为空树；
若n>0，满足（1）有且仅有一个根（root）结点（2）其余结点可分为m个互不相交的有限集T1，T2...Tm。每个集合又是一棵树，称为根的子树。

所以树是一个递归（嵌套）的概念。

5.1.1 树的定义

树（Tree）是n个结点的有限集。包含多种表示方式：嵌套集合，广义表，凹入表示。

结点：数据元素以及指向的子树的分支。
根结点：非空树中无前驱结点的结点。
结点的度：结点拥有的子树数。
树的度：树内各结点的度的最大值。
树的深度：树中结点的最大层次。
叶子结点（终端结点）：度=0
分支结点（非终端结点）：度≠0，根结点以外的分支节点称为内部节点。
双亲：结点的子树的根称为该结点的孩子(child)，该结点成为该孩子的双亲(parent)。
堂兄弟：parent位于同一层的结点
祖先：从root到该node所经分支上的所有结点。
子孙：以某结点为根结点的子树中任意node（在它之下，除了它自己，全部都是；如果子树的根结点是叶子节点，那该子树的根结点是孩子也是孙子）

树的分类：
1.有序树：树中结点各子树从左至右有次序（最左边的第一个孩子）
2.无序树：树中结点各子树无次序。

3.森林：m(m≥0)棵互不相交的树的集合。把root删除，树就变成看森林；给森林中各子树加上一个双亲结点，森林就变成了树。一棵树是特殊的森林。

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

5.1.2 二叉树的定义

二叉树的结构最简单，规律性最强，可以证明，所有树都能转为唯一对应的二叉树。
二叉树：由一个根结点和两颗互不相交的（左子树、右子树）树的二叉树组成。
1）二叉树中的node的度总是≤2。
2）子树有左右之分，次序不能颠倒。即使仅有一颗子树，也要说明左子树和右子树。（而对于树而言，只有一个孩子时，无须区分是左还是右的次序。这是二叉树和树的不同）
3）二叉树可以是空集合，可以有空的左子树和右子树。可以看出，二叉树的每个结点位置/次序是固定的，可以是空，但不能没有。
二叉树和树是两个不同的概念
二叉树的5中基本形态
空二叉树
根和空的左右子树
根的左子树
根的右子树
根的左右子树

5.2 树的实际应用

1.数据压缩：
将数据文件转换成由0、1组成的二进制串，称之为编码。

等长编码（浪费内存）
不等长编码1（通过前缀码辨别不同子树，哈夫曼树）
不等长编码2

2.利用二叉树求解表达式的值：第一操作数 运算符 第二操作数
双亲结点：存储运算符
左子树：第一操作数
右子树：第二操作数
若为一元运算符，左子树为空

5.3 树和二叉树的抽象数据类型定义

ADT BinaryTree{ 数据对象D：数据关系R：基本操作P： }ADT BinaryTree

CreateBiTree(&T, definition) // 二叉树有不同的遍历方式，因而有不同的definition

5.4 二叉树的性质和存储结构

性质1：二叉树的第\(i\)层上至多有\(2^{i-1}\)个结点（一层的数量）
二叉树的第\(i\)层上至少有1个结点（一层的数量）
性质2：深度为\(k\)的二叉树至多有\(2^{k}-1\)个结点（所有层求和的数量）
深度为\(k\)的二叉树至少有\(k\)个结点（所有层求和的数量）
性质3：对任何一棵二叉树T1，如果叶子数为n0,，度为2的结点数为n2，则n0=n2+1

证明如下：
其中n为所有结点的个数，n2为度为2的节点个数，n1为度为1的结点个数
且n0+n1+n2=n
性质4：具有n个结点的完全二叉树深度为[\(log_{2}n\)]+1
[]表示取整

说明了结点编号与深度之间的关系
性质5：具有n个结点的完全二叉树（深度为[\(log_{2}n\)]+1）按层序编号，每层从左到右。则对任一结点i：（1≤i≤n）

若i=1，则结点i是二叉树的根，无双亲；如果i>1，则双亲是[i/2]
若2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子结点为2i
若2i+1>n，则结点i无右孩子；否则，其右孩子结点为2i+1。
说明了双亲结点编号与孩子结点编号之间的关系

两种特殊形式的二叉树
1.满二叉树：总结点数达到最大结点数的树。（深度为k且有2^k-1个结点的二叉树）
特点：

每一层都满：每一层上的结点数都是最大结点数
叶子结点全部都在最底层
对结点位置进行编号
编号规则：从根结点开始，自上而下，自左而右

2.完全二叉树：深度为k的具有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，该树为完全二叉树。

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

什么是连续？
满二叉树有4、5、6、7叶节点，需要去掉5、6、7（如果去掉的是5、7，就不是连续去掉）
不是完全二叉树

特点：

叶子结点只可能分布在层次最大的两层上（最后一层、倒数第二层）
对任一结点，如果右子树最大层次为i，则左子树最大层次必为i或i+!（最多相差一层）

二叉树的存储结构

顺序存储结构
实现：按照满二叉树的结点层次编号，依次存放二叉树中的数据元素。

缺点：大小固定，若树中的元素个数变化大，顺序存储不适用；空的内部结点也要存储null，浪费空间（最坏的情况：深度为k且只有k个结点的单支树需要长度为\(2^{k}-1\)的一维数组）适用于存储满二叉树和完全二叉树
优点：结点间的前驱和后继关系蕴含在存储位置中
链式存储结构：二叉链表/三叉链表
1）二叉链表：寻找结点的后继关系(child)
一个数据存储形式：数据域+指针域，包含数据本身+两个指针（嵌套/递归的定义）

| lchild |data | rchild |

定义BiNode结点类型为普通的结点类型BiNode和指向具有三个成员的结点类型的指针*BiTree
在n个结点的二叉链表中，有n+1个空指针域。（每个结点有2个链域，共有2n个链域；每个结点有且只有一个双亲，故有n-1个结点的链域存放指针）
2）三叉链表：寻找结点的后继关系(child)和前驱关系(parent)
一个数据域+3个指针域

5.5 二叉树的遍历

5.5.1 二叉树的遍历类型

遍历目的：得到树中所有结点的线性排列，这是树结构“增删改查”和排序运算的前提。
遍历方法：依次遍历二叉树的三个组成部分，共有6种方案（3!，重点研究DLR、LDR、LRD）
确定先左后右，有DLR先序遍历、LDR中序遍历和LRD后序遍历三种。

DLR先序遍历（自上而下）
首先树分为三个部分，左（B为根结点的树） + 右（D为根结点的树） + 根（A），先访问根结点A，然后处理左子树得到BEL，最后处理右子树得到DHMIJ。处理左右子树都根据DLR，先根再左右的方式。

算法实现：
二叉树先序遍历算法/理论
二叉树先序遍历算法/代码

具体实现过程：

LDR中序遍历（自下而上）
首先分为三个主要部分，先看左子树，如果左子树的左右子树不全为空，则继续往下搜寻，对每个孙子结点循环判断左右子树是否为空，直至存在一个叶子结点的左右子树为空。然后从叶结点所在的根结点的子树开始往上遍历（图中左子树中，最早的子树是以E为根结点的子树）。找到根结点A之后，在右子树去找最底层的左子树。以下图中，树先分为三个部分，左（B为根结点的树） + 右（D为根结点的树） + 根（A），先处理左子树得到ELB，然后到根结点A，之后处理右子树得到MHIDJ。

算法实现：
二叉树中序遍历算法/代码

LRD后序遍历
首先树分为三个部分，左（B为根结点的树） + 右（D为根结点的树） + 根（A），先处理左子树得到LEB，然后处理右子树得到MIHJD，最后是根结点A。

算法实现：
二叉树后序遍历算法/代码

这三种遍历方式只有输出语句位置不一样，如果去掉输出语句，从递归的角度看这三种算法的访问路径是相同的，只是访问结点的时机不同。
遍历算法的分析

5.5.2 根据遍历序列确定二叉树

若二叉树各结点的值均不相同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的。
由二叉树的先序序列和中序序列，或者由二叉树的中序序列和后序序列可以唯一确定一棵二叉树。

根据先序序列和中序序列
首先，从先序中确定根结点A；然后，在中序中找到左子树包含的序列CDBEF，右子树包含的序列IHFJ。
对于左子树，在先序中找到根结点B，在中序中找到左子树CD，右子树FE；
同理，对于右子树，在先序中找到根结点G，在中序中找到左子树IH，右子树J。
按照这个规律类推，得到二叉树。
根据中序序列和后序序列
首先，从后序序列尾部找到根结点A；在中序中找到左子树包含的序列BDCE，右子树包含的序列FHG。
对于左子树，在后序中找到根结点B，在中序中找到右子树DCE，左子树为空；
同理，对于右子树，在后序中找到根结点F，在中序中找到右子树HG，左子树为空。
按照这个规律类推，得到二叉树。