一、 已知先序和中序遍历序列，求后序遍历序列

先序序列：ABDECF
中序序列：DBEAFC

步骤：

1. 由先序序列确定根结点A
2. 由中序序列确定根结点A的左子树（DBE）和右子树（FC）
3. 对于根结点A的左子树，有：
   先序序列：BDE
   中序序列：DBE
   对于根结点A的右子树，有：
   先序序列：CF
   中序序列：FC
   分别对左右子树递归进行1-3步，直至左右子树为空

构建二叉树

最后得后序序列：DEBFCA

二、 已知中序和后序遍历序列，求先序遍历序列

中序序列：DBEAFC
后序序列：DEBFCA

步骤：

1. 由后序序列确定根结点A
2. 由中序序列确定根结点A的左子树（DBE）和右子树（FC）
3. 对于根结点A的左子树，有：
   中序序列：DBE
   后序序列：DEB
   对于根结点A的右子树，有：
   中序序列：FC
   后序序列：FC
   分别对左右子树递归进行1-3步，直至左右子树为空

构建二叉树

最后得先序序列：ABDECF

三、 已知先序和后序遍历序列

这种情况无法唯一确定一颗二叉树，例如：

先序序列：ABC
后序序列：CBA
中序序列：CBA、BCA、ACB、ABC

四、代码实现

#include <iostream>

using namespace std;

/* 二叉树结点 */
struct Node
{
    char data;
    Node* lchild;
    Node* rchild;

    Node():lchild(nullptr),rchild(nullptr){};
};


/* 递归创建二叉树 */
Node* rCreate(char data, Node* lchild, Node* rchild)
{
    Node* root = new Node;
    root->data = data;
    root->lchild = lchild;
    root->rchild = rchild;

    return root;
}


/* 由先序和中序序列，建立二叉树
 * 参数：先序序列、中序序列、序列长度
 * 返回值：当前树的根结点
 */
Node* CreateA(char* preSeq, char* inSeq, int len)
{
    int rootIndex = 0;
    Node* root = nullptr;

    if(len == 0) return nullptr;
    else if(len == 1)
    {
        root = new Node;
        root->data = *preSeq;
        return root;
    }

    while(*preSeq != inSeq[++rootIndex]);
    //递归创建左子树
    Node* lchild = CreateA(preSeq+1, inSeq, rootIndex);
    //递归创建右子树
    Node* rchild = CreateA(preSeq+rootIndex+1, inSeq+rootIndex+1, len-rootIndex-1);

    return rCreate(*preSeq, lchild, rchild);
}


/* 由中序和后序序列，建立二叉树
 * 参数：中序序列、后序序列、序列长度
 * 返回值：当前树的根结点
 */
Node* CreateB(char* inSeq, char* postSeq, int len)
{
    int rootIndex = 0;
    Node* root = nullptr;

    if(len == 0) return nullptr;
    else if(len == 1)
    {
        root = new Node;
        root->data = *inSeq;
        return root;
    }

    while(postSeq[len-1] != inSeq[++rootIndex]);
    //递归创建左子树
    Node* lchild = CreateB(inSeq, postSeq, rootIndex);
    //递归创建右子树
    Node* rchild = CreateB(inSeq+rootIndex+1, postSeq+rootIndex, len-rootIndex-1);

    return rCreate(postSeq[len-1], lchild, rchild);
}


/* 先序遍历二叉树 */
void preOrderTraverse(Node* root)
{
    if(root)
    {
        cout << root->data;
        preOrderTraverse(root->lchild);
        preOrderTraverse(root->rchild);
    }
}


/* 后序遍历二叉树 */
void postOrderTraverse(Node* root)
{
    if(root)
    {
        postOrderTraverse(root->lchild);
        postOrderTraverse(root->rchild);
        cout << root->data;
    }
}


/* 后序遍历删除二叉树 */
void DeleteTree(Node* root)
{
    if(root)
    {
        DeleteTree(root->lchild);
        DeleteTree(root->rchild);
        delete root;
    }
}


int main()
{
    char preSeq[] = "ABDECF";
    char inSeq[] = "DBEAFC";
    char postSeq[] = "DEBFCA";
    Node* btreeA = nullptr;
    Node* btreeB = nullptr;

    //由先序和中序序列构建二叉树
    btreeA = CreateA(preSeq, inSeq, 6);
    //输出后序序列
    postOrderTraverse(btreeA);

    cout << endl;

    //由中序和后序序列构建二叉树
    btreeB = CreateB(inSeq, postSeq, 6);
    //输出先序序列
    preOrderTraverse(btreeB);

    //删除二叉树
    DeleteTree(btreeA);
    DeleteTree(btreeB);

    return 0;
}

作者：Wray Zheng
原文：http://www.codebelief.com/article/2016/12/binary-tree-traversal-sequence/

相关文章

• 彻底理解二分查找及其边界情况