欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

中序遍历序列和 后序遍历序列重建二叉树

程序员文章站 2022-03-24 16:07:08
...
//中序区间为【inL,inR】 ,后序区间为【postL,postR】,返回根节点 
  node *creat(int postL,int postR,int inL,int inR)
 {
 	if(postL>postR)
 	{
 		return NULL;
	 }
	node *root=new node;
	root->data=post[postR];
	int k;
	for(int i=inL;i<=inR;i++)
	{
		if(post[postR]==in[i])
		{
			k=i;
			break;
		}
	}
	int numleft=k-inL;     //根据数量去划分左右子树 
	root->lchild=creat(postL,postL+numleft-1,inL,k-1);
	root->rchild=creat(postL+numleft,postR-1,k+1,inR);
	return root;
 }
相关标签: 数据结构