建立二叉搜索树及根据中序遍历序列和先序（或后序）遍历序列建立二叉树与二叉树先序、中序、后序、层次（记录当前层次的和不记录的）遍历实现

落日映苍穹つ 2023-10-03 18:43 22阅读 0赞

#### 文章目录 ####

*  树（结点）的构建：
 *  二叉树的建立
 *   *  建立二叉搜索树
     *  根据中序和先序遍历序列建树
     *  根据中序和后序遍历序列建树
 *  二叉树的遍历
 *   *  先序遍历（递归）
     *  中序遍历（递归）
     *  后序遍历（递归）
     *  层次遍历
 *  完整代码（可直接运行）
 *  参考链接

二叉树原理层面就不赘述了，可以看看文末的参考链接，直接上干货代码！

## 树（结点）的构建： ##

struct Node {
        
    	int data;
    	Node *left,*right;
    	Node(){
        //声明无参构造方法 
    		
    	}
    	Node(int d) {
         //注意要这样写才能用这个：new Node(a[l1]);
    		data = d;
    	}
    };

## 二叉树的建立 ##

### 建立二叉搜索树 ###

//递归建立二叉搜索树
    void cre(Node* &t, int x, int level) {
        
    	if(t==NULL) {
        
    		t = new Node;//创建对象，由于定义了有参构建，所以要声明无参构造方法 
    		t->left = t->right = NULL;
    		t->data = x;
    //		cnt[level]++;
    //		if(level>mmax) mmax = level;
    		return;
    	}
    	if(x<=t->data) cre(t->left, x, level+1);
    	else cre(t->right, x, level+1);
    }

### 根据中序和先序遍历序列建树 ###

Node* PreInCreate(int l1,int r1,int l2,int r2,int level) {
         //根据先序以及中序遍历建树
    	if(l2>r2) return NULL;//要根据中序序列l2,r2而不是l1,r1，来判断是否有无左右子树
    	v[level].push_back(a[l1]);//带层次的层次遍历！！ 
    	Node *root = new Node(a[l1]);//确定当前的根，必然是先序序列的下一个字符
    	int i;
    //	cout<<"111"<<endl;
    	for(i=l2; b[i]!=a[l1]; i++); //确定根在中序序列位置
    	int llen=i-l2;//计算左子树的长度
    	root->left=PreInCreate(l1+1,l1+llen,l2,i-1,level+1);//左子树
    	root->right=PreInCreate(l1+llen+1,r1,i+1,r2,level+1);//右子树
    	return root;//别忘记返回节点
    }

### 根据中序和后序遍历序列建树 ###

Node* PostInCreate(int l1,int r1,int l2,int r2,int level) {
         //根据后序以及中序遍历建树
    	if(l2>r2) return NULL;//要根据中序序列l2,r2而不是l1,r1，来判断是否有无左右子树
    	v[level].push_back(a[r1]);//带层次的层次遍历！！ 
    	Node *root=new Node(a[r1]);//确定当前的根，必然是后序序列的最后一个字符
    	int i;
    	for(i=l2; b[i]!=a[r1]; i++); //确定根在中序序列位置
    	int llen=i-l2;//计算左子树的长度
    	root->left=PostInCreate(l1,l1+llen-1,l2,i-1,level+1);//左子树
    	root->right=PostInCreate(l1+llen,r1-1,i+1,r2,level+1);//右子树
    	return root;//别忘记返回节点
    }

## 二叉树的遍历 ##

### 先序遍历（递归） ###

void PreTravse(Node *root) {
         //先序遍历，根左右
    	if(root==NULL)return;
    	printf("%d",root->data);//根
    	PreTravse(root->left);//左
    	PreTravse(root->right);//右
    }

### 中序遍历（递归） ###

void InTravse(Node *root) {
         //中序遍历，左根右
    	if(root==NULL)return;
    	InTravse(root->left);//左
    	printf("%d",root->data);//根
    	InTravse(root->right);//右
    }

### 后序遍历（递归） ###

void PostTravse(Node *root) {
         //后序遍历，左右根
    	if(root==NULL)return;
    	PostTravse(root->left);//左
    	PostTravse(root->right);//右
    	printf("%d",root->data);//根
    }

### 层次遍历 ###

void LevelTravse(Node *root) {
        //层次遍历 
    	queue<Node*> q;
    	q.push(root);
    	Node *p;
    	while(!q.empty()) {
        
    		p=q.front();
    		q.pop();
    		cout<<p->data<<" ";
    		if(p->left) q.push(p->left);
    		if(p->right) q.push(p->right);
    	}
    }

## 完整代码（可直接运行） ##

//根据中序+先序或中序+后序遍历序列建立二叉树
    #include <bits/stdc++.h>
    using namespace std;
    int a[10000],b[10000];//a是PreOrder或者是PostOrder,b是InOrder
    int n;
    vector<int> v[10000];//v[层次]，每层次中每个结点的{结点值} 
    struct Node {
        
    	int data;
    	Node *left,*right;
    	Node(){
        //声明无参构造方法 
    		
    	}
    	Node(int d) {
         //注意要这样写才能用这个：new Node(a[l1]);
    		data = d;
    	}
    };
    //递归建立二叉搜索树
    void cre(Node* &t, int x, int level) {
        
    	if(t==NULL) {
        
    		t = new Node;//创建对象，由于定义了有参构建，所以要声明无参构造方法 
    		t->left = t->right = NULL;
    		t->data = x;
    //		cnt[level]++;
    //		if(level>mmax) mmax = level;
    		return;
    	}
    	if(x<=t->data) cre(t->left, x, level+1);
    	else cre(t->right, x, level+1);
    }
    
    Node* PreInCreate(int l1,int r1,int l2,int r2,int level) {
         //根据先序以及中序遍历建树
    	if(l2>r2) return NULL;//要根据中序序列l2,r2而不是l1,r1，来判断是否有无左右子树
    	v[level].push_back(a[l1]);//带层次的层次遍历！！ 
    	Node *root = new Node(a[l1]);//确定当前的根，必然是先序序列的下一个字符
    	int i;
    //	cout<<"111"<<endl;
    	for(i=l2; b[i]!=a[l1]; i++); //确定根在中序序列位置
    	int llen=i-l2;//计算左子树的长度
    	root->left=PreInCreate(l1+1,l1+llen,l2,i-1,level+1);//左子树
    	root->right=PreInCreate(l1+llen+1,r1,i+1,r2,level+1);//右子树
    	return root;//别忘记返回节点
    }
    Node* PostInCreate(int l1,int r1,int l2,int r2,int level) {
         //根据后序以及中序遍历建树
    	if(l2>r2) return NULL;//要根据中序序列l2,r2而不是l1,r1，来判断是否有无左右子树
    	v[level].push_back(a[r1]);//带层次的层次遍历！！ 
    	Node *root=new Node(a[r1]);//确定当前的根，必然是后序序列的最后一个字符
    	int i;
    	for(i=l2; b[i]!=a[r1]; i++); //确定根在中序序列位置
    	int llen=i-l2;//计算左子树的长度
    	root->left=PostInCreate(l1,l1+llen-1,l2,i-1,level+1);//左子树
    	root->right=PostInCreate(l1+llen,r1-1,i+1,r2,level+1);//右子树
    	return root;//别忘记返回节点
    }
    void PreTravse(Node *root) {
         //先序遍历，根左右
    	if(root==NULL)return;
    	printf("%d",root->data);//根
    	PreTravse(root->left);//左
    	PreTravse(root->right);//右
    }
    void InTravse(Node *root) {
         //中序遍历，左根右
    	if(root==NULL)return;
    	InTravse(root->left);//左
    	printf("%d",root->data);//根
    	InTravse(root->right);//右
    }
    void PostTravse(Node *root) {
         //后序遍历，左右根
    	if(root==NULL)return;
    	PostTravse(root->left);//左
    	PostTravse(root->right);//右
    	printf("%d",root->data);//根
    }
    void LevelTravse(Node *root) {
        //层次遍历 
    	queue<Node*> q;
    	q.push(root);
    	Node *p;
    	while(!q.empty()) {
        
    		p=q.front();
    		q.pop();
    		cout<<p->data<<" ";
    		if(p->left) q.push(p->left);
    		if(p->right) q.push(p->right);
    	}
    }
    int main() {
        
    	Node *root=NULL;
    //	int n;
    	cin>>n;
    	for(int i=0; i<n; i++) {
        
    		cin>>a[i];//先or后序遍历序列
    	}
    	for(int i=0; i<n; i++) {
        
    		cin>>b[i];
    	}
    	int mode;
    	cin>>mode;//0为先序，1为后序
    	if(mode==0) {
        
    		root = PreInCreate(0,n-1,0,n-1,1);
    		cout<<"先序遍历:\n";
    		PreTravse(root);
    		cout<<endl;
    		cout<<"中序遍历:\n";
    		InTravse(root);
    		cout<<endl;
    		cout<<"后序遍历:\n";
    		PostTravse(root);
    		cout<<endl;
    		cout<<"层次遍历\n";
    		LevelTravse(root);
    		cout<<endl;
    		//带层次的层次遍历！！ 
    		for(int i=1;v[i].size()!=0;i++){
        
    			cout<<i<<endl;
    			for(auto t:v[i]){
        
    				cout<<t<<" ";
    			}
    			cout<<endl;
    		}
    
    	} else {
        
    		root=PostInCreate(0,n-1,0,n-1,1);
    		cout<<"后序遍历:\n";
    		PostTravse(root);
    		cout<<endl;
    		cout<<"中序遍历:\n";
    		InTravse(root);
    		printf("\n");
    		cout<<"先序遍历:\n";
    		PreTravse(root);
    		cout<<endl;
    		cout<<"层次遍历\n";
    		LevelTravse(root);
    		cout<<endl;
    		//带层次的层次遍历！！ 
    		for(int i=1;v[i].size()!=0;i++){
        
    			cout<<"level: "<<i<<endl;
    			for(auto t:v[i]){
        
    				cout<<t<<" ";
    			}
    			cout<<endl;
    		}
    	}
    
    }

## 参考链接 ##

[根据后序遍历（先序遍历）和中序遍历建树][Link 1]  
看原理：[数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）][C]  
[【算法模板】二叉树的三种遍历方式，以及根据两种遍历方式建树][Link 2]  
[二叉树层次遍历算法——C/C++][C_C]

[Link 1]: https://www.cnblogs.com/dreamy-xay/p/14061966.html
[C]: https://blog.csdn.net/chinesekobe/article/details/110874773?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165027983516782184667941%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165027983516782184667941&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-110874773.142%5Ev9%5Econtrol,157%5Ev4%5Econtrol&utm_term=%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1018.2226.3001.4187
[Link 2]: https://blog.csdn.net/Hide_in_Code/article/details/82943479?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%A0%B9%E6%8D%AE%E9%81%8D%E5%8E%86%E7%BB%93%E6%9E%9C%E5%BB%BA%E6%A0%91&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-82943479.142%5Ev9%5Econtrol,157%5Ev4%5Econtrol&spm=1018.2226.3001.4187
[C_C]: https://blog.csdn.net/weixin_42109012/article/details/92250160?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165033991916780357248291%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165033991916780357248291&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-92250160.142%5Ev9%5Econtrol,157%5Ev4%5Econtrol&utm_term=%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86c%2b%2b&spm=1018.2226.3001.4187