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

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

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