[数据结构与算法]DS二叉树--二叉树构建与遍历

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘#’表示，连续输入t行。

输出

输出每个二叉树的先序遍历、中序遍历和后序遍历结果。

样例输入

2

AB0C00D00

AB00C00

样例输出

ABCD
BCAD
CBDA
ABC
BAC
BCA

#include <iostream>
#include <string>
using namespace std;
class BitNode{
public:
	char data;
	BitNode*lchild,*rchild;
	BitNode(){
		lchild=NULL;
		rchild=NULL;
	}
};
class Bitree{
public:
	BitNode*root;
	string str;
	int pos;
	Bitree(string str){
		this->str=str;
		pos=0;
		root=createTree();
	}
	BitNode*createTree(){//createTree需要递归，这是为什么pos不在里面定义的原因 
		char ch;
		ch=str[pos];
		pos++;
		if(ch=='0'){
			return NULL;
		} 
		else{
			BitNode*b=new BitNode();
			b->data=ch;
			b->lchild=createTree();
			b->rchild=createTree();
			return b;
		}
	}
	void preOrder(BitNode*b){
		if(b!=NULL){
			cout<<b->data;
			preOrder(b->lchild);
			preOrder(b->rchild);
		}
	} 
	void inOrder(BitNode*b){
		if(b!=NULL){
			inOrder(b->lchild);
			cout<<b->data;
			inOrder(b->rchild);
		}
	}
	void postOrder(BitNode*b){
		if(b!=NULL){
			postOrder(b->lchild);
			postOrder(b->rchild);
			cout<<b->data;
		}
	}
};
int main(){
	int t;
	cin>>t;
	while(t--){
		string str;
		cin>>str;
		Bitree b(str);
		b.preOrder(b.root);
		cout<<endl;
		b.inOrder(b.root);
		cout<<endl;
		b.postOrder(b.root);
		cout<<endl;
	}
}