先序中序后序遍历二叉树_一颗二叉树的先序序列和后序序列正好相反，该二叉树的形态是什么？...

今天我们主要介绍二叉树的遍历算法，在开始正文之前请首先思考一下下面这个问题：

问：若一颗二叉树的先序序列和后序序列正好相反，该二叉树的形态是什么？

答案：文末揭晓

一二叉树的四种遍历方法

二叉树的遍历是指按照一定次序访问树中所有节点，并且每个节点仅被访问一次的过程。下面我们介绍四种遍历二叉树的方法：

先序遍历

先序遍历二叉树的过程是：

访问根节点；
先序遍历左子树；
先序遍历右子树；

先序遍历的递归算法：

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); // 访问根节点
    }
}

层次遍历算法

对于一颗二叉树，从根节点开始，按照从上到下，从左到右的顺序访问每一个节点。每一个节点只访问一次。

解决思路：

1. 使用一个队列, 先将根节点进队；

2. 队不空时循环 : 从队列中出列一个节点*p ，访问它；

若有左孩子节点，将左孩子节点进队；

若有右孩子节点，将右孩子节点进队。

对应的代码如下：

void LevelOrder(BTNode *b)
{ BTNode *p;
 BTNode *qu[MaxSize]; // 定义环形队列, 存放节点指针
int front, rear; // 定义队头和队尾指针
 front=rear=0; // 置队列为空队列
 rear++;
 qu[rear]=b; // 根节点指针进入队列
while (front!=rear) // 队列不 为 空循环
 { front=(front+1)%MaxSize;
  p=qu[front]; // 队头出队列
printf("%c ",p->data); // 访问节点
if (p->lchild!=NULL) // 有左孩子时将其进队
  {  rear=(rear+1)%MaxSize;
   qu[rear]=p->lchild;
  }  if (p->rchild!=NULL) // 有右孩子时将其进队
  { rear=(rear+1)%MaxSize;
   qu[rear]=p->rchild;
  }
 }
}//算法的时间复杂度为O(n)。