浙江财经大学
信工学院ACM集训队

非递归输出中序遍历

本文由 Ocrosoft 于 2016-06-01 11:30:55 发表

先根据括号表达式建树,然后输出中序遍历结果,前序只需要把输出内容拿到前面,后序比较麻烦。

#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 PrintInS(Tree *p)
{
    stack<Tree*> s;
    Tree *q=p;
    while(!s.empty()||q!=NULL)
    {
        while(q!=NULL)
        {
            s.push(q);
            q=q->left;
        }
        if(!s.empty())
        {
            q=s.top();
            s.pop();
            printf("%c",q->data);
            q=q->right;
        }
    }
}
int main()
{
    cin>>s;
    creat();
    cout<<"InOrder:";
    PrintInS(tree);
    cout<<endl;
    return 0;
}

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

点赞 (0)or拍砖 (0)

评论 抢沙发

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