wustoj(二叉树根节点到指定结点的路径-非递归算法)

妖狐艹你老母 2022-06-05 05:09 147阅读 0赞

问题描述:

二叉树采用二叉链表存储结构进行存储，需要输出从二叉树的树根到指定结点的完整路径。按照给出的先序序列根据教材中算法6.4所示的算法建立二叉链表。二叉树中每个结点的数据都不相同。

Input

包含多组测试数据。

每组测试数据的第一行给出二叉树的先序遍历序列（结点数至少1个，不超过100个），用于建立二叉链表存储的二叉树。

第二行一个整数m，表示有m个结点需要输出从根节点到它自己的路径。

接下来m行，每行一个字符c，表示需要输出从根节点到本结点的路径。

Output

每组数据输出m行，每行为一个从根节点到对应结点之间的路径。

ABC^^DE^G^^F^^^  
3  
A  
D  
G

ABD

ABDEG

题目分析:二叉树上找路径（非递归算法），主要利用的是二叉树的后序遍历的非递归算法， [点这里][Link 1]

后序遍历中，栈顶如果是对应的指定节点，那么这个栈就保存的是这条路径。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<stack>
    #include<string>
    using namespace std;
    
    string str;
    int cur,len,n;
    char e;
    struct tree
    {
        char val;
        struct tree* lchild,*rchild;
        bool flag;
    }*Tree;
    stack<struct tree*> s,ans;
    void build(struct tree* &T)
    {
        if (cur>=len) return ;
        if (str[cur]=='^') {
            T=NULL;;
            cur++;
            return ;
        }
        else {
            T=new struct tree();
            T->val=str[cur];
            cur++;
            build(T->lchild);
            build(T->rchild);
        }
    }
    
    void postorder(struct tree* T)
    {
        if (T==NULL) return ;
        struct tree* p=T;
        while (p!=NULL) {
            p->flag=false;
            s.push(p);
            p=p->lchild;
        }
        while (s.size()) {
            struct tree* p=s.top();
            if (p->flag==true||p->rchild==NULL) {
                if (p->val==e) return ;
                else {
                    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) {
            cin>>n;
            cur=0;len=str.size();
            build(Tree);
            while (n--) {
                cin>>e;
                while (s.size()) s.pop();
                postorder(Tree);
                while (s.size()) {//注意这条路径是倒着的
                    struct tree* p=s.top();
                    s.pop();
                    ans.push(p);
                }
                while (ans.size()) {
                    struct tree* p=ans.top();
                    ans.pop();
                    cout<<p->val;
                }
                cout<<endl;
            }
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/wust_cyl/article/details/78445613