学步园

二叉树的遍历，根据根节点位置的不同，可分为前序遍历(PreOrder)、中序遍历(MidOrder)和后序遍历(PostOrder)。所谓的前、中、后，指的是根所在的位置。以前序遍历为例，根与左右子树的输出次序为：根、左、右。

二叉树对应的结构体类型如下：

<pre name="code" class="cpp">typedef struct node{
int data;  //数据域
struct node  *left; //左孩子指针
struct node  *right; //右孩子指针
}BiTree;

下面介绍前序遍历的方法：

1、递归实现

void PreOrder(BiTree *tp)
{
if(tp==NULL)//节点为空
return;
else
{
printf("%5d",tp->data);//输出根节点.就三句代码。如果把这句放到中间，那就是中序遍历；放到最后，就是后序遍历
PreOrder(tp->left);//前序遍历左子树
PreOrder(tp->right);//前序遍历右子树
}
}

说明 ：因为树的定义就是递归的，用递归方法遍历，十分地简明易懂，但效率却不高，要是面试的时候，通常会被要求写非递归方法，因此掌握下面的遍历方法十分必要

2、非递归方法实现

//其实递归调用是要用到栈的（隐式的）。不使用函数递归的调用，就得显式地使用栈。可以自己定义一个一维数组，作栈用。

void PreOrder(BiTree *tp)
{
BiTree *p;//工作指针，用于遍历
BiTree *stack[MAXSIZE];//栈定义，其实就是个指针数组，用于存放指针变量。具体大小看个人情况吧，就不写具体数字了
int top=-1;//定义并初始化栈顶指针 
  if(tp==NULL)//同样地，要判断输入节点是否为空
<span style="white-space:pre">	</span>return ;
  else
  {
   top++;
   stack[top]=tp;
   while(top>-1)
   {
    p=stack[top];
    top--;
    printf("%5d",p->data);
   if(p->right)
   {
    top++;
    stack[top]= p->right;
   }
   if(p->left)
   {
    top++;
    stack[top]=p->left;
   }//这里关键是栈是先进后出的，则想要让右子树后打印，就得让右子树先入栈
  }//while
 }//else
}//至于中序遍历、后序遍历，就自己动下脑筋，写出来吧。