# 二叉树的遍历

XAMPP相关 461浏览

1. 先序（根）遍历(preorder traversal)

（1）访问根结点

（2）先序遍历左子树

（3）先序遍历右子树

2. 中序遍历(inorder traversal)

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

3. 后序（根）遍历(postorder traversal)

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点

4. 层次遍历(level traversal)

（1）访问根结点(第1层)

（2）从左到右访问第2层的所有结点

（3）从左到右访问第3层的所有结点，……，第h层的所有结点。

5. 算法实现

``````//先序遍历的递归算法
``````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);
``````    }
````}````