數據結構實驗之二叉樹七：葉子問題

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

已知一個按先序輸入的字符序列，如abd,,eg,,,cf,,,(其中,表示空結點)。請建立該二叉樹并按從上到下從左到右的順序輸出該二叉樹的所有葉子結點。

Input

 輸入數據有多行，每一行是一個長度小于50個字符的字符串。

Output

 按從上到下從左到右的順序輸出二叉樹的葉子結點。

Example Input

abd,,eg,,,cf,,,

xnl,,i,,u,,

Example Output

dfg

uli

Hint

Author

 xam

#include<string.h>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<queue>#include<iostream>using namespace std;typedef struct node{   char data;   struct node*l;   struct node*r;}tree;tree* creat(char *&ss)//將一個一維數組轉換建立成為一個先序建立的樹{   tree*root = new tree;   if(*ss==',')   {      ss++;      return NULL;   }   root->data = *ss++;   root->l = creat(ss);   root->r = creat(ss);   return root;}void ccout(tree*root)//層次遍歷求出所有的葉節點{   queue<tree*>q;   tree*p =NULL;   if(root)   {      q.push(root);   }   while(!q.empty())   {      p = q.front();      q.pop();      if(p->l==NULL&&p->r==NULL)      {         cout<<p->data;      }      if(p->l)      q.push(p->l);      if(p->r)      q.push(p->r);   }}int main(){   char ss[102],*p;   while(~scanf("%s",ss))   {       p =  ss;       tree* root ;       root = creat(p);       ccout(root);       cout<<endl;   }}/***************************************************User name: jk160505徐紅博Result: AcceptedTake time: 0msTake Memory: 176KBSubmit time: 2017-02-07 16:26:35****************************************************/