数据结构实验之二叉树的建立与遍历
Time Limit: 1000MS Memory limit: 65536K
题目描述
已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。
输入
输入一个长度小于50个字符的字符串。
输出
输出共有4行：
第1行输出中序遍历序列；
第2行输出后序遍历序列；
第3行输出叶子节点个数；
第4行输出二叉树深度。
第1行输出中序遍历序列；
第2行输出后序遍历序列；
第3行输出叶子节点个数；
第4行输出二叉树深度。
示例输入
abc,,de,g,,f,,,
示例输出
cbegdfacgefdba35
提示
来源
ma6174
示例程序
DBEFCA#include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct node{ char data ; node *lchild , *rchild ; }*tree; //建立一个先序的二叉树 void low(tree &t) { char ch ; scanf("%c", &ch); if(ch==',') t = NULL ; else { t = new node; t->data = ch ; low(t->lchild); low(t->rchild); } return ; } //中序遍历 void mid(tree t) { if(t) { mid(t->lchild); printf("%c", t->data); mid(t->rchild); } return ; } //后序遍历 void high(tree t) { if(t) { high(t->lchild); high(t->rchild); printf("%c", t->data); } } int leaf(tree t,int &num) { if(t) { if(!t->lchild && !t->rchild) { num++; return 0; } if(t->lchild) leaf(t->lchild,num); if(t->rchild) leaf(t->rchild,num); } return 0; } int getdepth(tree t) { int depth = 0; if(!t)return depth ; int nl = getdepth(t->lchild); int nr = getdepth(t->rchild); if(nr > nl) depth = nr+1; else depth = nl+1; return depth ; } int main() { int num = 0 ; tree head ; low(head); mid(head); printf("\n"); high(head); printf("\n"); leaf(head,num); printf("%d\n", num); printf("%d\n", getdepth(head)); return 0; }