层序遍历(队列实现）

实现过程

• 从队列中取出一个元素；
• 访问该元素所指结点；
• 若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。

不断执行这三步操作，直到队列为空，再无元素可取，二叉树的程序遍历就完成了。

void LevelorDerTraversal(BinTree BT)
{
    Queue Q;
    BinTree T;

    if(!BT)
        return;/* 若是空树则直接返回 */

    Q = CreatQueue();	/* 创建空队列 */
    AddQ(Q, BT);
    while(!IsEmpty(Q))
    {
        T = DeteleQ(Q);
        printf("%d",T->Data); /* 访问取出队列的结点 */
        if(T->Left)
            AddQ(Q, T->Left);
        if(T->Right)
            AddQ(Q, T->Right);
    }
}

3、由遍历序列还原二叉树

已知先序遍历和中序遍历，可以还原二叉树；
已知中序遍历和后序遍历，可以还原二叉树；
已知先序遍历和后序遍历，不可以还原二叉树.

a.已知先序遍历和中序遍历还原二叉树

算法思路：
1、根据先序遍历结果确定根节点。先序遍历的第一个节点为根节点。
2、 在中序遍历结果中找到根节点，根节点左侧的部分为左子树节点，根节点右侧的部分为右子树节点。
3、 将中序遍历的结果按根节点分为两部分，迭代的执行第一步和第二步，直到还原整个二叉树。