题目描述
二叉排序树,也称为二叉查找树。
可以是一颗空树,也可以是一颗具有如下特性的非空二叉树:
若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值;
若右子树非空,则右子树上所有节点关键字值均不小于根节点的关键字值;
左、右子树本身也是一颗二叉排序树。
现在给你 N 个关键字值各不相同的节点。
要求你将这些节点按顺序插入一个初始为空树的二叉排序树中。
每次成功插入一个节点后,求其相应的父亲节点的关键字值,如果没有父亲节点,则输出 −1。
输入格式
第一行包含整数 N,表示待插入的节点数。
第二行包含 N 个互不相同的正整数,表示要顺序插入节点的关键字值。
数据范围
1≤N≤100
,
节点关键字值取值范围 [1,10^8]
。
输入样例:
5
2 5 1 3 4
输出样例:
-1
2
2
5
3
C代码(用了C++的引用)
#include <stdio.h>
#include <stdlib.h>
//树结构
typedef struct TreeNode {
int data;
struct TreeNode* lchild, * rchild;
}BSTNode,*BiTree;//BST表示二叉排序树
//二叉排序树插入结点
int BST_Insert(BiTree& T, int data,BSTNode *father) {
//1.如果树为空,直接插入充当根结点
if (T == NULL)
{
//calloc申请空间时就将lchild、rchild置为了NULL,若果要用malloc,则要自己写T->lchild = T->rchild = NULL
T = (BSTNode*)calloc(1,sizeof(BSTNode));
T->data = data;
if (father)
{
return father->data;
}
return -1;//表示没有父结点
}
//2.如果该插插入的结点已经存在,则直接返回,因为题目中说各个数不同,所以这一步直接略过
//如果插入的结点小于当前根结点,则应该递归插入左子树中,反之
BSTNode* temp = T;//临时存储当前结点,充当下一结点的父结点
if (T->data > data)
{
return BST_Insert(T->lchild, data,temp);//插入到左子树中
}
if (T->data < data)
{
return BST_Insert(T->rchild, data,temp);//插入到右子树中
}
}
//创建二叉排序树
void Creat_BSTree(BiTree &T, int* datas, int n) {
T = NULL;//初始化树为空
int i = 0;
int fatherNode;
while (i < n)
{
fatherNode = BST_Insert(T, datas[i],NULL);
printf("%d\n", fatherNode);
i++;
}
}
int main() {
BiTree root;//二叉排序树
int n;
scanf("%d", &n);
int* datas = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
scanf("%d", &datas[i]);
}
Creat_BSTree(root, datas, n);
return 0;
}