[递归]给定前序、中序遍历序列，重构二叉树

#include
#include "bintree.cc"

using namespace std;
int pre_seq[]={2,4,7,6,3,1,5};
int in_seq[]={4,7,6,2,1,5,3};


/*

给定前序（前根）遍历序列 pre_seq 和中序（中根）遍历序列in_seq,

重构这个长得很怂的二插树。


         2
        / \
       /   \
       4    3
        \   /
         7 1
          \ \
           6 5
*/

// 前序序列索引，用以依次取出各层子树的根


static int pre_seq_index=0;





// isi_left: inorder sequence index left boundary
// isi_right: inorder sequence index right boundary
BinTreeNode<int> *BuildTree(int isi_left, int isi_right)
{
    
    if(isi_left>isi_right) return NULL;
    int root_value=pre_seq[pre_seq_index];
    pre_seq_index++;
    
    BinTreeNode<int>* node=new BinTreeNode<int>(root_value);
    if(isi_left==isi_right)
    {
        return node;
    }
 
    int i;
    for(i=isi_left; in_seq[i]!=root_value; i++);
    
    node->_left=BuildTree(isi_left, i-1);
    node->_right=BuildTree(i+1, isi_right);
  
    return node;
}

int main()
{
    BinTree<int> new_tree(BuildTree(0,6));
    cout<<"Tree reconstructed PreOrder:"<<endl;
    new_tree.PreOrder();
    cout<<endl;
    cout<<"Tree reconstructed InOrder:"<<endl;
    new_tree.InOrder();
    cout<<endl;

}

输出结果为：

Tree reconstructed PreOrder:
2 4 7 6 3 1 5
Tree reconstructed InOrder:
4 7 6 2 1 5 3