一本通-1340：【例3-5】扩展二叉树

【题目描述】

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

【输入】

扩展二叉树的先序序列。

【输出】

输出其中序和后序序列。

【输入样例】

ABD..EF..G..C..

【输出样例】

DBFEGAC DFGEBCA

---

#include <bits/stdc++.h>

using namespace std;

class Tree
{
    struct TreeNode {
        char ch;
        TreeNode *left, *right;
        TreeNode(char x): ch(x), left(NULL), right(NULL) {}
    };
    TreeNode *root;
    int pos;

    void build(const string & s, TreeNode *& root)
    {
        if (s[++pos] != '.') {
            root = new TreeNode(s[pos]);
            build(s, root -> left);
            build(s, root -> right);
        }
        else root = NULL;
    }

    void inorderTraversal(TreeNode *root)
    {
        if (root) {
            inorderTraversal(root -> left);
            cout << root -> ch;
            inorderTraversal(root -> right);
        }
    }

    void postorderTraversal(TreeNode *root)
    {
        if (root) {
            postorderTraversal(root -> left);
            postorderTraversal(root -> right);
            cout << root -> ch;
        }
    }

    void makeEmpty(TreeNode *& root)
    {
        if (root) {
            makeEmpty(root -> left);
            makeEmpty(root -> right);
            delete root;
            root = NULL;
        }
    }

public:
    Tree(): root(NULL), pos(-1) {}

    ~Tree() { makeEmpty(root); }

    void build(const string & s){ build(s, root); }

    void inorderTraversal() { inorderTraversal(root); }

    void postorderTraversal() { postorderTraversal(root); }
};


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    cin >> s;
    Tree obj;
    obj.build(s);

    obj.inorderTraversal();
    cout << endl;
    obj.postorderTraversal();
    cout << endl;

    return 0;
}