wustoj(二叉树的非递归遍历方法)

我会带着你远行 2022-06-06 09:05 130阅读 0赞

问题描述:

包含多组测试数据。每组测试数据一行，给出二叉树的先序遍历序列（至少1个结点）

输出二叉树的先序，中序和后序遍历结果。

^表示空节点

ABC^^DE^G^^F^^^
    A^^
    AB^^C^^

ABCDEGF
    CBEGDFA
    CGEFDBA
    A
    A
    A
    ABC
    BAC
    BCA

题目分析:很简单的一道二叉树遍历，递归遍历的方法很简单，这里就不说了！这里主要介绍的是非递归算法，也就是利用栈结构来遍历二叉树！

先序遍历:先序遍历满足DLR遍历方式，也就是先根，在左儿子，然后右儿子。先入栈根节点，然后我们遇到一个节点，就把它输出出来，然后先入栈它的右儿子，然后再入栈它的左儿子。因为栈的先进后出特性！一直到栈空，结束。

中序遍历:中序遍历满足LDR的遍历方式。一直要把一个树的左子树全部遍历完，才访问根，然后访问右子树。所以我们入栈的时候，把根节点入栈，然后把它所有的左儿子全部入栈。然后弹出栈顶，输出，如果它的右子树存在，那么连同这个节点和它的所有的左儿子全部入栈。一直到栈空，结束。

后序遍历:后序遍历满足LRD的遍历方式。后序遍历难在，先要把左子树访问完，然后右子树，然后根。那么我们在操作时，怎么知道这个根的左右子树被访问了？ 左子树好办，因为我们要把根和左子树先入栈，右子树了？ 开始入栈的时候和中序遍历一样，然后这里我们要有一个标记，标记这个节点的右子树是否被访问，如果被访问或者右子树不存在那么就可以输出该节点，如果没有那么我们就把节点的标记置为true,表示被访问了，然后把右儿子丢入栈，把它看成一棵树的根节点，重复操作！

具体看代码:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<stack>
    using namespace std;
    
    int cur,len;
    string str;
    struct tree
    {
        struct tree* lchild;
        struct tree* rchild;
        char val;
        bool flag;//仅仅后序遍历需要
    };
    
    void build(tree * &T)
    {
        if (cur>=len) return ;
        if (str[cur]=='^')
            T=NULL,cur++;
        else {
            T=new tree();
            T->val=str[cur++];
            build(T->lchild);
            build(T->rchild);
        }
    }
    void firstorder(tree *T)
    {
        stack<struct tree*> s;
        if (T==NULL) return ;
        s.push(T);
        while (s.size()) {
            struct tree* p=s.top();
            s.pop();
            cout<<p->val;
            if (p->rchild!=NULL) s.push(p->rchild);
            if (p->lchild!=NULL) s.push(p->lchild);
        }
    
    }
    void midorder(tree *T)
    {
        stack<struct tree*> s;
        if (T==NULL) return ;
        struct tree* p=T;
        while (p!=NULL) {//所有的左儿子
            s.push(p);
            p=p->lchild;
        }
        while (s.size()) {
            p=s.top();
            s.pop();
            cout<<p->val;
            p=p->rchild;
            while (p!=NULL) {
                s.push(p);
                p=p->lchild;
            }
        }
    }
    void postorder(tree *T)
    {
        stack<struct tree*> s;
        if (T==NULL) return;
        struct tree* p=T;
        while (p!=NULL) {
            p->flag=false;//开始为false
            s.push(p);
            p=p->lchild;
        }
        while (s.size()) {
            struct tree* p;
            p=s.top();
            if (p->flag==true||p->rchild==NULL) {//判断条件
                cout<<p->val;
                s.pop();
            }
            else {
                p->flag=true;
                p=p->rchild;
                while (p!=NULL) {
                    p->flag=false;
                    s.push(p);
                    p=p->lchild;
                }
            }
        }
    }
    int main()
    {
        while (cin>>str) {
            struct tree* Tree;
            cur=0;len=str.size();
            build(Tree);
            firstorder(Tree);cout<<endl;
            midorder(Tree);cout<<endl;
            postorder(Tree);cout<<endl;
        }
        return 0;
    }