数据结构入门5-1（树和二叉树）_createbitree是什么意思

目录

注

树和二叉树的定义

树的定义

树的基本术语

二叉树的定义

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

二叉树的性质和存储结构

二叉树的性质

二叉树的存储结构

1. 顺序存储结构

2. 链式存储结构

遍历二叉树和线索二叉树

遍历二叉树（traversing binary tree）

1. 算法描述

2. 根据遍历序列确定二叉树

3. 二叉树遍历算法的应用

线索二叉树（Threaded Binary Tree）

1. 线索二叉树的基本概念

2. 构造线索二叉树

3. 遍历线索二叉树

---

注

        本笔记主要参考《数据结构（C语言版）》

---

        树结构是一种非常重要的非线性数据结构，这种层次结构以分支关系定义。树结构非常常见，在操作系统、编译系统或者数据库中都有树的身影。

树和二叉树的定义

树的定义

        树（tree）是 n（n ≥ 0）个结点的有限集，通过n，可以将树归为：① 空树（n = 0）；② 非空树（n ＞ 0）。

        而对于非空树T：

例如：

        其中，对于（b）中一般的树，可以认为：

        树的结构定义是一个递归的定义，即在 树的定义中 又用到了树的定义。树的表示方式有很多，譬如：

    之所以存在多种多样的表示方式，说明了树结构在日常生活及计算机程序设计中的重要性。

树的基本术语

    通过上述定义可知，可以用森林和树互相递归的定义描述树。 

         就逻辑结构而言，任何一颗树都是一个二元组 Tree = (root, F)，其中：

        当m ≠ 0时，树根和其子树森林之间存在下列关系：

二叉树的定义

        二叉树（Binary Tree）是n（n ≥ 0）个结点所构成的集合，它可以为空树（n = 0），或者是非空树。

        对于非空树T：

        二叉树和树一样，都具有递归的性质。而二者的差别主要体现在：

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

        二叉树的递归定义表明：二叉树或为 空 ，或为 一个根结点加上两棵互不相交的二叉树（左子树和右子树）组成（两棵子树也可以是空树）。

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

    设A、B是集合，离散数学中的一些定义如下：

• A - B：是属于集合的减法，它表明的是属于A，但不属于B的所有元素组成的集合；
• Ø：空集（也可通过Φ表示），即是指不含任何元素的集合；
• 划分：若把集合A分成若干个叫做分块的非空子集，并且集合A中的任一元素属于并且仅属于一个分块，那么把这些分块构成的集合称为划分；
• 下述的R：简单地说，是D中任意两个元素之间的关系的集合（笛卡尔乘积）。

        树的抽象数据类型定义：

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

二叉树的性质和存储结构

二叉树的性质

        二叉树具有三个重要的性质：

        另外，还存在两种特殊形态的二叉树，称为 满二叉树 和 完全二叉树 ：

---

        对于满二叉树而言：

    对二叉树的结点进行编号，约定：编号从根结点开始，自上而下，从左到右。

---

        而对于完全二叉树而言：

    可以把满二叉树看作是一种特殊的完全二叉树。

        同时，完全二叉树还具有两个重要的特性：

二叉树的存储结构

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

1. 顺序存储结构

//#define TElemType int	//自行定义TElemType的类型
//
#define MAXSIZE 100		//二叉树的最大结点数
typedef TElemType SqBiTree[MAXSIZE];	//其中，下标为0的单元存储根结点
SqBiTree bt;

        顺序存储结构通过一组地址连续的存储单元来存储数据元素，并且，为了能够反映出存储结构中的结点之间的逻辑关系，需要将二叉树中的结点按照一定的规律安排到这组单元内：

• 完全二叉树：从根处开始，按照层序进行存储（即从上到下，从左到右存储结点元素）。

  

• 一般的二叉树：将其结点与对应深度的完全二叉树上的结点相对照，存储在一维数组的相应分量中。

  

    在最坏的情况下，一个深度为k且只有k个结点的单支树（数中不存在度为2的结点）却需要长度远超k的一维数组进行存储。

        由此可知，顺序存储结构仅适用于完全二叉树。一般二叉树更适合链式存储结构。

---

2. 链式存储结构

        根据结点结构的不同，存在不同形式的链式存储结构。

1. 二叉链表：链表的结点中包含了3个域，分别是数据域和左、右指针域。

   

   #define TElemType int
    
   typedef struct BiTNode {
   	TElemType data;						//结点的数据域
   	struct BiTNode* lchild, * rchild;	//结点的左、右孩子的指针域
   }BiTNode, * BiTree;
   

2. 三叉链表：相比于二叉链表，这种结点结构增加了一个指向双亲结点的指针域。

   

   （代码实现参考二叉链表）

        对应于上述的结点结构，存在相应的存储结构：

• 对于二叉链表而言：

  

          可以看出，在有n个结点的二叉链表中存在着 n+1 个空链域（这些空链域可以存储其他有用信息）。
•  对于三叉链表而言：

  

    在不同的层次结构中，实现二叉树的操作方式也会有所不同。就比如 PARENT(T, e)（寻找结点x的双亲），在三叉链表中（因为有存储双亲地址的指针域）可以轻松找到目标；而在二叉链表中则需要从根结点开始巡查。

    因此，在考虑二叉树的存储结构时，还应该考虑这个二叉树将要进行何种操作。

遍历二叉树和线索二叉树

作用：

• 遍历二叉树：①在树中查找具有某种特征的结点，②对树中的全部结点逐一进行处理；
• 线索二叉树：在第一次遍历时记录结点的前驱、后驱信息，方便再次遍历。

遍历二叉树（traversing binary tree）

1. 算法描述

        算法要实现的目标：按某条搜索路径巡防树中的每个结点，使得每个结点均被访问，且仅被访问一次。

||| 访问的含义：对结点进行各种处理，包括 输出结点的信息 ，对结点进行运算和修改 等。

    遍历二叉树是二叉树中最基本的操作。

        遍历的实质是对二叉树进行线性化的过程，遍历的结果是将 非线性结构（的树）中的结点排成一个线性序列。为了实现这个目标，就需要寻找能够排列二叉树上的结点的规律。

        由于二叉树是由3个基本单元组成的：根结、左子树和右子树。因此，如果要遍历整个二叉树，就是要遍历这三个部分。现在假设：

• D：访问根结点；
• L：遍历左子树；
• R：遍历右子树。

        由上述假设可以得到6种遍历二叉树的方案：DLR、DRL、LDR、LRD、RDL、RLD。在此之上，对遍历方案进行限制，要求遍历顺序必须是先左后右，由此选出3种方案，根据遍历根结点的先后顺序，命名得到：

例如，下方的二叉树表示的是表达式 a + b * (c - d) - e / f：

• 若按先序遍历上述二叉树，可得到该二叉树的先序序列：

  

• 按中序遍历上述二叉树，得到该二叉树的中序序列：

  

• 按后序遍历上述二叉树，得到该二叉树的后序序列：

  

例子：中序算法

    约定：在该中序算法中，对于结点的访问即为数据的输出。

【递归版本】

void InOrderTraverse(BiTree T)
{//中序遍历二叉树T的递归算法
	if (T)				//若二叉树非空
	{
		InOrderTraverse(T->lchild);		//中序遍历左子树
		cout << T->data;				//访问根结点
		InOrderTraverse(T->rchild);		//中序遍历右子树
	}
}

（ps：如果改变上述语句的先后顺序，就可以实现先序和后序遍历的递归算法。）

        由上述代码可知，3种遍历的不同仅在于访问次序的差异。因此，如果从递归的角度讨论先序、中序和后序遍历，会发现三者是完全相同的：

        现在要求通过中序遍历的方式遍历上述二叉树，由代码可得遍历的执行过程：

 【非递归版本（使用栈）】

        根据目前的知识，可以把上述的递归算法改为非递归算法：

void inordertraverse(BiTree T)
{//中序遍历二叉树T的非递归算法（栈）
	SqStack S;
	InitStack(S);
	BiTree p = T;					//初始化p，用来指向二叉树T的根结点
	BiTree q = new BiTNode;		    //申请一块结点空间，用来存放栈顶弹出的元素
 
	while (p || !StackEmpty(S))		//p非空且栈非空
	{
		if (p)						//p非空
		{
			Push(S, p);				//根指针进栈
			p = p->lchild;			//遍历左子树
		}
		else
		{
			Pop(S, q);				//退栈
			cout << q->data << " ";	//访问根结点
			p = q->rchild;			//遍历右子树
		}
	}
	DestoryStack(S);
}

程序执行的结果如下：

【分析】

        在上述程序中，栈S的变化过程如下：

        在遍历二叉树中，因为每个结点都被访问了一次，因此无论是递归还是非递归算法，其时间复杂度都是O(n)。而由上图可知，辅助空间的大小就是树的深度，因此，在最坏情况（树的深度为n的情况）下，空间复杂度也是O(n)。

    之前提到过，除了前序、中序和后序外，还有一种按层次（从上到下，从左到右）遍历二叉树的顺序 —— 层序。在上述二叉树中，如果使用层序遍历，得到的遍历序列是：-*cab。

（另外，层序遍历的算法可以通过队列进行实现。）

---

2. 根据遍历序列确定二叉树

        从之前的探讨中可以得出结论：若二叉树的各结点的值均不同，则任意二叉树结点的先序序列、中序序列和后序序列是唯一的。

        反过来，通过这个结论也可以得出一个推论：由二叉树的先序序列和中序序列（或后序序列和中序序列）能唯一确定一棵二叉树。

        上述推理过程确定了包括根结点在内的三个结点。而如果继续拆分得到的两个子序列，就可以继续取得各个结点，最终就可以得到一棵二叉树。

    同理，也可以由后序序列和中序序列确定唯一的一棵二叉树（后序序列的最后一个结点就是当前的根结点）。

【例子】

        设存在一棵二叉树，有：

• 中序序列：B D C E A F H G
• 后序序列：D E C B H G F A

        要求：画出该二叉树。

【分析】

1. 根据后序序列的特征（根结点必定在后序序列的尾部），可以确定该二叉树的根结点为 A；
2. 由根结点A，将中序序列拆分为两个子序列：

   

3.  将新获得的子序列与后序序列进行元素匹配，得到后序序列中的两个子序列：

   

4.  继而，可以得出：
   1. 在子树DECB中，存在 B 为 A 的左孩子（即B为该子树的根结点）；
   2. 在子树FHG中，存在 F 为 A 的右孩子；
5. 由此，可以继续对子树进行拆分：

   

6. 通过这种方式类推，最终得到一棵二叉树：

   

    由于无法区分左、右子树，因此一棵二叉树的先序序列和后序序列无法唯一确定一棵二叉树。

---

3. 二叉树遍历算法的应用

        作为二叉树各种操作的基础，“遍历” 会因为 访问结点 这一具体操作的不同而产生不同作用。譬如，假设 “访问” 能够判别结点、计数或者生成结点等，就可以解决一些更加实际的问题。

【例子：创建二叉树的存储结构（二叉链表）】

        提示：为了创建二叉树，需要在遍历过程中生成结点。并且约定

• 二叉树中结点的元素均为一个单字符；
• 按先序遍历的顺序建立二叉链表；
• T为指向根节点的指针。

【代码】

void CreateBiTree(BiTree& T)
{//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	
	if (ch == '#')			//递归结束，当前结点为空
		T = NULL;
	else					//递归，创建二叉树
	{
		T = new BiTNode;	//生成当前结点
		T->data = ch;
 
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}
}

    由代码逻辑可知，'#' 代表空结点。

譬如，执行程序，输入 ABC##DE#G##F### ,可以创建二叉树：

------

【例子：复制二叉树】

        要求：复制已有的一棵二叉树，得到与该二叉树完全相同的另一棵二叉树。

【代码】

void Copy(BiTree T, BiTree& NewT)
{//复制一棵和T完全相同的二叉树
	if (T == NULL)				//若为空结点，则当前递归结束
	{
		NewT = NULL;
		return;
	}
	else
	{
		NewT = new BiTNode;
		NewT->data = T->data;	//复制根结点
		Copy(T->lchild, NewT->lchild);		//递归复制右子树
		Copy(T->rchild, NewT->rchild);		//递归复制左子树
	}
}

【分析】

        复制二叉树主要考虑两种情况：

1. 若树T当前结点为空，则NewT对应结点也为空；
2. 若树T当前结点不为空，则NewT需要存在对应结点存储数据。

        类似于遍历二叉树，上述的算法也是进行按照先序进行，按照 ①根结点；②左子树；③右子树 的方式进行浏览。

不推荐的非递归算法：

void Copy(BiTree T, BiTree& NewT)
{//中序遍历二叉树T的非递归算法（栈）
	SqStack S;
	InitStack(S);
	BiTree p = T;
	BiTree q = new BiTNode;
 
	NewT = new BiTNode;
	BiTree r = NewT;
	BiTree s = new BiTNode;
 
	while (p || !StackEmpty(S))
	{
		if (p)						//若p非空
		{
			Push(S, p);				//根指针进栈
			p = p->lchild;			//遍历左子树
 
			Push(S, r);				//将NewT的结点也入栈
			if (p)					//如果该层次是空，则不建立结点
				r->lchild = new BiTNode;
			r = r->lchild;
		}
		else
		{
			Pop(S, s);				//后进先出
			Pop(S, q);				//退栈
			s->data = q->data;
			p = q->rchild;			//遍历右子树
 
			r = NULL;
			if (p)					//若右子树为空，则不建立结点
				s->rchild = new BiTNode;
			r = s->rchild;
		}
	}
	DestoryStack(S);
}

    在遍历二叉树的过程中，递归的层次 ≤ 树的深度，也就是说，递归的层次是有限的。而在相同情况下，如果使用非递归算法，代码不仅会显得麻烦，并且会难以理解。

（ps：如果一定要使用非递归算法，可考虑使用两个栈或者双栈结构。）

------

【例子：计算二叉树的深度】

        二叉树的深度就是树中结点的最大层次（即其左、右子树深度的较大者加1）。

【代码】

int Depth(BiTree T)
{//计算二叉树T的深度
	if (T == NULL)
		return 0;
	else
	{
		int m = Depth(T->lchild);		//递归，计算左子树的深度
		int n = Depth(T->rchild);		//递归，计算右子树的深度
 
		if (m > n)                      //求出两棵子树深度的较大值
			return m + 1;
		else
			return n + 1;
	}
}

        该算法是建立在后序遍历二叉树的算法基础上的（先访问左子树，再访问右子树，最后考虑根结点）。

------

【例子：统计二叉树中结点的个数】

结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1（根结点）

int NodeCount(BiTree T)
{//统计二叉树T中结点的个数
	if (T == NULL)			//若遇到空结点，则返回0
		return 0;
	else					//结点个数通过公式计算得到
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

线索二叉树（Threaded Binary Tree）

        从上述讨论可知，遍历二叉树就是将二叉树中的结点按照一定的规律进行排列，这实际上是对一个非线性结构进行的线性化操作。

        但是，在实际操作中也可以看到：当二叉链表作为存储结构时，结点中只存储左、右孩子信息，而结点在任一序列中的直接前驱和直接后驱是无法得到的。

    如：中序序列a+b*c，其中 “b” 的前驱是 “+” ，后驱是 “*” 。而这种信息只存在于遍历的动态过程中。

        很显然，这在某些时候无法满足程序的需要。

    当然，可以在 每个结点 中增加指针域来存储有关前驱和后驱的信息，但这样做的代价就是结构的存储密度的大幅降低。

        为此，就需要引入线索二叉树的概念，通过它，可以保存那些原本只存在于动态过程中的前驱和后驱信息。

1. 线索二叉树的基本概念

||| 规定：

1. 若结点有左子树，则：
   1. lchild域 将指示其左孩子；
   2. 否则，令 lchild域 指示其前驱。
2. 若结点有右子树，则：
   1. rchild域 将指示其右孩子；
   2. 否则，令 rchild域 指示其后继。

        如图所示：

        二叉树的二叉线索类型定义：

typedef struct BiThrNode
{
	TElemType data;
	struct BiThrNode* lchild, * rchild;		//左、右孩子指针
	int LTag, RTag;							//左、右标志
}BiThrNode, *BiThrTree;

        由此而产生的各种概念：

例如：下图所示为一中序线索链表

        在上图中：

• 虚线作为 线索 ，连接了前驱和后驱。
• 添加了头结点，并且：
  • 头结点的lchild域的指针指向根结点，rchild域的指针指向中序遍历时访问的最后一个结点；
  • 令二叉树中序序列中的 ①第一个结点的lchild域指针，②最后一个结点的rchild域的指针 均指向头结点。

---

2. 构造线索二叉树

        线索二叉树构造的实质：将二叉链表中的空指针改为指向其前驱或后驱的线索。

【代码】

    其中 指针变量pre 是提前设置的全局变量，它始终是 p 的前驱。

① 不带头结点的版本

void InThreading(BiThrTree p)
{
	if (p)
	{
		InThreading(p->lchild);			//左子树递归线索化
 
		if (!p->lchild)					//p的左孩子为空
		{
			p->LTag = 1;				//给p加上做线索
			p->lchild = pre;			//p的左孩子的指针指向前驱（pre）
		}
		else
			p->LTag = 0;
 
		if (!pre->rchild)				//pre的右孩子为空
		{
			pre->RTag = 1;				//给pre加上右线索
			pre->rchild = p;			//pre的右孩子的指针指向后继（p）
		}
		else
			pre->RTag = 0;
 
		pre = p;						//移动pre，令pre始终都是p的前驱
		InThreading(p->rchild);			//右子树递归线索化
	}
}

【注】

        在实际的操作中，若全局变量pre没有被主动分配指向空间，它将默认为一个空指针（NULL）。为此，可以使用new进行动态内存分配；

        另外，在编写代码及测试中，在函数外部无法定义结构体的成员。若要进行测试，可以将结构体pre的变量定义放到主函数内。

---

② 带头结点的版本（需要使用上述的函数InThreading）

void InOrderThreading(BiThrTree& Thrt, BiThrTree T)
{//将二叉树T中序线索化，令 THrt 指向头结点
	Thrt = new BiThrNode;		//建立头结点
	Thrt->LTag = 0;				//由上图可知，头结点有左孩子。若树非空，其左孩子就是树根
	Thrt->RTag = 1;				//存在右线索
	Thrt->rchild = Thrt;		//初始化时，右指针指向自己
 
	if (!T)
		Thrt->lchild = Thrt;	//若树为空，则左指针也指向自己
	else
	{
		Thrt->lchild = T;		//头结点的左孩子指向树根
		pre = Thrt;				
 
		InThreading(T);			//调用函数InThreading，对二叉树T进行中序线索化
 
		pre->rchild = Thrt;		//函数InThreading调用结束时，pre指向最右边的结点
		pre->RTag = 1;
		Thrt->rchild = pre;		//头结点的右线索指向pre
	}
}

---

    由于线索二叉树拥有结点的前驱和后驱的信息，所以相比于普通二叉树的遍历，线索二叉树的遍历及指定结点的查找都变得更加简单。 

3. 遍历线索二叉树

        一般地，如果需要经常查找结点的前驱和后继，会选择采用线索链表作为存储结构。而在不同次序中，结点内部存储地址的含义也会有所不同，为此需要进行分类讨论。

【分类讨论】

    下方所举例子来源于上方的中序线索链表。

（1）在中序线索二叉树中

• 查找指定结点的前驱：

• 查找指定结点的后继：

------

（2）在先序线索二叉树中：

• 查找指定结点的前驱：

• 查找指定结点的后继：

------

（3）在后序线索二叉树中：

• 查找指定结点的前驱：

• 由于比较复杂，需要分类讨论指定结点的后继情况：

        在遇到上述这种查找后继比较复杂的情况时，可以直接使用含4个指针的线索链表。

    由于结点内已经存在了前驱和后继的信息，线索二叉树的遍历就不再需要设栈，因此在时间和空间上都比遍历二叉树节省。接下来的算法就是通过 查找结点的后继 进行线索二叉树的遍历的。

【代码：中序遍历线索二叉树】

void InOrderTraverse_Thr(BiThrTree T)	
{//中序遍历线索二叉树T的非递归算法，其中访问操作就是直接输出
	BiThrNode* p = T->lchild;		//其中，T指向头结点，故p指向根结点
 
	while (p != T)					//当T为空树，或遍历结束时，p == T
	{
		while (p->LTag == 0)		//沿左孩子向下寻找
		{
			p = p->lchild;
		}
		cout << p->data;			//访问（输出）左子树为空的结点
 
		while (p->RTag == 1 && p->rchild != T)
		{
			p = p->rchild;			//通过右线索寻找后继
			cout << p->data;		
		}
		p = p->rchild;				//转向p的右子树
	}
}

【分析】

• 时间复杂度：O(n);
• 空间复杂度：O(1)，因为上述操作未涉及任何堆栈。