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

时间:2021-05-24 10:31:16

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

   

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
**************************************/