【数据结构】（二叉树）根据先序和中序唯一确定一颗二叉树

痛定思痛。 2021-11-14 12:42 647阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 3]

## 完整代码 ##

typedef struct BiTree{
        
    	char data;
    	BiTree *lchild;
    	BiTree *rchild;
    	
    }BiTree;
    BiTree* PreInCreate2(char pre[],char in[],int s1,int end1,int s2,int end2){
        
    
    	BiTree *root=(BiTree*)malloc(sizeof(BiTree));
    	root->data=pre[s1];
    	int i;
    	for(i=s2;in[i]!=root->data;i++);
    	int left=i-s2;
    	int right=end2-i;
    	if(left){
        
    		root->lchild=PreInCreate2(pre,in,s1+1,s1+left,s2,s2+left-1);
    	}else{
        
    		root->lchild=NULL;
    	}
    	if(right){
        
    		root->rchild=PreInCreate2(pre,in,end1-right+1,end1,end2-right+1,end2);
    	}else{
        
    		root->rchild=NULL;
    	}
    
    	return root;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]: /images/20211114/945ad25ab75c4538b7d18426c7602ef4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 1]: /images/20211114/8c7eb17b598342b480c2edf64d0983a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 2]: /images/20211114/0960890dd21d407e86b63cbd8f15c680.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 3]: /images/20211114/581370d976ba45559bd0b5f651a0db6c.png