中序先序（后序）遍历二叉树构建二叉树

中序遍历二叉树得到的结果是先左子树，然后根节点，然后右子树的顺序，所以，中序遍历的结果即为各个节点在整个树中的顺序。

建树的具体思路为，我们根据先序遍历的结果可以知道，先序遍历根节点后面紧跟的是左子树，右子树，只要知道哪些是左子树的，哪些是右子树的即可完成划分，这样就可以形成一个递归的过程。

由中序遍历可知，我们可以知道根节点和左子树第一个节点在树中的位置的顺序，相减即可知道左子树的大小（n），这样在先序遍历的结果中，后n位都为左子树。右子树则在当前的start_point + n + 1处开始。左子树的start_point和当前的一样（子树的左子树和子树在同一点开始）。右子树的大小为上当前的大小减去左子树的大小再减去1（根节点一个）。

下面为中序遍历和先序遍历合成的代码：

#include <stdio.h>

#include <stdlib.h>



struct node

{

    node *left;

    node *right;

    int value;

    node(int v) : value(v), left(NULL), right(NULL){};

};



int tree_index[256]; //各个元素在中序遍历时在树中的位置。



void map_index(int *indorder, int n)

{

    for (int i = 0; i < n; ++i)

    {

        tree_index[indorder[i]] = i;

    }

}



node *merge(int *pre, int size, int start_point) //size表示该节点以及节点的子树一共有多少节点，start_point表示该子树在树中开始的位置（由中序遍历得出）

{

    if (size == 0)

        return NULL;

    int root_value = pre[0];

    int left_size = tree_index[root_value] - start_point;

    node *root = new node(root_value);

    root->left = merge(pre + 1, left_size, start_point);

    root->right = merge(pre + left_size + 1, size - 1 - left_size, start_point + left_size + 1);

    return root;

}



void post_print(struct node *root)

{

    if(root == NULL)

        return;

    post_print(root->left);

    post_print(root->right);

    printf("%d \n",root->value);    

}



int main()

{

    int pre[] = {7, 10, 4, 3, 1, 2, 8, 11};

    int in[] = {4, 10, 3, 1, 7, 11, 8, 2};

    int size = sizeof(in) / sizeof(int);

    map_index(in, size);

    struct node * root = merge(pre, size, 0);

    post_print(root);

    return 0;

}

同理可得，由后序遍历和中序遍历合成二叉树类似。

左子树的start_point和根节点的start_point一样，右子树的start_point为根节点的start_point+n+1，左子树的size为根节点的位置减去start_point，右子树的size为当前的size减去左子树的size减去一。

和先序遍历合成不同的是，每次移动后序遍历数组的下标。先序遍历的左子树为当前元素下标的后面一个，右子树的下标为当前节点下标+n+1。后序遍历的左子树下标为当前节点的前一个，（不想用我贫瘠的文字写了，我还是直接上代码吧）。

#include <cstdio>

#include <cstdlib>



struct node

{

    node *left;

    node *right;

    int value;

    node(int v) : value(v), left(NULL), right(NULL){};

};



int tree_index[256];



void index(int size, int *inorder)

{

    for (int i = 0; i < size; i++)

    {

        tree_index[inorder[i]] = i;

    }

}



node *merge(int *post, int size, int start_point)

{

    if (size == 0)

        return NULL;

    int root_value = post[size - 1];

    int left_size = tree_index[root_value] - start_point;

    node *root = new node(root_value);

    ;

    root->left = merge(post, left_size, start_point);

    root->right = merge(post + left_size, size - 1 - left_size, start_point + left_size + 1);



    return root;

}



void pre_print(node *root)

{

    if (root == NULL)

        return;

    printf("%d \n", root->value);

    pre_print(root->left);

    pre_print(root->right);

}



int main()

{

    int post[] = {4, 1, 3, 10, 11, 8, 2, 7};

    int in[] = {4, 10, 3, 1, 7, 11, 8, 2};

    int size = sizeof(in) / sizeof(int);

    index(size, size);

    struct node *root = merge(post, size, 0);

    pre_print(root);

    return 0;

}