前序中序、后序中序遍历创建二叉树，并检验是否是二叉搜索树，若是则转换为双向链表

前序中序、后序中序遍历创建二叉树，并检验是否是二叉搜索树，若是则转换为双向链表

finalbst.h

//该程序的作用是根据所给的前序序列以及中序序列或者中序序列以及后序序列创建二叉树 
#include 
#include 
using namespace std;
typedef int datatype;

struct node{
	datatype data;
	node *Lchild;
	node *Rchild;
	node *Rpar;		//右孩子的双亲节点 
	node *Lpar;		//左孩子的双亲节点 
	node *nxt;
	node *lst;
};

class BST{
	public:
		BST();
		void createpre(vector&pre, vector&mid); 		//1、该函数将元素按前序、中序储存在两个vector容器中 
		node* buildpre(vectorpre,vectormid);			//2、调用1创建好的参数，创建二叉树 
		void createpos(vector&pos,vector&mid);			//3、该函数将元素按后序、中序序列存在两个vector容器中 
		node*buildpos(vectorpos, vectormid);			//4、调用 3创建好的参数，创建二叉树 
		int printBST(node*curr);											//5、显示二叉树 
		bool ifBST();														//6、通过key的值判断二叉树是否是搜索树 
		node*returnroot();													//7、返回根节点 
		int JudgeBST(node*curr);											//8、判断是否是二叉搜索树，并给出key值 
		
		int convert(node*curr);											//7、将二叉搜索树转换为双向链表
		void printChain();										//8、显示双向链表 
	private:
		node*root;
		node*head;
		datatype rootdata;		//储存根节点的值 
		int size;		//树的节点数 
		int key;		//判断是否是BST 
};

finalbst.cpp

#include
#include"finalbst.h"
using namespace std;

BST::BST(){
	root=new node();
	key = 1;		//初始化key值为1 
	head=new node();
	cout<<"初始化完成";
}

void BST::createpre(vector&pre, vector&mid){
	cout<<"输入前序序列,输入-1停止" <>a&&a!=-1){
		pre.push_back(a); 
	}
	rootdata=pre[0]; 
	cout<<"输入中序序列，输入-1停止"<>b&&b!=-1){
		mid.push_back(b);
	}
}

node*BST::buildpre(vectorpre, vectormid){
	size = pre.size();		//调用头文件vector.h中的函数返回当前容器的大小 
	if(size==0)	return NULL;
	node*curr;
	curr=new node();
	curr->data=pre[0];		//当前节点对应当前根节点 
	vectorLpre, Rpre, Lmid, Rmid;
	if(curr->data==rootdata) root=curr;		//确定根节点 
	int currpos;		//记录当前节点在mid中的位置 
	for(int i=0;icurrpos){
			Rpre.push_back(pre[i]);
			Rmid.push_back(mid[i]);
		}
	}
	curr->Lchild=buildpre(Lpre, Lmid);		//布置当前节点的左右子树 
	curr->Rchild=buildpre(Rpre, Rmid);
	return curr;		//该函数返回的值是当前函数参数对应的根节点 
}

void BST::createpos(vector&pos, vector&mid){
	datatype a,b;
	cout<<"输入中序序列：(按-1停止)"<>a&&a!=-1){
		mid.push_back(a);
	}
	cout<<"输入后序序列：（按-1停止）"<>b&&b!=-1){
		pos.push_back(b);
	}
	size=pos.size();
	rootdata=pos[size-1];
	//cout<pos, vectormid){
	size=pos.size();
	if(size==0) return NULL;
	node *curr;
	curr=new node();
	curr->data=pos[size-1];
	if(curr->data==rootdata) root=curr;
	int currpos=0;
	while(mid[currpos]!=curr->data){
		currpos++;
	}
	vectorLpos, Lmid, Rpos, Rmid;
	for(int i=0;icurrpos){
			Rpos.push_back(pos[i-1]);
			Rmid.push_back(mid[i]);
		}
	}
	curr->Lchild=buildpos(Lpos, Lmid);
	curr->Rchild=buildpos(Rpos, Rmid);
	return curr;
}

int BST::printBST(node*curr){		//在该函数中布置双亲指针 
	if(curr==NULL) return 0;
	if(curr->Lchild!=NULL||curr->Rchild!=NULL)cout<<"根节点"<data<Lchild!=NULL) {
		cout<<"左孩子"<Lchild->data<Lchild->Lpar=curr;
	}
	if(curr->Rchild!=NULL){
		cout<<"右孩子"<Rchild->data<Rchild->Rpar=curr;
	} 
	printBST(curr->Lchild);
	printBST(curr->Rchild);
}

int BST::JudgeBST(node*curr){
	if(curr==NULL) return 0;
	if(curr->Lchild!=NULL&&curr->Rchild!=NULL)
			if(curr->Lchild->data>=curr->data||curr->Rchild->data<=curr->data){
				key=0;
				return 0;
			}
	else if(curr->Lchild!=NULL&&curr->Rchild==NULL)
		if(curr->Lchild->data>=curr->data){
			key = 0;
			return 0;
		}
	else if(curr->Rchild!=NULL&&curr->Lchild==NULL)
		if(curr->Rchild->data<=curr->data){
			key = 0;
			return 0;
		}
	
	JudgeBST(curr->Lchild);
	JudgeBST(curr->Rchild);
}

bool BST::ifBST(){
	if(key==1) return true;
	else return false;
}

node*BST::returnroot(){
	return root;
}

int BST::convert(node*curr){
	if(curr==NULL) return 0;
	//cout<data<<"  ";//测试 
	if(curr->Rchild==NULL&&curr->Lchild==NULL) return 0;
	if(curr==root){
		if(curr->Rchild!=NULL&&curr->Lchild!=NULL){
			curr->Lchild->nxt=curr;
			curr->lst=curr->Lchild;
			curr->nxt=curr->Rchild;
			curr->Rchild->lst=curr;
		}
		else if(curr->Rchild!=NULL&&curr->Lchild==NULL){
			curr->nxt=curr->Rchild;
			curr->Rchild->lst=curr;
		}
		else if(curr->Lchild!=NULL&&curr->Rchild==NULL){
			curr->Lchild->nxt=curr;
			curr->lst=curr->Lchild;
		}
	}
	else if(curr->Lpar!=NULL){
		if(curr->Rchild!=NULL&&curr->Lchild!=NULL){
			if(curr->lst!=NULL&&curr->lst->data<=curr->Lchild->data){
				curr->lst->nxt=curr->Lchild;
				curr->Lchild->lst=curr->lst;
			} 
			curr->nxt=curr->Rchild;
			curr->Rchild->lst=curr;
			curr->Rchild->nxt=curr->Lpar;
			curr->Lpar->lst=curr->Rchild;
			curr->Lchild->nxt=curr;
			curr->lst=curr->Lchild;
		}
		else if(curr->Rchild!=NULL&&curr->Lchild==NULL){
			curr->nxt=curr->Rchild;
			curr->Rchild->lst=curr;
			curr->Rchild->nxt=curr->Lpar;
			curr->Lpar->lst=curr->Rchild;
		}
		else if(curr->Rchild==NULL&&curr->Lchild!=NULL){
			if(curr->lst!=NULL&&curr->lst->data<=curr->Lchild->data){
				curr->lst->nxt=curr->Lchild;
				curr->Lchild->lst=curr->lst;
			} 
			curr->Lchild->nxt=curr;
			curr->lst=curr->Lchild;
		}
	}
	else if(curr->Rpar!=NULL){
		if(curr->Rchild!=NULL&&curr->Lchild!=NULL){
			if(curr->nxt!=NULL&&curr->nxt->data>=curr->Rchild->data){
				curr->Rchild->nxt=curr->nxt;
				curr->nxt->lst=curr->Rchild;
			}
			curr->nxt=curr->Rchild;
			curr->Rchild->lst=curr; 
			curr->Lchild->nxt=curr;
			curr->lst=curr->Lchild;
			curr->Rpar->nxt=curr->Lchild;
			curr->Lchild->lst=curr->Rpar;
			
		}
		else if(curr->Rchild==NULL&&curr->Lchild!=NULL){
			curr->Lchild->nxt=curr;
			curr->lst=curr->Lchild;
			curr->Rpar->nxt=curr->Lchild;
			curr->Lchild->lst=curr->Rpar;
		}
		else if(curr->Rchild!=NULL&&curr->Lchild==NULL){
			if(curr->nxt!=NULL&&curr->nxt->data>=curr->Rchild->data){
				curr->Rchild->nxt=curr->nxt;
				curr->nxt->lst=curr->Rchild;
			}
			curr->nxt=curr->Rchild;
			curr->Rchild->lst=curr;
		}
	}
	convert(curr->Lchild);
	convert(curr->Rchild);
}

void BST::printChain(){
	node *curr;
	curr=root;
	while(curr->lst!=NULL){
		//system("PAUSE");//测试 
		curr=curr->lst;
		//cout<data<lst<data<data<<"  ";//测试
		cout<data<<"  "; 
		curr=curr->nxt;
	} 
}

int main(){
	//前序：9 4 2 1 3 6 5 7 13 11 10 12 15 14 16
	//中序：1 2 3 4 5 6 7 9 10 11 12 13 14 15 16
	//前序：5 3 2 4 7 6 8 9
	//中序：2 3 4 5 6 7 8 9 
	BST use;
	cout<<"1、前序+中序	  2、后序+中序"<>a;
	if(a==1){
		vectorpre;
		vectormid;
		use.createpre(pre, mid);
		use.buildpre(pre, mid);
	}
	else{
		vectorpos;
		vectormid;
		use.createpos(pos, mid);
		use.buildpos(pos, mid);
	}
	use.printBST(use.returnroot());		//函数返回值作参数 
	use.JudgeBST(use.returnroot());		//判断是否是二叉搜索树，并为key赋值
	if(use.ifBST()==true){
		cout<<"是BST"< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5710923.html