Informatics Olympiad 1340: [example 3-5] extended binary tree

【 Topic link 】

ybt 1340：【 example 3-5】 Expand the binary tree

【 Topic test site 】

1. Binary tree

【 Their thinking 】

solution 1：

use getchar() or cin.get() Read one character at a time .
The format of the preorder sequence is ：< Root node > < The first sequence of the left subtree > < The precedence sequence of the right subtree >
A binary tree can be constructed recursively ：

1. Read in a character , As the root node
2. Recursive construction of left subtree
3. Recursively build the right subtree
4. Connect the left and right subtrees under the root node of this tree , Return the address of the root node

After building the tree , Then output the middle order and post order traversal sequence of this tree .

【 Solution code 】

solution 1：

#include <bits/stdc++.h>
using namespace std;
struct Node// Binary tree node 
{
    
    char val;
    int left, right;
};
Node node[1000];// Node pool 
int p = 1;
void inOrder(int r)// In the sequence traversal 
{
    
    if(r != 0)
    {
    
        inOrder(node[r].left);
        cout << node[r].val;
        inOrder(node[r].right);
    }
}
void postOrder(int r)// After the sequence traversal  
{
    
    if(r != 0)
    {
    
        postOrder(node[r].left);
        postOrder(node[r].right);
        cout << node[r].val;
    }
}
int createTree(char val)// Pass in the value of the root of the binary tree to be generated , Returns the address of the generated binary tree 
{
    
    int np;
    if(val == '.')
        return 0;
    else
    {
    
        np = p++;
        node[np].val = val;
        node[np].left = createTree(cin.get());// Read in character , Build the left subtree 
        node[np].right = createTree(cin.get());// Read in character , Build the right subtree 
        return np;
    }
}
int main()
{
    
    int root = createTree(cin.get());
    inOrder(root);
    cout << endl;
    postOrder(root);
    return 0;
}