数据结构实验之二叉树七：叶子问题

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: Accepted
Take time: 0ms
Take Memory: 176KB
Submit time: 2017-02-07 16:26:35
****************************************************/