二叉树-3

Posted on | Post modified: | In
Words count in article: 1,276 | Reading time ≈ 5

-遍历二叉树

二叉树的遍历
所谓二叉树的遍历，是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且只被访问一次。
由二叉树的递归定义可知，遍历一颗二叉树便要决定对根结点N，左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）、后序（LRN）三种遍历算法。

先序遍历
先序遍历的操作过程为：
如果二叉树为空，什么也不做。否则：
1.访问根结点
2.先序遍历左子树
3.先序遍历右子树

对应的递归算法如下：

1
2
3
4
5
6
7
void PreOrder(BiTree T){
	if(T!=NULL){               
		visit(T);              //访问根结点 
		PreOrder(T->lchild);   //递归遍历左子树
		PreOrder(T->rchild);   //递归遍历右子树
	}
}

中序遍历
中序遍历的操作过程为：
如果二叉树为空，什么也不做。否则：
1.中序遍历左子树
2.访问根结点
3.中序遍历右子树

对应的递归算法如下：

1
2
3
4
5
6
7
void Inorder(BiTree T){
	if(T!=NULL）
		Inorder(T->lchild);   //递归遍历左子树
		visit(T);             //访问根结点  
		Inorder(T->rchild);   //递归遍历右子树
	}
}

后序遍历
后序遍历操作过程为：
如果二叉树为空，什么也不做。否则：
1.后序遍历左子树
2.后序遍历右子树
3.访问根结点

对应的递归算法如下：

1
2
3
4
5
6
7
void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

不管是哪种便利算法，每个结点都只访问一次，时间复杂度都是O（n）

递归算法与非递归算法的转换
可以借助栈，将二叉树的递归算法转换成非递归算法

以中序遍历为例，给出非递归算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrder2(BiTree T){
	//二叉树中序遍历的非递归算法，算法需要借助一个栈
	InitStack(S);                 //初始化栈
	BiTree p=T;                   //p是遍历指针
	while(p||!IsEmpty(s)){        //栈不空或p不空时循环
		if(p){                    //根指针进栈，遍历左子树
			Push(S,p);            //没遇到非空二叉树先向左走
			p=p->lchild;
		}
		else{                     //根指针退栈，访问根结点，遍历右子树  
			Pop(S,p);             //退栈，访问根结点 
			visit(p);              
			p=p->rchild;          //再向右子树走
		}
	}
}

先扫描（并非访问）根结点的所有左结点并将它们一一进栈。然后出战一个结点p（显然结点p没有左孩子结点或者左孩子结点均已访问过），则访问它。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。
显然，非递归算法的执行效率要高于递归算法。

层次遍历
二叉树的层次遍历，即按照箭头所指方向，按照1,2,3,4的层次顺序，对二叉树中各个结点进行访问。
要进行层次遍历，需要借助一个队列。先将二叉树的结点入队，然后出队，访问该结点，如果它有左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。然后出队，对出队结点进行访问，如此反复，直到队列为空。

二叉树的层次遍历算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
	}
}

由遍历序列构造二叉树
由二叉树的先序序列和中序序列可以唯一地确定一颗二叉树，在先序遍历序列中，第一个结点一定是二叉树的根结点，而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列就是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这颗二叉树。
同理，由二叉树的后序序列和中序序列也可以唯一地确定一颗二叉树，因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，就可以得到一颗二叉树。

Thanks for your reward！