不废话直接上题目跟代码了。
标题:求二叉树的深度
描述:给出一个字符串形式表达的二叉树,求出指定节点深度。
输入的树形结构字符串格式为:
1、以父节点、左子树、右子树表示的二叉树;每个父节点不会超过两个子节点;
2、树的每一个节点采用单个字母表示;树的层次采用数字表示,树根节点不会超过两个子节点;
3、字符串以“节点名称 层次数 节点名称 层次数...”的形式出现,同一个父节点下,先出现的为左子树。
例如字符串“a1b2c2d3e3f3”生成一颗如下树:
a
/ \
b c
/ \ /
d e f
节点a的深度为3,节点b 的深度为2,节点f的深度为1
时间限制: 无限制
内存限制: 无限制
输入: 一行字符串,表示一个二叉树
输出: 一行字符串,一个字符一个节点,输入确保字符不会存在重复节点
输出: 指定节点深度,如果节点不存在,返回0;整数之间用空格隔开
样例输入: a1b2c2d3e3f3
样例输出: 3 2
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#define max 100
char* input_str1()
{
static char input_char1[max]={'0'};
int len1;
int i,j,k=0,l,m;
int h[26]={0};//字符出现次数统计数组
scanf("%s",input_char1);
len1 = strlen(input_char1);
if(len1%2 == 0)
{
for(i = 1 ; i < len1-3; i = i+2)
if(input_char1[i] > input_char1[i+2])
exit(0);
for( j = 0 ; j < len1-2 ; j = j + 2 )
{
k=(int)(input_char1[j]-'a');
h[k]++;
}
}
else
exit(0);
for( l = 0 ; l < 26 ; l++)
if(h[l] >= 2)
exit(0);
//for(m=0;m<len1;m++)
// printf("%c",input_char1[m]);
return input_char1;
}
char *input_str2()
{
static char input_char2[max]={'0'};
int i,len2,k=0,l,m;
int h[26] = {0};
scanf("%s",input_char2);
len2=strlen(input_char2);
for(i = 0 ; i < len2 ; i++)
{
k = (int)(input_char2[i]-'a');
h[k]++;
}
for( l = 0 ; l < 26 ; l++)
if(h[l] >= 2)
exit(0);
//for(m=0;m<len2;m++)
// printf("%c",input_char2[m]);
return input_char2;
}
int* output(char *input_char1,char *input_char2)
{
// char input_char1[13]="a1b2c2d3e3f3";
// char input_char2[3]="ab";
int output_num[max]={0};
int i;
int in_num1;
int j=0,k=0,l;
int out_num;
int max_layer;
out_num = strlen(input_char2);
in_num1 = strlen(input_char1);
max_layer = (int)(input_char1[in_num1-1]-'0');
for(i = 0 ; i <= in_num1-2 && k < out_num ; i = i + 2)
{
if( input_char1[i] == input_char2[j] )
{
j++;
output_num[k]=max_layer-(int)(input_char1[i+1]-'0')+1;
k++;
}
else if( i == in_num1-2 && input_char1[i] != input_char2[j] )
{
j++;
output_num[k]=0;
k++;
}
}
// for(l=0;l<out_num;l++)
// printf("%d ",output_num[l]);
return output_num;
}
void main()
{
int i=0;
int m=0;
char *input_c1;
char *input_c2;
int *result_arr;
input_c1 = input_str1();
puts(input_c1);
input_c2 = input_str2();
puts(input_c2);
result_arr = output(input_c1 , input_c2);
m = strlen(input_c2);
for(i = 0; i < m ; i++)
printf("%d ",result_arr[i]);
printf("\n");
}
注:程序没有考虑每层元素的数量限制问题,比如根层最多1个,然后2个,然后4个...以及最多9层的限制。如果有心,看官可以自己编程加进去!
在此仅供学习!