数据结构(三)二叉树的遍历

  二叉树的遍历可以分为递归遍历、非递归遍历和层序遍历。其本质是如何把二维结构变成一维线性结构的过程。

递归遍历

  在递归遍历中又可以分为三种：先序遍历、中序遍历和后序遍历。

先序遍历

  先序遍历的遍历过程为：

1. 访问根节点；
2. 先序遍历其左子树；
3. 先序遍历其右子树。

void PreOrderTraversal ( BinTree BT )
{
	if(BT){ // 判断节点是否为空
	printf ("%d'”,BT->Data) ;
	PreOrderTraversal ( BT->Left ) ;
	PreOrderTraversal ( BT->Right );
	}
}

  对于下图中的树，其先序遍历结果为：A B D F E C G H I。

中序遍历

  中序遍历的遍历过程为：

1. 中序遍历其左子树;
2. 访问根结点;
3. 中序遍历其右子树。

void PreOrderTraversal ( BinTree BT )
{
	if(BT){ // 判断节点是否为空
	PreOrderTraversal ( BT->Left ) ;
	printf ("%d'”,BT->Data) ;
	PreOrderTraversal ( BT->Right );
	}
}

  对于下图中的树，其先序遍历结果为：D B E F A G H C I。

后序遍历

  后序遍历的遍历过程为：

1. 后序遍历其左子树;
2. 后序遍历其右子树;
3. 访问根结点。.

void PreOrderTraversal ( BinTree BT )
{
	if(BT){ // 判断节点是否为空
	PreOrderTraversal ( BT-> Left ) ;
	PreOrderTraversal ( BT-> Right );
	printf ("%d'”,BT->Data) ;
	}
}

  对于下图中的树，其先序遍历结果为：D E F B H G I C A。

  先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同。

  下图中在从入口到出口的曲线上用×号、星号和三角三种符号分别标记出了先序、中序和后序访问各结点的时刻：

非递归遍历

  上述方法是使用递归的算法对其进行求解，我们知道递归的方法算法空间复杂度较高，如果采用非递归的方法，我们可以使用堆栈的方法。

中序遍历非递归遍历算法

  中序遍历非递归遍历算法主要可以分为以下三步：

1. 遇到一个结点，就把它压栈，并去遍历它的左子树；
2. 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
3. 然后按其右指针再去中序遍历该结点的右子树。

  其程序如下：

void InOrderTraversal ( BinTree BT )
{ 	BinTree T = BT;
	stack s = Creatstack( Maxsize ); /* 创建并初始化堆栈s*/
	while( T || !IsEmpty(S) ) {
		while (T) { ( /*--直向左并将沿途结点压入堆栈*/
			Push(S,T) ;
			T = T->Left;
		}
		if(!IsEmpty (S) )T
			T = Pop(s); /*结点弹出堆栈*/
			printf ("%5d", T->Data); /* (访问)打印结点*/
			T = T->Right; /*转向右子树*/
		}
	}
}

  若想要把其改为先序遍历的非递归算法，只需把printf语句放到while(T)下面这一行：

void InOrderTraversal ( BinTree BT )
{ 	BinTree T = BT;
	stack s = Creatstack( Maxsize ); /* 创建并初始化堆栈s*/
	while( T || !IsEmpty(S) ) {
		while (T) { ( /*--直向左并将沿途结点压入堆栈*/
			printf ("%5d", T->Data); /* (访问)打印结点*/
			Push(S,T) ;
			T = T->Left;
		}
		if(!IsEmpty (S) )T
			T = Pop(s); /*结点弹出堆栈*/
			T = T->Right; /*转向右子树*/
		}
	}
}

层序遍历

  二叉树遍历的核心问题就是：二维结构的线性化。其实我们只需要一个存储结构来保存暂时不访问的结点就可以了，因此除了堆栈，我们还可以用队列的方式对其进行存储。

  队列实现：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。

  层序遍历基本过程：先根结点入队，然后：

1. 从队列中取出一个元素;
2. 访问该元素所指结点;
3. 若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。

void Leve lOrderTraversal ( BinTree BT )
{ Queue Q ; BinTree T ;
	if ( !BT ) return; /* 若是空树则直接返回*/
	Q =CreatQueue( Maxsize ); /*创建并初始化队列0*/
	AddQ(Q，BT);
	while(!IsEmptyQ(Q)){
		T=DeleteQ(Q);
		printf ("&d\n", T->Data) ; /*访 问取出队列的结点*/
		if ( T->Left ) AddQ( Q，T->Left ) ;
		if ( T->Right ) AddQ( Q，T->Right ) ;
	}
}

应用

• 输出二叉树中的叶子结点

  遍历二叉树的应用：输出二叉树中的叶子结点。在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”。

void PreOrderPrintLeaves( BinTree BT )
{
	if(BT) {
		if ( !BT-Left && !BT- >Right )
			printf ("8d"，BT- >Data ) ;
		PreOrderPrintLeaves ( BT- >Left ) ;
		PreOrderPrintLeaves ( BT- >Right ) ;
	}
}

• 求二叉树的高度：

int PostorderGetHeight( BinTree BT )
{	int HL, HR，MaxH;
	if(BT){
		Hi = PostorderGetHeight (BT->Ieft) ; /*求左子树的深度*/
		HR = PostorderGetHeight (BT->Right) ; /*求右子树的深度*/
		MaxH = (HI > HR) ? HL : HR; /*取左右子树较大的深度*/
		return ( MaxH + 1 ); /*返回树的深度*/
	}
	else return 0; /*空树深度为0 */
}

  如果想要由两种遍历序列确定二叉树，必须要有中序遍历才行。