4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序、按照先序遍历左子树再遍历右子树的原则,常见的遍历次序有先序(NLR)、中序遍历(LNR)和后序遍历(LRN)三种遍历算法。其中,序指的是根结点在何时被访问。

1、先序遍历(PreOrder)

如果二叉树为空,什么也不做,否则: 1)访问根结点

2)先序遍历左子树

3)先序遍历右子树

void preOrder(BiTree T){
	if(T!=null){
		visit(T);//访问根结点
		preOrder(T->lchild);//递归遍历左子树
		predOrder(T-rchild);//递归遍历右子树
	}
}

2、中序遍历(InOrder)

如果二叉树为空,什么也不做,否则:

1)中序遍历左子树

2)访问根结点

3)中序遍历右子树

void inOrder(BiTree T){
	if(T!=null){
		inOrder(T->lchild);//递归遍历左子树
		visit(T);//访问根结点
		inOrder(T-rchild);//递归遍历右子树
	}
}

3、后序遍历(PostOrder)

如果二叉树为空,什么也不做,否则:

1)后序遍历左子树

2)访问根结点

3)后序遍历右子树

void postOrder(BiTree T){
	if(T!=null){
		postOrder(T->lchild);//递归遍历左子树
		postOrder(T-rchild);//递归遍历右子树
		visit(T);//访问根结点
	}
}

三种遍历算法中递归遍历左、右子树的顺序是固定的,只是访问根结点的顺序不同。

不管采用哪种算法,每个结点都访问一次仅访问一次,故时间复杂度都是O(n)。在递归算法中,递归工作栈的栈深恰好为树的深度,所以在最坏的情况下,二叉树是有n个结点且深度为n的单支树,遍历算法的时间复杂度为O(n).

4、递归算法和非递归算法的转化

可以借助栈,将二叉树的递归遍历算法转化为非递归算法,下面以中序遍历为例给出中序遍历的非递归算法。先扫描(并非访问)根结点的所有左节点并将它们一一进栈,然后出栈一个结点*p(显然结点*p没有左孩子结点或左孩子结点均已访问过),访问它。然后扫描该结点的右孩子结点,将其进栈,再扫描该右孩子结点的所有左结点并一一进栈,如此继续,直到栈空为止

void inOrder2(BiTree T){
//二叉树中序遍历的非递归算法,算法需要借助一个栈
	initStack(s);//初始化栈;
	while(p||isEmpty(s)){//p是遍历指针,栈不空或p不空时循环
		IF(P){//p不空时
			push(s,p);//根指针进栈
			p=p->lchild;//每遇到非空二叉树,先向左走
		}else{
			pop(s,p);//根指针退栈
			visit(p);//访问根结点
			p=p->rchild;//再向右子树走
		}
	}
}

5、层次遍历

要进行层次遍历需要借助一个队列,现将二叉树根结点入队,然后出队,访问该结点,如果它由左子树,则将左子树根结点入队;如果它有右子树,则将右子树根结点入队。然后出队,对出队结点访问,如此反复,直到队列为空。

void levelOrder(BiTree T){
	initQueue(Q);//初始化辅助队列;
	BiTree p;
	EnQueue(Q,T);//将根结点入队
	while(!isEmpty(Q)){//队列不空循环
		DeQueue(Q,P);//队头元素出队
		visit(p);//访问当前p所指向结点
		if(p->lchild!=null){
			Enqueue(Q,p->lchild);//左子树不空,则左子树入队列
		}
		if(p->rchild!=null){
			Enqueue(Q,p->rchild);//右子树不空,则右子树入队列
		}
	}
}

6、由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树,在先序遍历序列中,第一个结点一定是二叉树的根结点,而在中序遍历中,根结点必然将中序序列分割称两个子序列,前一个子序列就是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点时右子树的根结点。如此递归地进行下去,便能唯一地确定这课二叉树。

同理,由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树,因为后序序列的最后一个结点如同先序序列的第一个结点,可以将中序序列分割成两个子序列,然后采用类似的方法递归地进行划分,就可以得到一棵二叉树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

834110
来自专栏深度学习思考者

二叉树的遍历、查找、插入以及删除

二叉树的主要存储方式是链接存储,标准存储结构也称为二叉链表。 二叉链表结点类的定义 struct Node{ Node *left, *right;...

407100
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

15830
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

9630
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

18850
来自专栏琯琯博客

PHP二叉树(三):红黑树

32940
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

31850
来自专栏F_Alex

数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树

12420
来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

22450
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

27330

扫码关注云+社区

领取腾讯云代金券