根据带虚结点的先序序列建立二叉树，输出该二叉树的中序、后序遍历序列。
输入格式:
测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符?表示虚结点（对应的子树为空）。
输出格式:
对于每组测试，分别在两行输出所建立二叉树的中序遍历序列和后序遍历序列。
输入样例:
HDAC*BGFE**
输出样例:
ADCBHFEG
ABCDEFGH
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
解题代码
#include<bits/stdc++.h>
using namespace std;
string str;
int len=0;
template<class T>
class Tree{
public:
Tree(){
root=NULL;
}
struct treeNode{
T data;
treeNode *L_child,*R_child;
treeNode(T d){
data=d;
}
};
treeNode *root;
treeNode* createNode()
{
treeNode *t;
if(len>=str.size()){
return NULL;
}
T data = str[len++];
if(data=='*'){
t=NULL;
}else{
t=new treeNode(data);
t->L_child=createNode();
t->R_child=createNode();
}
return t;
};
void LNR(treeNode *node);
void LRN(treeNode *node);
};
template<class T>
void Tree<T>::LNR(treeNode *node)
{
if(node!=NULL){
LNR(node->L_child);
cout<<node->data;
LNR(node->R_child);
}
}
template<class T>
void Tree<T>::LRN(treeNode *node)
{
if(node!=NULL){
LRN(node->L_child);
LRN(node->R_child);
cout<<node->data;
}
}
int main()
{
while(cin>>str){
len=0;
Tree<char> *tree = new Tree<char>();
tree->root=tree->createNode();
tree->LNR(tree->root);
cout<<endl;
tree->LRN(tree->root);
cout<<endl;
}
}
解题思路
这里用了模板类，起初是想着方便一点，但是越写越感觉麻烦，然后这里的刷创建节点就一直递归去创建，查找就按照中序和后续遍历的规则进行递归输出，其他的倒也没什么，抓住二叉树的性质去做就行
