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

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

Time Limit: 1000MSMemory Limit: 655336KB

Problem Description

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

Input

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

Output

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

Example Input

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

Example Output

cbegdfacgefdba35

Hint

Author

ma6174  

#include <iostream> #include<stdio.h> #include<algorithm> #include<malloc.h>

using namespace std; typedef struct node {     int data;     struct node *l,*r; }st; char s[10010]; int i; st *creat() {     st *root;     char ch;     ch=s[i++];     if(ch==',')     root=NULL;     else     {         root=(st *)malloc(sizeof(st));         root->data=ch;         root->l=creat();         root->r=creat();     }     return root; } void zx(st *root) {     if(root!=NULL)     {         zx(root->l);         printf("%c",root->data);         zx(root->r);     } } void hx(st *root) {     if(root!=NULL)     {         hx(root->l);         hx(root->r);         printf("%c",root->data);

    } } int yz(st *root) {     if(root==NULL)     return 0;     else if(root->l==NULL&&root->r==NULL)     return 1;     else     return yz(root->l)+yz(root->r); } int sd(st *root) {     int h,lh,rh;     if(root==NULL)     h=0;     else     {       lh=sd(root->l);       rh=sd(root->r);       if(lh>=rh)       h=lh+1;       else       h=rh+1;     }     return h; } int main() {     st *root;     int m=0,h=0;     while(~scanf("%s",s))     {         i=0;         root=creat();         zx(root);         cout<<endl;         hx(root);         cout<<endl;         m=yz(root);         cout<<m<<endl;         h=sd(root);         cout<<h<<endl;     } }