数据结构之二叉树的遍历

																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																				@[TOC](数据结构之二叉树的遍历)

  数据结构是程序设计的重要基础，它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。
  数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储称为存储结构(或物理结构)。数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类，其中，非线性结构又可分为树结构和图结构。
  树结构是一种非常重要的非线性结构，该结构中的一个数据元素可以有两个或两个以上的直接后继元素，树可以用来描述客观世界中广泛存在的层次结构关系。
  二叉树是 n(n≥0)个结点的有限集合，它或者是空树(n=0)，或者是由一个根结点及两棵不相交的且分别称为左、右子树的二叉树所组成。可见，二叉树具有递归性质。
  遍历是按某种策略访问树中的每个结点，且仅访问一次的过程。由于二叉树所具有的递归性质，一棵非空的二叉树是由根结点、左子树和右子树三部分构成的，因此若能依次遍历这三部分，也就遍历了整棵二叉树。按照先遍历左子树后遍历右子树的约定，根据访问根结点位置的不同，可得到二叉树的先序、中序和后序3种遍历方法。此外，对二叉树还可进行层序遍历。
  【函数】二叉树的先序遍历。

void PreOrder(BiTree root){
   
	if (root != NULL) {
   
		printf("%d", root->data);	/*访问根结点*/
		PreOrder(root->lchild);		/*先序遍历根结点的左子树*/
		PreOrder(root->rchild);		/*先序遍历根结点的右子树*/
	}/*if*/
}/*PreOrder*/

  【函数】二叉树的中序遍历。

void InOrder(BiTree root){
   
	if (root != NULL){
   
		InOrder(root->lchild);		/*中序遍历根结点的左子树*/
		printf("%d", root->data);	/*访问根结点*/
		InOrder(root->rchild);		/*中序遍历根结点的右子树*/
	}/*if*/
}/*InOrder*/

  【函数】二叉树的后序遍历

void PostOrder(BiTree root){
   
	if(root != NULL) {
   
		PostOrder(root->lchild);	/*后序遍历根结点的左子树*/
		PostOrder(root->rchild);	/*后序遍历根结点的右子树*/
		printf("%d", root->data);	/*访问根结点*/
	}/*if*/
}/*PostOrder*/

  从根结点出发，3种方法的遍历路线如下图所示。该路线从根结点出发，逆时针沿着二叉树的外缘移动，对每个结点均途经三次。若第一次经过结点时进行访问，则是先序遍历；若第二次（或第三次）经过结点时访问结点，则是中序遍历（或后序遍历）。因此，只要将遍历路线上所有在第一次、第二次和第三次经过的结点信息分别输出，即可分别得到该二叉树的先序、中序和后序遍历序列。所以，若去掉 3 种遍历算法中的打印输出语句，则3种遍历方法相同。这说明3种遍历过程的路线相同。

  遍历二叉树的基本操作就是访问结点，不论按照哪种次序遍历，对于含有 n 个结点的二叉树，遍历算法的时间复杂度都为 O(n)。因为在遍历的过程中，每进行一次递归调用，都是将函数的“活动记录”压入栈中，因此，栈的最大长度恰为树的高度。所以，在最坏情况下，二叉树是有n个结点且高度为n的单枝树，遍历算法的空间复杂度也为(n)。
  借助于一个栈，可将二叉树的递归遍历算法转换为非递归算法。下面给出中序遍历的非递归算法。
  【函数】二叉树的中序非递归遍历算法。

int InOrderTraverse(BiTree root){
   			/*二叉树的非递归中序遍历算法*/
	BiTree p;
	InitStack(St);							/*创建一个空栈*/
	p=root;									/*p指向树根结点*/
	while (p != NULL || !isEmpty(St)) {
   
		if (p!= NULL) {
   						/*不是空树*/
			Push(St, p);					/*根结点指针入栈*/
			p = p->lchild;					/*进入根的左子树*/
		} else {
   
			q=Top(St);	Pop(St);			/*栈顶元素出栈*/
			printf("%d", q->data);			/*访间根结点*/
			p = q->rchild;					/*进入根的右子树*/
		}/*if*/
	}/*while*/
}/*InOrderTraverse*/

  遍历二叉树的过程实质上是按一定的规则将树中的结点排成一个线性序列的过程，因此遍历操作得到的是树中结点的一个线性序列。在每一种序列中，有且仅有一个起始点和一个终结点，其余结点有且仅有唯一的直接前驱和直接后继。显然，关于结点的前驱和后继的讨论是针对某一个遍历序列而言的。
  对二叉树还可以进行层序遍历。设二叉树的根结点所在的层数为1，层序遍历就是从树的根结点出发，首先访问第一层的树根结点，然后从左到右依次访问第二层上的结点，其次是第三层上的结点，依此类推，自上而下、自左至右逐层访问树中各结点的过程就是层序遍历。
  【算法】二叉树的层序遍历算法。

void LevelOrder(BiTree root){
   		/*二叉树的层序遍历算法*/
	BiTree p;
	InitQueue(Q);					/*创建一个空队列*/
	EnQueue(Q, root);				/*将根指针加入队列*/
	while (!isEmpty(Q)){
   			/*队列不空*/
		DeQueue(Q, p);				/*队头元素出队，并使p取队头元素的值*/
		printf("%d", p->data);		/*访问结点*/
		if (p->lchild)	EnQueue(p->lchild);
		if (p->rchild)	EnQueue(p->rchild);
	}/*while*/
}/*LevelOrder*/