学步园

遍历二叉树常用的三种方式：
先序(根、左、右)
中序(左、根、右)
后序(左、右、根)
如图1所示：

1．先序遍历递归过程
      若二叉树为空遍历结束，否则：
    （1）访问根结点；
    （2）先序遍历根结点的左子树；
    （3）先序遍历根结点的右子树。
void PreOrder(BT *T)      		//先序遍历二叉树BT
{  
	if(T= =NULL)  				//递归调用的结束条件
		return;    	
    else
	{ 
		printf(T->data);      		// 输出结点的数据域
		Preorder(T->lchild);   	       // 先序递归遍历左子树
		Preorder(T->rchild);   	       // 先序递归遍历右子树
    }
}
图1先序遍历的序列为：
            A B D G C E F H
2．中序遍历递归过程
    若二叉树为空遍历结束，否则：
  （1）中序遍历根结点的左子树；
  （2）访问根结点；
  （3）中序遍历根结点的右子树。
void InOrder(BT *T) 	         // 中序遍历二叉树BT
{ 
	if(T = =NULL) 
		return;    	　    // 递归调用的结束条件
	else
	{
		Inorder(T->lchild);      	　    //  中序递归遍历左子树
		printf(T->data);       	　  // 输出结点的数据域
		Inorder(T->rchild);                // 中序递归遍历右子树
	}
}
图1中序遍历的序列为：
       D G B A E C H F
3．后序遍历递归过程
    若二叉树为空遍历结束，否则：
  （1）后序遍历根结点的左子树；
  （2）后序遍历根结点的右子树。
  （3）访问根结点；
void PostOrder(BT *T)          	// 后序遍历二叉树BT
{ 
	if(T = =NULL) 
		return; 	            // 递归调用的结束条件
    else
	{
		Postorder(T->lchild);    	           // 后序递归遍历左子树  
		Postorder(T->rchild);   	          // 后序递归遍历右子树
		printf(T->data);                        // 输出结点的数据域
    }
}
图1后序遍历的序列为：
              G D B E H F C A