根据二叉树的前序遍历和中序遍历结果重建二叉树

根据二叉树的前序遍历和中序遍历的结果重建二叉树，假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

以下为实例程序：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct BinaryTreeNode
  5 {
  6     int m_nValue;
  7     struct BinaryTreeNode* m_pLeft;
  8     struct BinaryTreeNode* m_pRight;
  9 }BinaryTreeNode;
 10 
 11 BinaryTreeNode* ConstructCore(int *startPreorder,int* endPreorder,int* startInorder,int* endInorder);
 12 
 13 //构建二叉树
 14 BinaryTreeNode* 
 15 Construct(int *preorder,int *inorder,int length)
 16 {
 17     if(preorder==NULL || inorder==NULL || length<=0)
 18     {
 19         printf("输入错误！
");
 20         return NULL;
 21     }
 22     else
 23     {
 24         return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1);
 25     }
 26 }
 27 
 28 //构建结点
 29 BinaryTreeNode* 
 30 ConstructCore(int *startPreorder,int *endPreorder,int* startInorder,int* endInorder)
 31 {
 32     //前序遍历的第一个数字是根结点的值
 33     int rootValue=*startPreorder;
 34     BinaryTreeNode *root=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
 35     root->m_nValue=rootValue;
 36     root->m_pLeft=root->m_pRight=NULL;
 37 
 38     //只有一个结点
 39     if(startPreorder==endPreorder)
 40     {
 41         if(startInorder==endInorder&&  *startPreorder==*startInorder)
 42             return root;
 43         else
 44         {
 45             printf("输入错误！
");
 46             exit(0);
 47         }
 48     }
 49 
 50     int *rootInorder=startInorder;
 51     while(rootInorder<=endInorder && *rootInorder!=rootValue)
 52     {
 53         rootInorder++;
 54     }
 55     if(rootInorder==endInorder && *rootInorder!=rootValue)
 56     {
 57         printf("输入错误！
");
 58         exit(0);
 59     }
 60     
 61     //在中序遍历中找到根结点的值
 62     int leftLength=rootInorder-startInorder;
 63     int *leftPreorderEnd=startPreorder+leftLength;
 64     if(leftLength>0)
 65     {
 66         //左子树递归
 67         root->m_pLeft=ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
 68     }
 69     if(leftLength<endPreorder-startPreorder)
 70     {
 71         //右子树递归
 72         root->m_pRight=ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
 73     }
 74     return root;
 75 }
 76 
 77 //后序遍历
 78 void LastOrder(BinaryTreeNode *root,int* lasorder,int* index)
 79 {
 80     if(root!=NULL)
 81     {
 82         if(root->m_pLeft!=NULL){
 83             LastOrder(root->m_pLeft,lasorder,index);
 84         }
 85         if(root->m_pRight!=NULL){
 86             LastOrder(root->m_pRight,lasorder,index);
 87         }
 88         lasorder[*index]=root->m_nValue;
 89         *index=*index+1;
 90     }
 91 }
 92 
 93 int
 94 main(void)
 95 {
 96     int *preorder;
 97     int *inorder;
 98     int *lasorder;
 99     int length;
100     int i;
101     BinaryTreeNode* tree=NULL;
102     int index=0;
103 
104     printf("输入结点数：
");
105     scanf("%d",&length);
106     preorder=(int *)malloc(length*sizeof(int));
107     inorder=(int *)malloc(length*sizeof(int));
108     lasorder=(int *)malloc(length*sizeof(int));
109     printf("输入前序遍历序列：");
110     for(i=0;i<length;i++)
111     {
112         scanf("%d",&preorder[i]);
113     }
114     printf("输入中序遍历序列：");
115     for(i=0;i<length;i++)
116     {
117         scanf("%d",&inorder[i]);
118     }
119     tree=Construct(preorder,inorder,length);
120     if(tree!=NULL)
121     {
122         printf("构造二叉树成功！
");
123 
124     }
125     else{
126         printf("构造二叉树失败！
");
127         return 0;
128     }
129     LastOrder(tree,lasorder,&index);
130     for(i=0;i<length;i++)
131     {
132         printf("%d ",lasorder[i]);
133     }
134     printf("
");
135     return 0;
136 }

前序遍历的第一个值为根结点的值。在中序遍历中找到根结点，左边为左子树，右边为右子树。

运行结果：

不完全二叉树：

完全二叉树：

只有一个结点：

只有右子树：

只有左子树：

前序遍历与中序遍历不匹配：