二叉树:两种遍历序列确定另一种遍历序列

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

先序序列: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;
}

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注