preface

Binomial tree traversal and reconstruction of binomial tree is a classic problem, but also the main events often test content (especially PAT and ladder), the following I will combine my own learning experience and brush the experience of a simple talk about binomial tree traversal and reconstruction

Binary tree traversal

There are usually three kinds of binary tree traversal, which are preorder, middle order, and postorder traversal. Remember, before, in, and after are the positions of the root node, and the root node in front is the previous order traversal… And so onOn closer inspection, it’s not hard to learn that at the code level, it’s just the location of the output statement

Let’s do a problem

Tree Walk Aizu – ALDS1_7_C

Write a program based on the following algorithm to access all nodes of a given binary tree. 1. Output node numbers in the order of root node, left subtree, and right subtree. This is called a preordering walk of the tree. 2. Output node numbers in the left subtree, root node, and right subtree sequence. This is called in-order traversal of a binary tree. 3. Output node numbers in the order of left subtree, right subtree, and root node. This is called a back-order traversal of a binary tree. Let a given binary tree have n nodes, numbered 0 to N-1.

Input

In the first line, enter the number of nodes n. The next n lines are one line for each node in the following format. Id Left Right INDICATES the node ID. Left indicates the number of the left child node, and right indicates the number of the right child node. There is no child node whose left(right) is -1.

Output

The first line prints “Preorder”, and the second line prints the node number in the sequence traversed in the preceding order. The third line prints “Inorder”, and the fourth line prints the node number in the order traversed in. The fifth line prints “Postorder”, and the sixth line prints the node number in the traversal sequence. One space is displayed before the node number.

Examples

Sample Input 1 9 0 1 4 1 2 3 2 -1 -1 3 -1 -1 4 5 8 5 6 7 6 -1 -1 7 -1 -1 8 -1 -1 Sample Output 1 Preorder 0 1 2 3 4 5 6 7 8 Inorder 2 1 3 0 6 5 7 4 8 Postorder 2 3 1 6 7 5 8 4 0

Hint

1 ≤ n ≤ 25

The question:

Give the information (ID, left, right) of each node of the binary tree, and output the previous order, the order, the order after the traversal results

Answer key:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int NIL = - 1;
const LL maxn = 1e4;

struct node{intp, l, r; }T[maxn];void preOrder(int n){
    if(n==NIL) return;
    printf(" %d",n);
    preOrder(T[n].l);
    preOrder(T[n].r);
}
void inOrder(int n){
    if(n==NIL) return;
    inOrder(T[n].l);
    printf(" %d",n);
    inOrder(T[n].r);
}
void PostOrder(int n){
    if(n==NIL) return;
    PostOrder(T[n].l);
    PostOrder(T[n].r);
    printf(" %d",n);
}
int main(a)
{
    int N, v, l, r, root;
    scanf("%d",&N);
    for(int i = 0; i <= N; i++) T[i].p=NIL;
    for(int i = 0; i < N; i++){
        scanf("%d%d%d",&v,&l,&r);
        T[v].l = l, T[v].r = r;
        if(l! =NIL) T[l].p = v;if(r! =NIL) T[r].p = v; }for(int i = 0; i < N; i++)
        if(T[i].p==NIL)
            root = i;
    printf("Preorder\n");
    preOrder(root);
    printf("\nInorder\n");
    inOrder(root);
    printf("\nPostorder\n");
    PostOrder(root);
    printf("\n");
	return 0;
}
Copy the code

Binary tree reconstruction

The reconstruction of the binary tree is a very common type, is usually given in the preamble of binary tree and sequence traversal sequence after, or in the given sequence before and after the sequence traversal sequence (but not given before sequence after sequence in sequence, unable to complete) this kind of thinking a little clever, if temporarily don’t understand the classmate can also write down the template, is very common. For example, given pre = {1,2,3,4,5}, in = {3,2,4,1,5}, in = {3,2,4,1,5}, in = {3,2,4,1,5}, in = {3,2,4,1,5}, in = {3,2,4,1,5}, in = {3,2,4,1,5} The right side of the subscript must be the right subtree of the point, using this principle, we can recurse in turn. The template as follows

int N, pre[maxn], in[maxn], post[maxn];
int postPos = 1, prePos = 1;
void rec(int l, int r){
    if(l >= r) return;
    // The next node of pre
    int c = pre[prePos++], m;
    // the position of c in
    for(int i = 1; i <= N; i++)
        if(in[i] == c){
            m = i; break;
        }
    rec(l, m);  // Rebuild the left subtree
    rec(m+1, r);// Reconstruct the right subtree
    post[postPos++] = c;
}
Copy the code

Similarly can be obtained, given the order and order before order traversal, traversal post from the back to the front, at the same time the output order should be changed

int N, pre[maxn], in[maxn], post[maxn];
int postPos = N, prePos = 1;
void rec(int l, int r){
    if(l >= r) return;
    // The next node to post
    int c = post[postPos--], m = 0;
    // the position of c in
    for(int i = 1; i <= N; i++)
        if(in[i] == c){
            m = i; break;
        }

    rec(m+1, r);// Reconstruct the right subtree
    rec(l, m);  // Rebuild the left subtree
    pre[prePos++] = c;
}
Copy the code

Let’s do an example

Reconstruction of a Tree

Write a program which reads two sequences of nodes obtained by the preorder tree walk and the inorder tree walk on a binary tree respectively, and prints a sequence of the nodes obtained by the postorder tree walk on the binary tree.

Input

In the first line, an integer n, which is the number of nodes in the binary tree, is given. In the second line, the sequence of node IDs obtained by the preorder tree walk is given separated by space characters. In the second line, the sequence of node IDs obtained by the inorder tree walk is given separated by space characters.

Every node has a unique ID from 1 to n. Note that the root does not always correspond to 1.

Output

Print the sequence of node IDs obtained by the postorder tree walk in a line. Put a single space character between adjacent IDs.

Examples

Sample Input 1 5 1 2 3 4 5 3 2 4 1 5 Sample Output 1 3 4 2 5 1 Sample Input 2 4 1 2 3 4 1 2 3 4 Sample Output 2 4 3 2 1

Hint

1 n 40 or less or less






The question:

The fore-order and middle-order traversal of N nodes tree are given, and the post-order traversal is obtained

Answer key:

The template can be directly set, but remember that N should be slightly larger

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 45;

int N, pre[maxn], in[maxn], post[maxn];
int postPos = 1, prePos = 1;
void rec(int l, int r){
    if(l >= r) return;
    // The next node of pre
    int c = pre[prePos++], m;
    // the position of c in
    for(int i = 1; i <= N; i++)
        if(in[i] == c){
            m = i; break;
        }
    rec(l, m);  // Rebuild the left subtree
    rec(m+1, r);// Reconstruct the right subtree
    post[postPos++] = c;
}
int main(a)
{
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> pre[i];
    for(int i = 1; i <= N; i++)
        cin >> in[i];

    rec(1, N+1);// The right edge is slightly larger
    cout << post[1];
    for(int i = 2 ; i <= N; i++)
        cout << "" << post[i];
    cout << endl;
	return 0;
}


Copy the code

Reference blog: blog.csdn.net/CSDN___CSDN…