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

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: Accepted
Take time: 0ms
Take Memory: 152KB
Submit time: 2017-02-07 10:27:00
****************************************************/