c语言实现二叉树的恢复

根据二叉树的先序和中序序列恢复二叉树的递归思想是：先根据先序序列的第一个节点建立根节点，然后在中序序列中找到该节点，从而划分处根节点的左右子树的中序序列。接下来再在先序序列中确定左右子树的先序序列，并由左子树的先序序列与中序序列继续递归建立左子树，由左子树的先序序列继续递归建立右子树。

根据二叉树的中序和后序序列恢复二叉树的递归思想是：先根据后序序列的最后一个节点建立根节点，然后在中序序列中找到该节点，从而划分处根节点的左右子树的中序序列。接下来再在先序序列中确定左右子树的先序序列，并由左子树的先序序列与中序序列继续递归建立左子树，由左子树的先序序列继续递归建立右子树。

下面是我的一个实例，供参考，有什么问题，在下方留言，我们一起探讨。

#include<stdio.h>
#include<stdlib.h>

struct BinaryTree
{
int data;
BinaryTree *lchild,*rchild;
};

BinaryTree *CreateTree()
{
BinaryTree *root;

root = (BinaryTree*)malloc(sizeof(BinaryTree));
root = NULL;

return root;
}

//由先序和中序恢复二叉树
void Pre_in_order(char *pred,char *ind,int i,int j,int k,int h,BinaryTree **root)
{
//i,j和k,h分别为当前子树的先序序列和中序序列的下上界
int m;

*root = (BinaryTree*)malloc(sizeof(BinaryTree));
(*root)->data = pred[i];//根据pred数组生成二叉树的根节点

m = k ;//m指向ind数组的中序序列的第一个节点
while(ind[m] != pred[i])//找到根节点在中序序列中的所在位置
{
m++;
}

if(m == k)
{
//根节点是中序序列的第一个节点时则无左子树
(*root)->lchild = NULL;
}
else
{
/*//检查错误
int a1,a2,b1,b2;
a1 = i+1;
a2 = i+m-k;
b1 = k;
b2 = m-1;

printf("\n--1--%d %d %d %d\n",a1,a2,b1,b2);*/

//根据根节点所划分出中序序列的两个部分继续构造左右两颗子树
Pre_in_order(pred,ind,i+1,i+m-k,k,m-1,&(*root)->lchild);
}

if(m == h)
{
//根节点时中序序列的两个部分的最后一个节点时则无右子树
(*root)->rchild = NULL;
}
else
{
////检查错误
//int a1,a2,b1,b2;
//a1 = i+m-k+1;
//a2 = j;
//b1 = m+1;
//b2 = h;

//printf("\n--2--%d %d %d %d\n",a1,a2,b1,b2);

//根据根节点所划分出中序序列的两个部分继续构造左右两颗子树
Pre_in_order(pred,ind,i+m-k+1,j,m+1,h,&(*root)->rchild);
}

}

//由中序和后序恢复二叉树
void In_post_order(char *ind,char *post,int l1,int r1,int l2,int r2,BinaryTree **root)
{
//l1,r1和l2,r2分别为当前子树的中序序列和后序序列的下上界
int m;

*root = (BinaryTree*)malloc(sizeof(BinaryTree));
(*root)->data = post[r2];//根据post数组生成二叉树的根节点(后序序列最后一个数)

m = l1;//m指向ind数组的中序序列的第一个节点
while(ind[m] != post[r2])//找到根节点在中序序列中的所在位置
{
m++;
}

//根节点是中序序列的第一个节点时则无左子树
if(m == l1)
{
(*root)->lchild = NULL;
}
else
{
//根据根节点所划分出中序序列的两个部分继续构造左右两颗子树
////检查错误
//int a1,a2,b1,b2;
//a1 = l1;
//a2 = m-1;
//b1 = l2;
//b2 = l2+m-l1-1;

//printf("\n--1--%d %d %d %d\n",a1,a2,b1,b2);

In_post_order(ind,post,l1,m-1,l2,l2+m-l1-1,&(*root)->lchild);
}

//根节点时中序序列的两个部分的最后一个节点时则无右子树
if(m == r1)
{
(*root)->rchild = NULL;
}
else
{
/*//检查错误
int a1,a2,b1,b2;
a1 = m+1;
a2 = r1;
b1 = l2+m-l1;
b2 = r2-1;

printf("\n--2--%d %d %d %d\n",a1,a2,b1,b2);
*/
//根据根节点所划分出中序序列的两个部分继续构造左右两颗子树
In_post_order(ind,post,m+1,r1,l2+m-l1,r2-1,&(*root)->rchild);
}
}

void PostTree(BinaryTree *root)
{
if(root)
{
PostTree(root->lchild);
PostTree(root->rchild);

printf("%c ",root->data);
}
}

int main()
{
BinaryTree *tree;

tree = CreateTree();

char pred[10] = {'f','d','b','a','c','e','g','i','h','j'};
char ind[10] = {'a','b','c','d','e','f','g','h','i','j'};
char post[10] = {'a','c','b','e','d','h','j','i','g','f'};

printf("先序和中序恢复结果:\n");
Pre_in_order(pred,ind,0,9,0,9,&tree);

PostTree(tree);
printf("\n\n");

printf("中序和后序恢复结果:\n");
In_post_order(ind,post,0,9,0,9,&tree);

PostTree(tree);
printf("\n");

return 0;
}

运行结果: