数据结构实验之二叉树的建立与遍历
Time Limit: 1000MS Memory limit: 65536K
题目描述
已知一个按先序序列输入的字符序列,如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树,最后求出叶子节点个数和二叉树深度。输入
输入一个长度小于50个字符的字符串。输出
输出共有4行:第1行输出中序遍历序列;
第2行输出后序遍历序列;
第3行输出叶子节点个数;
第4行输出二叉树深度。
示例输入
abc,,de,g,,f,,,
示例输出
cbegdfacgefdba35
提示
#include <stdio.h>
#include <string.h>
int tf[100];
struct node
{
char c;
struct node *r;
struct node *l;
}*que[100];
int i = 0;
struct node *root = NULL;
struct node *tmp,*now;
int lr = 1;
int add (char q)
{
if (q != ',')
{
tmp = new node;
tmp->c = q;
tmp->l = NULL;
tmp->r = NULL;
if (root == NULL)
{
root = tmp;
now = tmp;
que[i++] = now;
}else
{
if (lr)
{
now->l = tmp;
now = now->l;
que[i++] = now;
}else
{
now->r = tmp;
now = now->r;
que[i++] = now;
lr = 1;
}
}
}else
{
now = que[--i];
lr = 0;
}
}
int prizhong(struct node *root)
{
if (root->l != NULL)
prizhong (root->l);
printf ("%c",root->c);
if (root->r != NULL)
prizhong (root->r);
}
int num = 0;
int prihou(struct node *root)
{
if (root->l != NULL)
prihou (root->l);
if (root->r != NULL)
prihou (root->r);
if (root->l == NULL && root->r == NULL)
num++;
printf ("%c",root->c);
}
int shen(struct node *root)
{
int l1 = 1,l2 = 1;
if (root->l != NULL)
l1 += shen(root->l);
if (root->r != NULL)
l2 += shen(root->r);
return l1 > l2 ? l1 : l2;
}
int main()
{
char q;
while (q = getchar (),q != '\n')
{
add (q);
}
prizhong(root);
printf ("\n");
prihou(root);
printf ("\n");
i = 0;
int h = shen(root);
printf ("%d\n%d\n",num,h);
return 0;
}
/**************************************
Problem id: SDUT OJ C
User name: mxj130202陈海波
Result: Accepted
Take Memory: 260K
Take Time: 0MS
Submit Time: 2014-02-17 19:26:13
**************************************/