pta上的题目,不知道为啥只有80/100,求各位看看还有什么情况没考虑到?
给出一个不同的整数序列来构建二叉搜索树,并输出特定级别的节点。
输入格式:
3行。
第一行表示序列号。这个数字大于 1 小于 20。
第二行给出了不同整数的序列。整数除以逗号。您必须根据输入顺序构建树。
第三行表示层数(>=1)。根节点位于第 1 层。根的子节点位于第 2 层。依此类推。
输出格式:
1行。
以逗号分隔的数字序列。数字从左到右表示给定级别上的节点。
如果层上没有节点,则输出-1。
输入样例:
在这里给出一组输入。例如:
10
32,3,56,4,75,53,33,76,90,2,
3
输出样例:
在这里给出相应的输出。例如:
2,4,53,75,
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
typedef struct node
{
int data;
struct node *left;
struct node *right;
}*Node;
typedef struct tree
{
Node root;
}*Tree;
void insert(Tree tree, int data); //建树
void search(Node node, int level); //查找对应层
int get_height(Node node); //判断深度
int main()
{
int n;
if(scanf("%d", &n) != 1)
printf("fail");
Tree tree = (Tree)malloc(sizeof(Tree));
tree->root = NULL;
for(int i=0; i<n; i++){
int data;
if(scanf("%d", &data) != 1)
printf("fail");
getchar();
insert(tree, data);
}
int level;
if(scanf("%d", &level) != 1)
printf("fail");
search(tree->root, level);
if(get_height(tree->root) < 3)
printf("-1");
printf("\n");
return 0;
}
void insert(Tree tree, int data)
{
Node node = (Node)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
if(tree->root == NULL){ //根节点为空
tree->root = node;
}
else{
Node temp = tree->root;
while(temp != NULL){ //查找到末节点
if(temp->data > data){
if(temp->left == NULL){
temp->left = node;
break;
}
else
temp = temp->left;
}
else if(temp->data < data){
if(temp->right == NULL){
temp->right = node;
break;
}
else
temp = temp->right;
}
else
break;
}
}
}
void search(Node node, int level)
{
if(node != NULL){
if(level == 1)
printf("%d,", node->data);
else{
search(node->left, (level-1));
search(node->right, (level-1));
}
}
}
int get_height(Node node)
{
if(node == NULL)
return 0;
else{
int m1=get_height(node->left);
int m2=get_height(node->right);
int m = max(m1, m2);
return m+1;
}
}