二叉树的先序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作： （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;                                      /*遍历右子树*/     } } } 以上算法是直接利用数组来模拟栈的实现，当然也可以定义一个栈类型实现。如果用第四章的链式栈实现，需要将数据类型改为指向二叉树结点的指针类 型。

评论