数据结构先序遍历非递归算法-C++数据结构——二叉树的建立与遍历

  根据带虚结点的先序序列建立二叉树数据结构先序遍历非递归算法，输出该二叉树的中序、后序遍历序列。

  输入格式:

  测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符∗表示虚结点（对应的子树为空）。

  

  输出格式:

  对于每组测试，分别在两行输出所建立二叉树的中序遍历序列和后序遍历序列。

  

  输入样例:

  HDACBGFE*

  

  输出样例:

  代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

  解题代码

<p><pre>#include
using namespace std;
string str;
int len=0;
template
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
void Tree::LNR(treeNode *node)
{

if(node!=NULL){
    LNR(node->L_child);
    coutR_child);
}

}
template
void Tree::LRN(treeNode *node)
{

if(node!=NULL){
    LRN(node->L_child);
    LRN(node->R_child);
    cout>str){
    len=0;
    Tree *tree = new Tree();
    tree->root=tree->createNode();
    tree->LNR(tree->root);
    coutroot);
    cout