앞 순서와 중간 순서 트리, 뒤 순서와 중간 순서 트리

귀속을 이용하여 두 갈래 나무를 구축할 때 주로 전순과 중순, 후순과 중순의 관계를 분명히 한 다음에 귀속적으로 아래로 구축해야 한다. 먼저 현재 노드의 왼쪽 아이를 세우고 오른쪽 아이를 만들어야 한다. 그리고 나는 다른 서열을 이용하여 여러 차례 구축된 두 갈래 나무가 정확한지 검증한다.

#include 
#include 
using namespace std;
const int maxn = 35;
int in[maxn];
int pre[maxn];
struct node {
    int data;
    node *lchild;
    node *rchild;
};


//inOrder preOrder   
/*
    inOrder: 12 11 20 17 1 15 8 5
    preOrder: 1 11 12 17 20 5 8 15
*/
// or
//
//use the inOrder and preOrder create the binary tree
node *Create(int preL, int preR, int inL,int inR) {
    if ( preL > preR ) return NULL;
    node *root = new node();
    root->data = pre[preL];
    int index;
    for ( index = inL; index <= inR; index++ ) {
        if ( in[index] == pre[preL] )break;
    }
    int numLeft = index - inL;
    root->lchild = Create(preL+1, preL+numLeft, inL, index-1);
    root->rchild = Create(preL+numLeft+1, preR, index+1, inR);
    return root;
}


void PostOrderTraversal(node *root) {
    if ( root != NULL ) {
        PostOrderTraversal(root->lchild);
        PostOrderTraversal(root->rchild);
        cout << root->data << " ";
    }
}
int main() {
    int n;
    cin >> n;


    for ( int i = 0 ; i < n; i++ ) {
        cin >> in[i];
    }
    for ( int i = 0; i < n; i++ ) {
        cin >> pre[i];
    }
    node *root;
    root = Create(0,n-1,0,n-1);


    PostOrderTraversal(root);


    return 0;
}

#include 
#include 
using namespace std;
const int maxn = 35;
int in[maxn];
int post[maxn];
struct node {
    int data;
    node *lchild;
    node *rchild;
};
//inOrder postOrder    
/*
    inOrder:12 11 20 17 1 15 8 5
    postOrder:12 20 17 11 15 8 5 1
*/
// use the inOrder and postOrder create the binary tree
//
node *Create(int postL, int postR, int inL, int inR) {
    if ( postL > postR ) return NULL;
    node *root = new node();
    root->data = post[postR];
    int index;
    for ( index = inL; index <= inR; index++ ) {
        if ( in[index] == post[postR] )break;
    }
    int numLeft = index - inL;
    root->lchild = Create(postL, postL+numLeft-1, inL, index-1);
    root->rchild = Create(postL+numLeft, postR-1, index+1, inR);
    return root;
}
void PreOrderTraversal(node *root) {
    if ( root != NULL ) {
        cout << root->data << " ";
        PreOrderTraversal(root->lchild);
        PreOrderTraversal(root->rchild);
    }
}
int main() {
    int n;
    cin >> n;
    for ( int i = 0 ; i < n; i++ ) {
        cin >> in[i];
    }
    for ( int i = 0; i < n; i++ ) {
        cin >> post[i];
    }
    node *root;
    root = Create(0,n-1,0,n-1);
    PreOrderTraversal(root);
    return 0;
}

Java Edition 내차순 및 후차순 세그먼트 트리

import java.util.Scanner;

public class Main {
    final static int MAXN = 100;
    static int[] in = new int[MAXN];
    static int[] post = new int[MAXN];
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        for (int i = 0; i < n; i++) {
            in[i] = input.nextInt();
        }
        for (int i = 0; i < n; i++) {
            post[i] = input.nextInt();
        }
        node root = Create(0, n-1, 0, n-1);
        PreOrderTraversal(root);
    }
    private static void PreOrderTraversal(node root) {
        // TODO Auto-generated method stub
        if (root != null) {
            System.out.print(root.data+" ");
            PreOrderTraversal(root.lchild);
            PreOrderTraversal(root.rchild);
        }
    }

    private static node Create(int postL, int postR, int inL, int inR) {
        // TODO Auto-generated method stub
        if (postL > postR) return null;
        node root = new node();
        root.data = post[postR];
        int index;
        for (index = inL; index <= inR; index++) {
            if (in[index] == post[postR]) break;
        }
        int numLeft = index - inL;
        root.lchild = Create(postL, postL+numLeft-1, inL, index-1);
        root.rchild = Create(postL+numLeft, postR-1, index+1, inR);
        return root;
    }
}
class node {
    public int data;
    node lchild;
    node rchild;
}