二叉树的遍历方法

二叉树先序递归遍历

 1 int PreOrderTraverse(bitree T)
 2 {
 3     bitree p=T;
 4     if(p)
 5     {
 6         cout<<p->data<<' ';
 7         traverse(p->lchild);
 8         traverse(p->rchild);
 9     }
10 }

二叉树先序非递归遍历（顺序队列实现）

int PreOrderTraverse(bitree T)
{
    bitree a[100];   
    int rear,front;
    rear=front=0;
    a[++rear]=T;
    while(rear!=front)
    {
        bitree p=a[++front];
        cout<<p->data<<' ';
        if(p->lchild)
            a[++rear]=p->lchild;
        if(p->rchild)
            a[++rear]=p->rchild;
    }
}

二叉树中序非递归遍历（顺序栈实现）

int Traverse(bitree T)            /*栈实现遍历*/
{
    bitree stack[1000];
    int top=0;
    bitree p=T;
    while(p!=NULL||top>0)
    {
        while(p!=NULL)
        {
            stack[top++]=p;        /*先将左子树入栈，然后根据每个左子树访问他们的右子树*/
            p=p->lchild;
        }
        if(top>0)            /*访问右子树*/
        {
            p=stack[--top];
            printf("%2c",p->data);
            p=p->rchild; 
        }
    }
}

二叉树先序非递归遍历（顺序栈实现）

 1 int Traverse(bitree T)            /*栈实现遍历*/
 2 {
 3     bitree stack[1000];
 4     int top=0;
 5     bitree p=T;
 6     while(p!=NULL||top>0)
 7     {
 8         while(p!=NULL)
 9         {
10             printf("%2c",p->data);
11             stack[top++]=p;
12             p=p->lchild;
13         }
14         if(top>0)
15         {
16             p=stack[--top];
17             p=p->rchild; 
18         }
19     }
20 }

二叉树中序遍历

1 int Traverse(bitree T)    
2 {
3     if(T)
4     {
5         Traverse(T->lchild);
6         printf("%2c",T->data);
7         Traverse(T->rchild);
8     }
9 }

二叉树后续遍历

1 int Traverse(bitree T)            
2     if(T)
3     {
4         Traverse(T->lchild);
5         Traverse(T->rchild);
6         printf("%2c",T->data);
7     }
8 }