如何实现数据结构实验中的二叉树构建与遍历过程？
- 内容介绍
- 文章标签
- 相关推荐
本文共计656个文字，预计阅读时间需要3分钟。
数据结构实验之二叉树的建立与遍历+Time Limit:1000 ms+Memory Limit:65536 KiB+Submit+Statistic+Problem Description已知一个按先序遍历输入的字符序列，如abc,de,g,f(其中逗号表示空节点）。请建立相应的二叉树。+Input输入为若干行，每行一个字符序列，每行末尾以逗号结束。+Output对于输入的每个字符序列，输出相应的二叉树的前序遍历、中序遍历和后序遍历结果，每行输出一个遍历结果，以空格分隔。+Sample Inputabc,de,g,f,abc,+Sample Outputabc defg,abc def,abc def,+Hint二叉树的建立可以通过递归的方式实现，遍历则可以根据需要选择不同的遍历方法。
数据结构实验之二叉树的建立与遍历
Time Limit:1000 msMemory Limit:65536 KiB
SubmitStatistic
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;
}
本文共计656个文字，预计阅读时间需要3分钟。
数据结构实验之二叉树的建立与遍历+Time Limit:1000 ms+Memory Limit:65536 KiB+Submit+Statistic+Problem Description已知一个按先序遍历输入的字符序列，如abc,de,g,f(其中逗号表示空节点）。请建立相应的二叉树。+Input输入为若干行，每行一个字符序列，每行末尾以逗号结束。+Output对于输入的每个字符序列，输出相应的二叉树的前序遍历、中序遍历和后序遍历结果，每行输出一个遍历结果，以空格分隔。+Sample Inputabc,de,g,f,abc,+Sample Outputabc defg,abc def,abc def,+Hint二叉树的建立可以通过递归的方式实现，遍历则可以根据需要选择不同的遍历方法。
数据结构实验之二叉树的建立与遍历
Time Limit:1000 msMemory Limit:65536 KiB
SubmitStatistic
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;
}