sdutacm-数据结构实验之二叉树的建立与遍历

数据结构实验之二叉树的建立与遍历

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

      已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。

Input

 输入一个长度小于50个字符的字符串。

Output

输出共有4行：第1行输出中序遍历序列；第2行输出后序遍历序列；第3行输出叶子节点个数；第4行输出二叉树深度。

Example Input

abc,,de,g,,f,,,

Example Output

cbegdfa

cgefdba

3

5

Hint

Author

 ma6174

#include <iostream>#include<string.h>#include<stdio.h>#include<algorithm>#include<math.h>#include<stdlib.h>using namespace std;int num;typedef struct node{   int data;   struct node *l;   struct node *r;}tree;tree *creat(char *&ss){   /*if(*ss=='/0')   return NULL;*/   if(*ss==',')   {      ss++;      return NULL;   }   tree*p = (tree*)malloc(sizeof(tree));   p->data = *ss++;   p->l = creat(ss);   p->r = creat(ss);   return p;}/*tree *creat(tree*p){    char c;    if((c=getchar())==',')    {       p  =NULL;    }    else    {       p = (tree*)malloc(sizeof(tree));       p->data = c;       p->l = creat(p->l);       p->r = creat(p->r);    }   return p;}*/void intravel(tree*p){  if(p)  {      intravel(p->l);      printf("%c",p->data);      intravel(p->r);  }}void lasttravel(tree*p){   if(p)   {       lasttravel(p->l);       lasttravel(p->r);       printf("%c",p->data);   }}void leaves(tree *p){     if(p)     {        if(p->l==NULL&&p->r==NULL)         num++;         leaves(p->l);         leaves(p->r);     }}int deep(tree*p){     if(!p)     return 0;     else     {        return (max(deep(p->l),deep(p->r))+1);     }}int main(){    char ss[51],*p;//定义一个指针和缓存数组；    while(~scanf("%s",ss))    {    p = ss;    tree *root;    root = (tree*)malloc(sizeof(tree));    root = creat(p);    num = 0;    intravel(root);    cout<<endl;    lasttravel(root);    leaves(root);    cout<<endl<<num<<endl;    int shen = deep(root);    cout<<shen<<endl;    }    return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 0msTake Memory: 152KBSubmit time: 2017-02-07 10:27:00****************************************************/