二叉树的中序遍历序列

【问题描述】

设计算法求二叉树的中序遍历序列。

【输入形式】一行字符串，该行是扩展二叉树的前序遍历序列，用于构造二叉树。

【输出形式】二叉树中的中序遍历序列。

【样例输入】AB#D##C##

【样例输出】

 BDAC

#include<iostream>
using namespace std;
template<typename DataType>struct BiNode
{DataType data;BiNode<DataType> *lchild,*rchild;
};template <typename DataType>
class BiTree
{public:BiTree(){root=Creat();}void InOrder(){InOrder(root);}private:BiNode<DataType> *Creat();void InOrder(BiNode<DataType> *bt);BiNode<DataType> *root;
};template<typename DataType>
BiNode<DataType> *BiTree<DataType>::Creat()
{BiNode<DataType> *bt;char ch;cin>>ch;if(ch=='#')  bt=NULL;else{bt=new BiNode<DataType>;bt->data=ch;bt->lchild=Creat();bt->rchild=Creat();}return bt;
}template<typename DataType>
void BiTree<DataType>::InOrder(BiNode<DataType> *bt)
{if(bt){InOrder(bt->lchild);cout<<bt->data;InOrder(bt->rchild);}
}int main()
{BiTree<char>  t;t.InOrder();
}