层序遍历序列和中序遍历序列构建二叉树

ゝ一世哀愁。 2023-07-21 05:56 11阅读 0赞

输入节点个数

后两行分别输入层次遍历序列、中序遍历序列

使用build()函数建立二叉树，先找到根节点，再划分左右子树，分别构建两棵子树。

并将左右节点分别保存至lch、rch数组中，且保存的是其下标（无左节点时，lch=0；无右孩子时，rch=0）

第一个根节点时根节点的第一个节点，

之后子树的根节点寻找办法是，根据已经划分左右子树在中序遍历的序列中，找到第一个在层序遍历中找到的结点，则为子树的根节点。

具体代码见下面：

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    typedef long long ll;
    
    //还原二叉树 
    //输入二叉树的层次遍历序列和中序遍历序列
    //求这棵二叉树的先序遍历序列和后序遍历序列 
    // N 代表二叉树的节点个数
    /*
    7
    3 5 4 2 6 7 1
    2 5 3 6 4 7 1
    */ 
    const int maxn =30+5;
    int inOrder[maxn];//中序遍历序列
    int leverOrder[maxn];//层序遍历序列
    int preOrder[maxn];//先序遍历序列
    int postOrder[maxn];//后序遍历序列 
    int lch[maxn];
    int rch[maxn]; 
    int N; //结点个数 
    
    int find(int l, int r){
    	for(int i=1;i<=N;i++){
    		for(int j=l;j<=r;j++){
    			if(inOrder[j]==leverOrder[i]) return j; 
    		}
    	}
    	return 0;
    	 
    }
    
    void build(int root, int l, int r){//利用先序序列和后序序列建立一棵二叉树
    	//寻找中序遍历的根节点位置
    	if(l<=r){
    		int root1 = l;
    		while(inOrder[root1] != root)  root1++;
    		
    		lch[root1] = find(l, root1-1); //lch、rch存储的是 
    		build(inOrder[lch[root1]], l, root1-1);
    		
    		rch[root1] = find(root1+1, r);
    		build(inOrder[rch[root1]], root1+1, r);
    	}
    }
    
    //打印先序遍历序列
    int cnt1 = 0; 
    void pretravel(int x){
        if(x){ 
            preOrder[cnt1] = inOrder[x];
            cnt1++;
            //printf("%d", inOrder[x]);
            
            //中序遍历序列 
    	    pretravel(lch[x]);
    		pretravel(rch[x]); 
    	}	
    } 
    
    //打印后序遍历序列 
    int cnt2 = 0;
    void posttravel(int x){
    	if(x){ 
    	    posttravel(lch[x]);
    		posttravel(rch[x]); 
    		
    		postOrder[cnt2] = inOrder[x];
            cnt2++;
    		//printf("%d ", inOrder[x]);
    	}
    }
     
    int main(){
       
       scanf("%d",&N);//输入节点个数
       memset(leverOrder,0,sizeof(leverOrder));
       memset(inOrder,0,sizeof(inOrder));
       memset(preOrder,0,sizeof(preOrder));
       memset(postOrder,0,sizeof(postOrder));
       for(int i=1;i<=N;i++) scanf("%d",&leverOrder[i]);  //输入层序序列 
       for(int i=1;i<=N;i++) scanf("%d",&inOrder[i]);   //输入中序序列 
       //初始化左右孩子节点，左右孩子都为0的为叶子结点 
       memset(lch,0,sizeof(lch));
       memset(rch,0,sizeof(rch));
      
       int root = leverOrder[1]; 
       int root1 = 1;
       while(inOrder[root1] != root)  root1++;
       build(root, 1, N);	//建立一棵二叉树 
       pretravel(root1); //打印先序序列
       for(int i=0;i<N;i++){
       	 if(i!=0) printf(" ");
       	 printf("%d",preOrder[i]);
       }
       printf("\n"); 
       posttravel(root1);  //打印后续序列
       for(int i=0;i<N;i++){
       	 if(i!=0) printf(" ");
       	 printf("%d",postOrder[i]);
       }
       printf("\n");
        
       return 0;
    }