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;}