首页 > 试题广场 >

二叉排序树

[编程题]二叉排序树
  • 热度指数：20424 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

输入描述:
输入包含多组测试数据，每组测试数据两行。
第一行，一个数字N（N<=100），表示待插入的节点数。
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。


输出描述:
输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。
示例1

输入

5
2 5 1 3 4

输出

-1
2
2
5
3
算法知识视频讲解
开通博客
头像 大内高手
发表于 2020-03-15 15:03:29
本题考察的是二叉树的建立，并且输出父节点的值。所以函数Insert的参数里多了一个int型的变量father，记录的是父节点的值。因为二叉排序树的新增节点都是在叶子处，所以root == NULL时，新建一个结点BTree(x)。 // runtime: 5ms // space: 504K #in 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 燃烧的橘子
发表于 2023-03-01 21:16:30
#include <iostream> using namespace std; struct BTree { int val; struct BTree* lchild,*rchild; BTree(int x):val(x),lchild(nullptr), 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Coming680
发表于 2022-02-10 11:35:36
#include<iostream> using namespace std; typedef struct node { int num; struct node* left, * right; node(int n) :num(n), left(NULL), 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 总之就是非常浪漫
发表于 2023-02-20 02:52:27
#include <cstdio> using namespace std; //const int NNUM=1e8 struct TN { int data; TN* left,*right; TN(int c):data(c),left(NULL),rig 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在考古的小鱼干很有气魄
发表于 2023-03-05 12:31:28
#include <bits/stdc++.h> #define MAX 100 using namespace std; typedef struct BiTNode { int data; struct BiTNode* lchild, *rchild; } BiT 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 yyer
发表于 2023-02-10 09:52:31
#include <iostream> using namespace std; struct TreeNode{ int data; TreeNode* leftChild; TreeNode* rightChild; }; TreeNode* func(Tre 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 行动胜于言语a
发表于 2023-03-21 16:54:24
#include<cstdio> #include<vector> #include<cmath> #include<iostream> #include<map> #include<string> using namespa 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 鱼儿恋上水
发表于 2020-03-15 22:45:57
1、在递归建树的过程中返回父节点 // 在递归建树的过程中返回父节点 #include <iostream> using namespace std; struct node{ int val; node* left, *right; }; node* newNode(i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 上林清风
发表于 2023-04-14 17:35:30
#include<iostream> using namespace std; int arr[101]; typedef struct BSTNode { int data; struct BSTNode* left; struct BSTNode* right 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 苇岸弦歌
发表于 2023-02-27 12:23:26
插入过程：插入子树，返回根结点，若子树为空，则新建节点并做为根结点返回 #include <iostream> using namespace std; struct treeNode { int data; treeNode* leftChild; treeNo 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树 递归
难度：
158条回答 11754浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号