二叉树的先序遍历的递归定义如下：
如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：
（1）访问根结点。
（2）先序遍历左子树。
（3）先序遍历右子树。
在二叉树先序的遍历过程中，对每一棵二叉树重复执行以上的递归遍历操作，就可以得到先序序列。例如，在遍历根结点A的左子树
{B,D,E,G,H,I}时，根据先序遍历的递归定义，先访问根结点B，然后遍历B的左子树为{D,G}，最后遍历B的右子树为{E,H,I}。访问过
B之后，开始遍历B的左子树{D,G}，在子树{D,G}中，先访问根结点D，因为D没有左子树，所以遍历其右子树，右子树只有一个结点G，所以访问G。
B的左子树遍历完毕，按照以上方法遍历B的右子树。最后得到结点A的左子树先序序列：B、D、G、E、H、I。
依据二叉树的先序递归定义，可以得到二叉树的先序递归算法。
void PreOrderTraverse(BiTree T)
/*先序遍历二叉树的递归实现*/
{
if(T)
/*如果二叉树不为空*/
{
printf(“%2c”,T->data); /*访问根结点*/
PreOrderTraverse(T->lchild); /*先序遍历左子树*/
PreOrderTraverse(T->rchild); /*先序遍历右子树*/
}
}
二叉树的先序遍历非递归算法实现如下。
void PreOrderTraverse(BiTree T)
/*先序遍历二叉树的非递归实现*/
{
BiTree stack[MaxSize];
/*定义一个栈，用于存放结点的指针*/
int top;
/*定义栈顶指针*/
BitNode *p;
/*定义一个结点的指针*/
top=0;
/*初始化栈*/
p=T;
while(p!=NULL||top>0)
{
while(p!=NULL)
/*如果p不空，访问根结点，遍历左子
树*/
{
printf(“%2c”,p->data); /*访问根结点*/
stack[top++]=p; /*将p入栈*/
p=p->lchild; /*遍历左子树*/
}
if(top>0)
/*如果栈不空*/
{
p=stack[--top]; /*栈顶元素出栈*/
p=p->rchild; /*遍历右子树*/
}
}
}
以上算法是直接利用数组来模拟栈的实现，当然也可以定义一个栈类型实现。如果用第四章的链式栈实现，需要将数据类型改为指向二叉树结点的指针类
型。
评论