1.理论依据：

具体情况下：

已知先序遍历：pre1、pre2、pre3、pre4、……、preN，中序遍历：in1、in2、……、inN。

由先序遍历的性质可知：pre1是当前二叉树根节点的值，然后，在中序遍历中遍历一遍，找到根节点（记为k），k左侧的就是左子树，k右侧的就是右子树。

左子树的长度：numleft=k-1；

那么，先序遍历中左子树的范围：2~2+numleft ，右子树的范围：k+1~N

中序遍历中左子树的范围： 1~k-1 ，右子树的范围：k+1~N

一般情况下：

已知先序遍历：preL、……、preR，中序遍历：inL、in2、……、inR。

由先序遍历的性质可知：preL是当前二叉树根节点的值，然后，在中序遍历中过一遍，找到根节点（记为k），k左侧的就是左子树，k右侧的就是右子树。

左子树的长度：numleft=k-inL；

那么，先序遍历中左子树的范围：preL+1~preL+numleft ，右子树的范围：preL+numleft+1~preR

中序遍历中左子树的范围： inL~k-1 ，右子树的范围：k+1~inR

2.代码

node* create(int preL,int preR,int inL,int inR){	if(preL>preR){     // 先序序列小于0，则返回 		return NULL;	}	node* root=new node;	root->data=pre[preL];       // 根节点赋值 	int k;	for(k=inL;k
   
    lchild=create(preL+1,preL+numLeft,inL,k-1); 	//对右子树进行递归 	root->rchild=create(preL+numLeft+1,preR,k+1,inR);    return root; }

完整代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define range 100#define NULL 0struct node{	int data;	node* lchild;	node* rchild;}; node* Root=NULL;int pre[range];int in[range];node* create(int preL,int preR,int inL,int inR){	if(preL>preR){     // 先序序列小于0，则返回 		return NULL;	}	node* root=new node;	root->data=pre[preL];       // 根节点赋值 	int k;	for(k=inL;k
       
        lchild=create(preL+1,preL+numLeft,inL,k-1); 	//对右子树进行递归 	root->rchild=create(preL+numLeft+1,preR,k+1,inR);    return root; }void preorder(node* root){      // 先序遍历 	if(root==NULL){		return ;	}	printf("%d ",root->data);	preorder(root->lchild);	preorder(root->rchild);} void inorder(node* root){       // 中序遍历 	if(root==NULL){		return ;	}	inorder(root->lchild);	printf("%d ",root->data);	inorder(root->rchild);} void postorder(node* root){     // 后序遍历 	if(root==NULL){		return ;	}	postorder(root->lchild);	postorder(root->rchild);	printf("%d ",root->data);} void layerorder(node* root){    // 层次遍历 	queue
        
          s; s.push(root); node* temp=NULL; while(!s.empty()){ temp=s.front(); s.pop(); printf("%d ",temp->data); if(temp->lchild!=NULL) s.push(temp->lchild); if(temp->rchild!=NULL) s.push(temp->rchild); }}//测试数据: 10 9 8 7 4 5 6 3 2 1 int main(){ int i,j; cout<<"请输入节点个数:"<
         
          >j; cout<<"请输入先序遍历:"<
          
           >pre[i]; cout<<"请输入中序遍历:"<
           
            >in[i]; Root=create(0,j-1,0,j-1); cout<
            
             <

如有错，请评论。

转载地址：http://ruven.baihongyu.com/

你可能感兴趣的文章