Postorder + inorder sequence to construct binary tree

Postorder + inorder sequence to construct binary tree

Input sample:

The length of the input sequence in the first line is n, the input of n characters in the second line indicates the sequence of binary tree post-order traversal, and the input of n characters in the third line indicates the sequence of binary tree in-order traversal

9
GHDBEIFCA
GDHBAECIF

Sample output:

Outputs a sequence of binary tree preorder traversals.

ABDGHCEFI

source code

 

#include <bits/stdc++.h>
using namespace std;

int nodeNum;
string hou, zhong;

typedef struct treeNode
{
    char data;
    treeNode *left;
    treeNode *right;
} TreeNode;

void printTest(TreeNode *treeRoot, int zhongLeft, int zhongRight, int houLeft, int houRight, int pos, int leftLen)
{
    cout << "*************************************" << endl;
    cout << "treeRoot.data = " << treeRoot->data << endl;
    cout << "leftTree : " << endl;
    cout << "   zhong : ";
    for (int i = zhongLeft; i <= pos - 1; ++i)
    {
        cout << zhong[i];
    }
    cout << endl;
    cout << "   hou : ";
    for (int i = houLeft; i <= houLeft + leftLen; ++i)
    {
        cout << hou[i];
    }
    cout << endl;
    cout << "rightTree : " << endl;
    cout << "   zhong : ";
    for (int i = pos + 1; i <= zhongRight; ++i)
    {
        cout << zhong[i];
    }
    cout << endl;
    cout << "   hou : ";
    for (int i = houLeft + leftLen + 1; i <= houRight - 1; ++i)
    {
        cout << hou[i];
    }
    cout << endl;
    cout << "*************************************" << endl;
}

treeNode *build(int zhongLeft, int zhongRight, int houLeft, int houRight)
{

    if (zhongLeft > zhongRight || houLeft > houRight)
    {
        // cout << t++ << endl;
        return nullptr;
    }
    else
    {
        TreeNode *treeRoot = new TreeNode();
        treeRoot->data = hou[houRight];
        int pos = zhong.find(hou[houRight]);
        int leftLen = pos - 1 - zhongLeft;

        printTest(treeRoot, zhongLeft, zhongRight, houLeft, houRight, pos, leftLen);

        treeRoot->left = build(zhongLeft, pos - 1, houLeft, houLeft + leftLen);
        treeRoot->right = build(pos + 1, zhongRight, houLeft + leftLen + 1, houRight - 1);
        return treeRoot;
    }
}

void xianRead(TreeNode *tree)
{
    if (tree)
    {
        cout << tree->data;
        xianRead(tree->left);
        xianRead(tree->right);
    }
}

int main()
{
    // cout << "begin" << endl;
    cin >> nodeNum;

    cin >> hou >> zhong;

    // cout << "nodeNum = " << nodeNum << endl;
    // cout << "hou = " << hou << endl;
    // cout << "zhong = " << zhong << endl;

    TreeNode *tree = build(0, zhong.size() - 1, 0, hou.size() - 1);

    xianRead(tree);

    return 0;
}

Summarize

nonsense

At that time, when I was learning data structure, I was often emphasized that a word related to trees used recursion.

Now that I am learning algorithms, I understand that recursion is always combined with divide and conquer, so I seem to understand a little more about using the phrase recursion for tree-related issues.

The tree structure seems to be designed for recursion. Recursion is used to solve the divide-and-conquer problem. The divide-and-conquer problem is the same as the structure of the problem. The difference is the scale of the problem. That is, a problem, when the scale of the problem is small, we can solve it, but when the scale of the problem is large, it is not easy to solve. But if this problem can be disassembled into multiple sub-problems of the same structure that are smaller than the problem, then this problem can be solved by a divide-and-conquer method. Trees are like this. A big tree is composed of two small sub-trees, and each small sub-tree is also a tree alone, so it is more comfortable to solve the tree problem with recursive divide and conquer.

back to this topic

1. The general idea is to generate a tree structure based on the results of in-order traversal and post-order traversal, and then perform pre-order traversal on the tree to print the results. (I always feel that it is possible not to generate a tree structure, and directly print out the results of pre-order traversal based on the results of post-order traversal and in-order traversal, but I haven't thought about that at the moment).

2. Imagine, when n==1: that is, this tree has only one root node, and then the title gives the results of post-order traversal and in-order traversal of this tree. Will you construct this tree? The answer is yes, your job is to apply for a piece of memory to represent the root node, store the unique node data in it, and then solve the problem.

3. Push it up, when n==3: Let’s clarify this question first, and I want to use the divide and conquer method to solve it. The question now is, how do I resolve this n==3 problem into several n==1 problems. First of all, the root node is easy to determine, and the last character of the postorder traversal is the root node. In addition to this, we only need to find the post-order traversal and in-order traversal sequences of the left subtree of this tree. Barbara looking for rules.

Tags: Algorithm data structure

Posted by Topsy Turvey on Sun, 20 Nov 2022 02:17:57 +0300