浙江财经大学
信息管理与工程学院

递归输出前序中序后序遍历

本文由 Ocrosoft 于 2016-06-01 11:29:17 发表

先根据括号表达式建树,然后输出前中后序遍历结果。

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;
struct Tree
{
    int data;
    Tree *left;
    Tree *right;
}*tree;
string s;
void creat()
{
    stack<Tree*> st;
    Tree *p = NULL;
    int k;
    tree = NULL;
    string::iterator it=s.begin();
    while(it!=s.end())
    {
        if(*it=='(')
        {
            st.push(p);
            k=1;
        }
        else if(*it==')')st.pop();
        else if(*it==',')k=2;
        else
        {
            p=new Tree();
            p->data=*it;
            p->left=p->right=NULL;
            if(tree==NULL)tree=p;
            else
            {
                if(k==1)st.top()->left=p;
                else st.top()->right=p;
            }
        }
        it++;
    }
}
void PrintPr(Tree *p)
{
    if(p==NULL)return;
    else
    {
        printf("%c",p->data);
        PrintPr(p->left);
        PrintPr(p->right);
    }
}
void PrintIn(Tree *p)
{
    if(p==NULL)return;
    else
    {
        PrintIn(p->left);
        printf("%c",p->data);
        PrintIn(p->right);
    }
}
void PrintAf(Tree *p)
{
    if(p==NULL)return;
    else
    {
        PrintAf(p->left);
        PrintAf(p->right);
        printf("%c",p->data);
    }
}
int main()
{
    cin>>s;
    creat();
    cout<<"PreOrder:";
    PrintPr(tree);
    cout<<endl;
    cout<<"InOrder:";
    PrintIn(tree);
    cout<<endl;
    cout<<"PostOrder:";
    PrintAf(tree);
    cout<<endl;
    return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » 递归输出前序中序后序遍历

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址