二叉树的遍历

//先序遍历的递归算法
void PreOrder(BTNode *b)
{
if(b != NULL)
    {
printf("%c ", b->data);  //访问跟结点
        PreOrder(b->lchild);    //先序遍历左子树
        PreOrder(b->rchild);    //先序遍历右子树
    }
}

//中序遍历的递归算法
void InOrder(BTNode *b)
{
if(b != NULL)
    {
        InOrder(b->lchild); //中序遍历左子树
printf("%c ", b->data);
        InOrder(b->rchild); //中序遍历右子树
    }
}

//后序遍历的递归算法
void PostOrder(BTNode *b)
{
if(b != NULL)
    {
        PostOrder(b->lchild);   //后序遍历左子树
        PostOrder(b->rchild);   //后序遍历右子树
printf("%c ", b->data);
    }
}

typedef struct
{
    BTNode *data[MaxSize];
int top;
}SqStack;
//非递归实现先序遍历1
void PreOrder1(BTNode *b)
{
    BTNode *p;
    SqStack *st;    //定义栈指针
    InitStack(st);  //初始化栈
if(b != NULL)
    {
        Push(st, b);    //根节点进栈
while (!StackEmpty(st)) 
        {
            Pop(st, p); //退根节点p并访问它
printf("%c", p->data);
if (p->rchild != NULL)  //有右孩子时将其进栈
                Push (st, p->rchild);
if (p->lchild != NULL)  //有左孩子时将其进栈
                Push (st, p->lchild);
        }
printf("    ");
    }
 
   DestroyStack (st);  //销毁栈
}

//非递归实现先序遍历2
void PreOrder2(BTNode *b)
{
    BTNode *p;
    SqStack *st;
    InitStack (st);
    p = b;
while (!StackEmpty(st) || p != NULL)
    {
while (p != NULL)   //访问结点p及其所有左下结点并进栈
        {
printf ("%c", p->data);
            Push (st, p);
            p = p->lchild;
        }
if (!StackEmpty(st))    //
        {
            Pop (st, p);    //出栈p
            p = p->rchild;  //转向处理其右子树
        }
    }
printf ("   ");
    DestroyStack (st);
}

//中序遍历的非递归算法
void InOrder1(BTNode *b)
{
BTNode *p;
SqStack *st;
InitStack (st);
p = b;
while (!StackEmpty (st) || p != NULL)
{
while (p != NULL)   //扫描结点p的所有坐下结点并进栈
{
Push (st, p);
p = p->lchild;
}
if (!StackEmpty (st))   
{
Pop (st, p);
printf ("%c", p->data);
p = p->rchild;  //转向处理其右孩子结点
}
}
printf ("   ");
DestroyStack (st);
}

//后序遍历的非递归算法
void PostOrder1(BTNode *b)
{
    BTNode *p, *r;
bool flag;
    SqStack *st;
    InitStack (st);
    p = b;
do
    {
while (p != NULL)   //扫面结点p的所有左下结点并进栈
        {
            Push (st, p);
            p = p->lchild;  //移动到左孩子
        }
        r = NULL;   //r指向刚访问的结点，初始时为空
        flag = true;    //flag为真表示正在处理栈顶结点
while  (!StackEmpty (st) && flag)
        {
            GetTop (st, p);
if (p->rchild == r) //若结点p的右孩子为空或者为刚刚访问的结点
            {
printf ("%c", p->data);
                Pop (st, p);
                r = p;  //r指向刚刚访问的结点
            }
else
            {
                p = p->rchild;  //转向处理其右子树
                flag = false;   //表示当前不是处理栈顶结点
            }
        }

    }
while (!StackEmpty (st));   //栈不空循环
printf ("   ");
    DestroyStack (st);
}

//层次遍历
typedef struct
{
    BTNode *data[MaxSize];
int front, rear;
}SqQueue;   //顺序队类型

void LevelOrder(BTNode *b)
{
    BTNode *p;
    SqQueue *qu;    //定义 环形队列 指针
    InitQueue (qu);
    enQueue (qu, b);    //根节点指针进队
while (!QueueEmpty (qu))
    {
        deQueue (qu, p);    //出队结点p
printf ("%c", p->data);
if (p->lchild != NULL)  //有左孩子时将其进队
            enQueue (qu, p->lchild);
if (p->rchild != NULL)  //有右孩子时将其进队
            enQueue (qu, p->rchild);
    }
}