數據結構實驗之二叉樹的建立與遍歷

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****************************************************/