序列遍历二叉树

目录

类模板（指针版）

来了来了！！！数组版！！构造遍历！不用指针！

层序输入不用建树（

就不多说了，按前序遍历的字符串创建的二叉树，然后有前、中、后、层序遍历输出，计算树的深度的功能。

层序遍历是用的队列版，后来发现数组版（貌似好像更）好写。

然后考试。

。

写类，是挺麻烦的，直接改成一个个普通函数会好写一些吧。

#include
#include
#include
using namespace std;
struct BN{
	char data;
	BN *lchild, *rchild;
}; 
class BT{
	private:
		BN *root;
		BN *creat (BN *bt);
		void preOrder(BN *bt);
		void inOrder(BN *bt); 
		void postOrder(BN *bt);
		//void leverOrder(BN *bt);
		int getDepth(BN *bt);
	public:
		BT(){root=creat(root);}
		void preOrder(){preOrder(root);}
		void inOrder(){inOrder(root);}
		void postOrder(){postOrder(root);}
		//void leverOrder(){leverOrder(root);}
		void leverOrder();
		int getDepth(){return getDepth(root);}
};
BN *BT::creat(BN *bt){
	char ch;
	cin >>ch;
	if(ch=='#')bt=NULL;
	else{
		bt = new BN;
		bt->data = ch;
		bt->lchild = creat(bt->lchild);
		bt->rchild = creat(bt->rchild);
	}
	return bt;
}
int BT::getDepth(BN *bt){
	int dep=0;
	if(bt==NULL)return 0;
	return max(getDepth(bt->lchild),getDepth(bt->rchild))+1;
}
void BT::preOrder(BN *bt){
	if(bt==NULL)return;
	cout <data;
	preOrder(bt->lchild);
	preOrder(bt->rchild);
}
void BT::inOrder(BN *bt){
	if(bt==NULL)return;
	inOrder(bt->lchild);
	cout <data;
	inOrder(bt->rchild);
}
void BT::postOrder(BN *bt){
	if(bt==NULL)return;
	postOrder(bt->lchild);
	postOrder(bt->rchild);
	cout <data;
}
//队列版 层序 
//void BT::leverOrder(BN *bt){
//	queue q;
//	if(bt!=NULL)q.push(bt);
//	while(!q.empty()){
//		BN *p=q.front();
//		cout <data;
//		if(p->lchild!=NULL)
//			q.push(p->lchild);
//		if(p->rchild)
//			q.push(p->rchild);
//		q.pop();
//	}
//}
//数组版 层序 
void BT::leverOrder(){
	BN* tp[100];
	int in=0,out=0;
	if(root==NULL)return;
	tp[in++]=root;
	while(in>out){
		if(tp[out]){
			cout <data;
			tp[in++]=tp[out]->lchild;
			tp[in++]=tp[out]->rchild;
		}
		out++;
	}
}
int main(){
	BT tr;
	cout <<"前序遍历：";tr.preOrder();
	cout <<"\n中序遍历：";tr.inOrder();
	cout <<"\n后序遍历：";tr.postOrder();
	cout <<"\n层序遍历：";tr.leverOrder();
	cout <<"\n树的深度："<

#include
#include
#include
using namespace std;
string s;
char tr[1000010];
int n,ct;
void Creat(int i){
	tr[i]=s[ct++];
	if(i>=n||tr[i]=='^')return;
	Creat(2*i+1);//注意根节点是0，所以左右节点这样表示
	Creat(2*i+2);
}
void preShow(int i){
	if(tr[i]=='^')return;
	cout <=0;i--){
		if(tr[i]!='^'){
			maxi=i;
			break;
		}
	}
	//cout <<"maxi="<=L&&maxi<=R)return k+1;
	}
}
int main(){
	for(int i=0;i<1000010;i++)tr[i]='^';//初始化 
	cin>>s;      //输入前序遍历字符串
	n=s.size(); 
	Creat(0);   //建树 
	cout <<"前序遍历：",preShow(0);
	cout <<"\n中序遍历：",inShow(0);    
	cout <<"\n后序遍历：",postShow(0);
	cout <<"\n层序遍历：",leverShow();
	cout <<"\n树的深度："<

#include
#include
using namespace std;
char node[1000000];
void show(int i){
	if(node[i]!='^')return;
	cout<>s;
	int len = s.length();
	for(int i=0;i