跳至主要內容

3.二叉树的遍历和线索二叉树

𝓳𝓭𝔂𝓼𝔂𝓪大约 10 分钟

二叉树的遍历

提示

👉史上最全遍历二叉树详解open in new window

leetcode练习

结论

  • 前序序列和中序序列的关系相当于以前序序列为入栈次序,以中序序列为出栈[1][2]
遍历顺序
先序根左右
中序左根右
后序左右根

先序遍历

void PreOrder(BiBree T){
	if(T!=NULL){
	visit(T);
	PreOrder(T->lchild);
	Preorder(T->rchild);
}

中序遍历

void PreOrder(BiBree T){
	if(T!=NULL){
	PreOrder(T->lchild);
	visit(T);
	Preorder(T->rchild);
}

后序遍历

void PreOrder(BiBree T){
	if(T!=NULL){
	PreOrder(T->lchild);
	Preorder(T->rchild);
	visit(T);
}

相关信息

三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)O(n)。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有nn个结点且深度为nn的单支树，遍历算法的空间复杂度为O(n)O(n)。

三种遍历过程示意图

暂时抹去和递归无关的 visit()语句,则整个个遍历算法完全相同,因此,从递归执行过程的角度看先序、中序和后序遍历也是完全相同的。
向下的箭头表示更深一层的递归调用,向上的箭头表示从递归调用退出返回;虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问根结点时输出的信息。例如,由于中序遍历中访问结点是在遍历左子树之后、遍历右子树之前进行的,则带圆形的字符标在向左递归返回和向右递归调用之问。由此,只要沿虚线从1出发到2结束,将沿途所见的三角形(或圆形或方形)内的字符记下,便得到遍历二叉树的先序(或中序或后序)序列。例如,在图5.7 中,沿虚线游走可以分别得到先序序列为ABDEC、中序序列为DBEAC、后序序列为 DEBCA
三种遍历过程示意图

非递归算法

先序

void InOrder2(BiTree T){
	InitStack(S);
	BiTree p = T;
	while(p||!IsEmpty(S)){
		if(p){
			visit(p);
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			p=p->rchild;
		}
	}
}

中序

void InOrder2(BiTree T){
	InitStack(S);
	BiTree p = T;
	while(p||!IsEmpty(S)){
		if(p){
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			visit(p);
			p=p->rchild;
		}
	}
}

后序

后序非递归遍历二叉树是先访问左子树,再访问右子树,最后访问根结点。结合图5.7来分析:

  1. 沿着根的左孩子,依次入栈,直到左孩子为空。此时栈内元素依次为 ABD。
  2. 读栈顶元素:若其右孩子不空且未被访问过,将右子树转执行1;否则,栈顶元素出栈并访问。

在上述思想的第2步中,必须分清返回时是从左子树返回的还是从右子树返回的,因此设定一个辅助指针rr,用于指向最近访问过的结点。也可在结点中增加一个标志域,记录是否己被访问。

void PostOrder(BiTree T){
	InitStack(S);
	BiTNode *p = T;
	BiTnode *r = NULL;
	while(p||!IsEmpty(S)){
		if(p){
			push(S,p);
			p=p->lchild;
		}
		else{
			GetTop(S,p);
			if(p->rchild && p->rchild != r)
				p=p->rchild;
			else{
				pop(S,p);
				visit(p->data);
				r=p;
				p=NULL;
			}
		}
	}
}

注意

每次出栈访问完一个结点就相当于遍历完以该结点为根的子树,需将pp置NUIL。

层次遍历

要进行层次遍历,需要借助一个队列。首先将二叉树根结点入队, 然后出队,访问出队结点,若它有左子树,则将左子树根结点入队:若它有右子树,则将右子树根结点入队。完成入队后出队,访问出队结点⋯⋯如此反复,直至队列为空。

void LevelOrder(BiTree T){
	InitQueue(Q);
	BiTree p;
	Enqueue(Q,T);
	while(!IsEmpty(Q)){
		DeQueue(Q,p);
		visit(p);
		if(p->lchild!=NULL)
			EnQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);
	}
}

由遍历序列构造二叉树

  1. 前序-中序遍历序列
  2. 后序-中序遍历序列
  3. 层序-中序遍历序列

注意

只知道二叉树的先序序列和后序序列,则无法唯一确定一棵二叉树

前序-中序遍历序列

image.png
image.png

后序-中序遍历序列

image.png
image.png

层序-中序遍历序列

image.png
image.png
image.png
image.png

线索二叉树

基本概念

引入线索二叉树是为了加快查找结点前驱和后继的速度

规定:若无左子树,令 lchild 指向其前驱结;若无右子树,令rchild指向其后继结点,还需增加两个标志域标识指针域,以指向左(右)孩子或前驱(后继)[3]

lchildltagdatartagrchild
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;
}ThreadNode,*ThreadTree

以这种结点结构构成的二叉链表作为二叉树的存储结构,称为线索链表,其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。

中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继[4]的线索。而前驱或后继的信息只有在遍历时才能得到,因此线索化的实质就是遍历一次二叉树。

附设指针pre指向刚刚访问过的结点,指针p指向正在访问的结点,即pre指向p的前驱。在中序遍历的过程中,检查p的左指针是否为空,若为空就将它指向 pre;检查 pre 的右指针是否为空,若为空就将它指向p

中序线索二叉树及其二叉链表示
中序线索二叉树及其二叉链表示
void InThread(ThreadTree &p,ThreadTree &pre){
	if(p!=NULL){
		InThread(p->lchild,pre);
		if(p->lchild==NULL){
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){ //此时p已经指向了pre的下一个节点即后继，妙！
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;
		InThread(p->rchild,pre);
	}
}



 
 
 
 
 
 
 
 
 



void CreateInThread(ThreadTree T){
	ThreadTree pre=NULL;
	if(T!=NULL){
		InThread(T,pre);
		pre->rchild=NULL; // 处理遍历的最后一个结点
		pre->rtag=1; 
	}
}




 



提示

为了方便,可以在二叉树的线索链表上也添加一个头结点,令其 lchild 域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点:令二叉树中序序列中的第一个结点的 lchild 域指针和最后一个结点的rchild 域指针均指向头结点。
带头结点的中序线索二叉树

其他线索二叉树的构建

👉视频讲解-5.3二叉树的遍历和线索二叉树open in new window

建立先序线索二叉树和建立后序线索二叉树的代码类似,只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置
先序线索二叉树和后序线索二叉树

注意事项

在前序线索二叉树中存在“转圈问题”，即在访问完一个结点之后，有可能有会去访问左孩子对应的子树，需要在递归前加上限制条件[5]
image.png

中序线索二叉树的遍历

提示

👉5.3.2_3在线索二叉树中找前驱后继open in new window

中序线索二叉树的前驱后继

后继为右子树最左下的结点
image.png

前驱为左子最右下的结点
image.png

中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只要先
找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。在中序线索二叉树中找结
点后继的规律是：若其右标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访
问的结点（右子树中最左下的结点)为其后继。

不含头结点的线索二叉树的遍历算法如下。

  1. 求中序线索二叉树中中序序列下的第一个结点:

找到以P为根的子树中，第一个被中序遍历的结点,循环找到最左下结点（不一定是叶结点）

ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag==0) p=p->lchild;
	return p;
}
  1. 求中序线索二叉树中结点p在中序序列下的后继
ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==0) return Firstnode(p->rchild);
	else return p->rchild;
}
  1. 利用上面两个算法,可以写出==不含头结点的中序线索二叉树的中序遍历的算法==

对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）

void Inorder(ThreadNode *T){
	for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
		visit(p);
}
  1. 求中序线索二叉树中中序序列下的最后结点:

找到以P为根的子树中，最后一个被中序遍历的结点

ThreadNode *Lastnode(ThreadNode *p){
	while(p->rtag==0) p=p->rchild;
	return p;
}
  1. 求中序线索二叉树中结点p在中序序列下的前驱
ThreadNode *Prenode(ThreadNode *p){
	if(p->ltag==0) return Lastnode(p->lchild);
	else return p->lchild;
}
  1. 对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
	for(ThreadNode *p=Lastnode(T);p!=NULL;pPrenode(p))
		visit(p);
}

  1. 参考题目open in new window ↩︎

  2. 都是根节点、左子树、右子树，（注意是入栈） 先序访问后入栈，中序出栈后访问， 则先序序列就是入栈顺序，中序序列就是出栈顺序。 ↩︎

  3. 为0表示指向孩子，为1表示指向前驱后继 ↩︎

  4. 这里的前驱或者后继是根据遍历序列而言的 ↩︎

  5. 后序线索化没有此问题 ↩︎

默认页脚
Copyright © 2023 𝓳𝓭𝔂𝓼𝔂𝓪