求根结点到指定结点的路径

Description

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

Input

Output

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

Sample Input 

Sample Output

#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<string>#include<algorithm>#include<stack>#include<queue>#include<map>#include<vector>#include<iostream> using namespace std;typedef struct BiTNode{    char d;    struct BiTNode *l;    struct BiTNode *r;}*BiTree,BiTreeNode;char ch;bool flag; void CreateBiTree( BiTree &T){    char tmp;    if( flag)        scanf("%c",&tmp);    else    {        tmp = ch;        flag = true;    }     if( tmp == '^')        T = NULL;    else    {        T = new BiTreeNode;        T->d = tmp;        CreateBiTree( T->l);        CreateBiTree( T->r);    } } void findpath( BiTree &T, char x, vector<int> &v){    if( T == NULL)        return;    v.push_back( T->d);    if( T->d == x)    {        flag = 1;        for( int i = 0; i < v.size(); i++)            putchar(v[i]);        putchar(10);        return;    }    findpath( T->l, x, v);    findpath( T->r, x, v);    v.pop_back(); } int main(){    while( ~scanf("%c",&ch))    {        if( ch == '/n')            continue;        BiTree T = NULL;        flag = false;        CreateBiTree( T);         int n;        scanf("%d",&n);        char x;        for( int i = 1; i <= n; i++)        {            scanf(" %c",&x);            vector<int> v;            findpath( T,x,v);            //putchar(10);        }     }     return 0;}