树结构是一种重要的非线性数据结构。直观地说，树是分支关系定义的层次结构。树木结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织。树木也广泛应用于计算机领域，尤其是二叉树。例如，在操作系统中，树用于表示文件目录的组织结构，在编译系统中，树用于表示源程序的语法结构，树结构也是数据库系统中信息的重要组织形式之一。

树(Tree)是n(n≥0)个结点的有限集，或空树(n=0)；或者非空树，非空树T：

• 只有一个结点叫根；
• 除根结点以外的其他结点可分为 m(m>0)不相交的有限集 T 1 , T 2 , … , T m T_1,T_2,…,T_m T1,T2,…,Tm，每一集本身都是一棵树，被称为根子树(SubTree)。

如下图所示，(a)树只有一个根结点；(b)树有13个结点，其中A是根，其余的结点分为三个子集： T 1 = { B , E , F , K , L } , T 2 = { C , G } , T 3 = { D , H , I , J , M } 。 T_1=\{B,E, F, K, L\}, T_2=\{C,G\},T_3=\{D, H, I, J, M\}。 T1={ B,E,F,K,L},T2​={ C,G},T3​={ D,H,I,J,M}。 T 1 、 T 2 T_1、T_2 T1​、T2​和 T 3 T_3 T3​都是根A的子树，且本身也是一棵树。例如 T 1 T_1 T1​，其根为B，其余结点分为两个互不相交的子集： T 11 = { E , K , L } , T 12 = { F } T_{11}=\{E,K,L\},T_{12}=\{F\} T11​={ E,K,L},T12​={ F}。 T 11 T_{11} T11​和 T 12 T_{12} T12​都是B的子树。而 T 11 T_{11} T11​中E是根，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ElWxM8zD-1630834564974)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.1snlu7sniveo.png)

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下几个性质:

• 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
• 树中所有结点可以有零个或多个后继。
• 树中的结点数等于所有结点的度数加1。
• 度为m的树中第i层上至多有 m i − 1 m^{i-1} mi−1个结点 ( i ≥ 1 ) (i ≥1) (i≥1)。
• 高度为h的m叉树至多有 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh−1)/(m−1)个结点。
• 具有n个结点的m叉树的最小高度为 [ log ⁡ m ( n ( m − 1 ) + 1 ) ] [\log_m {(n(m-1)+1)}] [logm​(n(m−1)+1)]。

树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

二叉树(Binary Tree)是n(n≥0)个结点所构成的集合，它或为空树(n=0); 或为非空树，对于非空树T:

• 有且仅有一个称之为根的结点；
• 除根结点以外的其余结点分为两个互不相交的子集 T 1 T_1 T1​和 T 2 T_2 T2​, 分别称为T的左子树和右子树，且 T 1 T_1 T1​和 T 2 T_2 T2​本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

• 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）；
• 二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。二叉树的5种基本形态如下图所示。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SF8XiIoy-1630834649275)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.y99zwnb80u8.png)

根据树的结构定义，加上树的一组基本操作就构成了树的抽象数据类型定义：

ADT Tree{
    数据对象D：D 是具有相同特性的数据元素的集合。
    数据关系R：若 D 为空集，则称为空树；其余略。
    基本操作P：
        InitTree(&T); //构造空树T。
    	DestroyTree(&T); //销毁树T。
    	CreateTree(&T,definition); //按definition构造树T。
    	ClearTree(&T); //将树T清为空树。
    	TreeEmpty(T); //若 T 为空树，则返回 true, 否则 false。
    	TreeDepth(T); //返回T的深度。
    	Root(T); //返回T的根。
    	Value(T,cur_e); //返回 cur_e 的值。
    	Assign(T,cur_e,value); //结点 cur_e 赋值为 value。
    	Parent(T,cur_e); //若 cur_e是 T 的非根结点，则返回它的双亲，否则函数值为“空”。
    	LeftChild(T,cur_e); //若 cur_e是T 的非叶子结点，则返回它的最左孩子，否则返回“空”。
    	RightSibling(T,cur_e); //若 cur_e 有右兄弟，则返回它的右兄弟，否则函数值为“空”。
    	InsertChild(&T,p,i,c); //插入c为T中p指结点的第i棵子树。
    	DeleteChild(&T,p,i); //删除T中 p 所指结点的第i棵子树。
    	TraverseTree(T); //按某种次序对T的每个结点访问一次。
}ADT Tree

二叉树的抽象数据类型定义如下：

ADT BinaryTree{
    数据对象D：D 是具有相同特性的数据元素的集合。
    数据关系R：若 D=∮，则R=∮，称BinaryTree为空二叉树；其余略。
    基本操作P：
        InitBiTree(&T); //构造空二叉树T。
    	DestroyBiTree(&T); //销毁二叉树T。
    	CreateBiTree(&T,definition); //按definition构造二叉树T。
    	ClearBiTree(&T); //将二叉树T清为空树。
    	BiTreeEmpty(T); //若T为空二叉树，则返回true, 否则false。
    	BiTreeDepth(T); //返回T的深度。
    	Root(T); //返回T的根。
    	Value(T,e); //返回e的值。
    	Assign(T,&e,value); //结点e赋值为value。
    	Parent(T,e); //若e是T的非根结点，则返回它的双亲，否则返回“空”。
    	LeftChild(T,e); //返回e的左孩子。若e无左孩子，则返回“空”。
    	RightChild(T,e); //返回e的右孩子。若e无右孩子，则返回“空”。
    	LeftSibling(T, e); //返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回 “空”。
    	RightSibling(T,e); //返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回 “空”。
    	InsertChild(&T,p,LR,c); //根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。
    	DeleteChild(&T, p, LR); //根据LR为0或1, 删除T中p所指结点的左或右子树。
    	PreOrderTraverse(T); //先序遍历T, 对每个结点访问一次。
    	InOrderTraverse(T); //中序遍历T, 对每个结点访问一次。
    	PostOrderTraverse(T); //后序遍历T, 对每个结点访问一次。
    	LevelOrderTraverse(T); //层序遍历T, 对每个结点访问一次。
}ADT BinaryTree

1. 满二叉树

   一棵高度为h，且含有 2 h − 1 2^h-1 2h−1个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点，如图(a)所示。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y9gl1LOE-1630834564980)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.7k4ldf2nvg40.png)

   可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树的定义。

2. 完全二叉树

   高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树，如图(b)所示。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DwTpx3f0-1630834564985)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.35kfs7nqx5c0.png)

   其特点如下:

   • 若 i ≤ ⌊ n / 2 ⌋ i≤\lfloor {n/2}\rfloor i≤⌊n/2⌋，则结点 i 为分支结点，否则为叶子结点。
   • 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
   • 若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征)。
   • 按层序编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于 i 的结点均为叶子结点。
   • 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

3. 二叉排序树

   左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

4. 平衡二叉树

   树上任一结点的左子树和右子树的深度之差不超过1。

二叉树具有下列重要特性：

• 性质1：在二叉树的第i层上至多有 2 i − 1 2^{i-1} 2i−1个结点(i≥1)。
• 性质2：深度为k的二叉树至多有 2 k − 1 2^{k}-1 2k−1个结点(k≥1)。
• 性质3：对任何一棵二叉树T, 如果其终端结点数为 n 0 n_0 n0​，度为2的结点数为 n 2 n_2 n2​，则 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。
• 性质4：具有n(n>0)个结点的完全二叉树的高(深)度为 ⌈ log ⁡ 2 ( n + 1 ) ⌉ \lceil \log_2 (n+ 1)\rceil ⌈log2​(n+1)⌉或 ⌊ log ⁡ 2 n ⌋ + 1 \lfloor \log_2n \rfloor+1 ⌊log2​n⌋+1。
• 性质5：对完全二叉树按从上到下、从左到右的顺序依次编号1,2,…, n，则有以下关系:
  • 当i>1时，结点 i 的双亲的编号为 ⌊ i / 2 ⌋ \lfloor i/2\rfloor ⌊i/2⌋，即当 i 为偶数时，其双亲的编号为i/2，它是双亲的左孩子;当 i 为奇数时，其双亲的编号为 ( i − 1 ) / 2 (i- 1)/2 (i−1)/2，它是双亲的右孩子。
  • 当2i≤n时，结点 i 的左孩子编号为2i，否则无左孩子。
  • 当2i+1≤n时，结点 i 的右孩子编号为2i+1，否则无右孩子。
  • 结点 i 所在层次（深度）为 ⌊ l o g 2 i ⌋ + 1 \lfloor log_2i\rfloor+ 1 ⌊log2​i⌋+1。

类似线性表，二叉树的存储结构也可采用顺序存储和链式存储两种方式。

1. 顺序存储结构

   顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。

   对于完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xvXvk3WF-1630834564987)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.6vnftcmc0nw0.png)

   对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，如下图所示，图中以"0"表示不存在此结点。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iDMBBAhP-1630834564988)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.1kwybra1r4xs.png)

   由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为K且只有K个结点的单支树（树中不存在度为2的结点）却需要长度为 2 k − 1 2^k-1 2k−1的一维数组。这造成了存储空间的极大浪费， 所以对于一般二叉树，更适合采取下面的链式存储结构。

2. 链式存储结构

   设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、 右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左、 右指针域，如下图(b)所示。有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域，如图 ( c ) 所示。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BpRJAxML-1630834564990)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.1c75cred95z4.png)

   利用上图中两种结点结构所得的二叉树的存储结构分别称为二叉链表和三叉链表，如下图所示。链表的头指针指向二叉树的根结点。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-p0xpOUB6-1630834564992)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.3hq3zrrbbm00.png)

   在不同的存储结构中，实现二叉树的操作方法也不同，如找结点x的双亲, 在三叉链表中很容易实现，而在二叉链表中则需从根指针出发巡查。由此，在具体应用中采用什么存储结构，除根据二叉树的形态之外还应考虑需进行何种操作。在下一节的二叉树遍历及其应用的算法均采用以下定义的二叉链表形式实现。

   // －－－－ 二叉树的二叉链表存储表示 －－－－
   typedef struct BiTNode{
       TElemType data;  //结点数据域
       struct BiTNode *lchild,*rchild;  //左右孩子指针
   }BiTNode,*BiTree;
   

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者是对树中的全部结点逐一进行处理，这就提出了一个遍历二叉树的问题。线索二叉树是在第一次遍历时将结点的前驱、后继信息存储下来，便于再次遍历二叉树。

遍历二叉树(traversing binary tree)是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

假如使用L、D、R分别表示遍历左子树、访问根结点和遍历右子树，且限定先左后右，则有我们常使用的4种遍历。我们使用下述表格进行说明：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mPUTEafX-1630834564994)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.2tuwwl6hvmm0.png)

接下来，我们会围绕上图所示的二叉树来介绍二叉树的先中后序遍历，并给出相关算法描述。我们首先来看一下各种不同的遍历所得到的输出顺序。

从遍历结果来看，先中后序遍历的结果所对应的恰好为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。

我们通过下图来具体了解一下先中后序遍历算法的递归执行过程。向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回；虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问结点时输出的信息。 只要沿着虚线从1出发到2结束，将沿途所见的三角形(或圆形或方形)内的字符记下，便得到遍历二叉树的先序（或中序或后序）序列。例如在下图中，沿虚线游走可以分别得到先序序列为ABDEC、中序序列为DBEAC、后序序列为DEBCA。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hk9EAYFK-1630834564995)(https://cdn.jsdelivr.net/gh/alonscholar/image-warehouse@master/blog/数据结构/数据结构(严蔚敏)]-第五章-树和二叉树/image.5pl9crxi5qo0.png)

下面我们给出先中后序遍历算法的递归与非递归实现，与层次遍历的代码实现。