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

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

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

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

输入

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

输出

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

示例输入

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

示例输出

cbegdfa
cgefdba
3
5

#include<bits/stdc++.h>  

 using namespace std;  

 int k;  

 typedef struct node  
 {  
     char a;  
     node *l,*r;  
 }*tree;  

 tree create(tree t)  
 {  
     char p;  
     cin>>p;  
     if(p==',')  
        t=NULL;  
     else  
     {  
         t=new node;  
         t->a=p;  
         t->l=create(t->l);  
         t->r=create(t->r);  
     }  
     return t;  
 }  

 void zhongxu(tree t)  
 {  
     if (t)  
     {  
         zhongxu(t->l);  
         cout<<t->a;  
         zhongxu(t->r);  
     }  
 }  

 void houxu(tree t)  
 {  
     if (t)  
     {  
         houxu(t->l);  
         houxu(t->r);  
         cout<<t->a;  
     }  
 }  

 void count(tree t)  
 {  
     if (t)  
     {  
         if (t->l==NULL&&t->r==NULL)  
            k++;  
         count(t->l);  
         count(t->r);  
     }  
 }  

 int deep(tree t)  
 {  
     int l,r;  
     if (t)  
     {  
         l=deep(t->l);  
         r=deep(t->r);  
         return (l>r?l:r)+1;  
     }  
     else  
        return 0;  
 }  

 int main()  
 {  
     tree t;  
     t=create(t);  
     zhongxu(t);  
     cout<<endl;  
     houxu(t);  
     cout<<endl;  
     count(t);  
     cout<<k<<"\n"<<deep(t)<<endl;  
     return 0;  
 }