数据结构实验之二叉树的建立与遍历
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。
Input
输入一个长度小于50个字符的字符串。
Output
输出共有4行：
第1行输出中序遍历序列；
第2行输出后序遍历序列；
第3行输出叶子节点个数；
第4行输出二叉树深度。
Sample Input
abc,,de,g,,f,,,
Sample Output
cbegdfa cgefdba 3 5
Hint
Source
ma6174
#include <stdio.h> #include <stdlib.h> #include <string.h> char a[101]; int l; struct node//二叉树的定义 { char data; struct node *lc; struct node *rc; }; struct node *creat()//老套路了，知道先序和中序搞出整棵树 { struct node *root; char c; c = a[l++]; if(c == ',') { return NULL; } else { root = (struct node *)malloc(sizeof(struct node)); root->data = c; root->lc = creat(); root->rc = creat(); } return root; } void mid(struct node *root) { if(root != 0) { mid(root->lc); printf("%c", root->data); mid(root->rc); } } void after(struct node *root) { if(root != 0) { after(root->lc); after(root->rc); printf("%c", root->data); } } int leav(struct node *root) { if(root == NULL) { return 0; } if(root->lc == NULL && root->rc == NULL) { return 1; } else { return leav(root->lc) + leav(root->rc); } } int deep(struct node *root)//求深度的话，就看左右子树哪个更深就返回哪个的深度，最后加个1就是整棵树的深度了 { int d = 0; if(root != NULL) { int d1 = deep(root->lc); int d2 = deep(root->rc); if(d1 >= d2) { d = d1 + 1; } else { d = d2 + 1; } } else { return 0;//一定到最后没有左右子树的话要返回0，这样就不会又加1了 } return d; } int main() { int k; struct node *root; while(scanf("%s", a) != EOF) { l = 0; root = (struct node *)malloc(sizeof(struct node)); root =creat(); mid(root); printf("\n"); after(root); printf("\n"); k = leav(root); printf("%d\n", k); printf("%d\n", deep(root)); } return 0; }
