个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
27
4
二叉搜索树（ Binary Search Tree ）也称二叉排序树，是一种各节点值之间存在一定次序关系的二叉树.
一般情况下，二叉搜索树中所有节点值是不重复的。 对于二叉搜索树中的每个节点： （1）如果其左子树不为空，那么其左边的节点值都比当前节点值小； （2）如果其右子树不为空，那么其右边的节点值都比当前的节点值要大.
二叉搜索树的中序遍历结果，就是所有节点值升序排序的结果.
根据二叉搜索树的特点，其实二叉搜索树中的查找和二分查找非常相似。从树的根节点出发，当前节点值 val 如果等于目标值 target ，那么就直接返回；如果 val 小于目标值 target ，那么就要往左边去寻找；如果 val 大于目标值 target ，那么就要往右边去寻找。假如最后节点为 NULL ，都没有找到等于目标值的节点，那么说明此时的二叉搜索树中不存在这个等与目标值 target 的节点.
我们将使用递归函数来实现这一过程，假设函数名为 SearchBST ，则大致步骤为： （1）节点为空，没有等于目标值的节点 if(!root) return NULL ； （2）当前节点值小于目标值 if(root->val < target) return SearchBST(root->left) ； （3）当前节点值大于目标值 if(root->val > target) return SearchBST(root->right) ； （4）找到该节点 return root .
//递归 查找二叉排序树指定元素target
BinaryTree Search_BST(BinaryTree root, Elemtype target){
if(!root) //最后没有找到root为NULL
return NULL;
if(target > root->val) //root值小于target 往其右子树查找
return Search_BST(root->rightchild, target);
if(target < root->val) //root值大于target 往其左子树查找
return Search_BST(root->leftchild, target);
return root; //找到直接返回该节点
}
二叉搜索树插入的元素，首先一定是当前二叉搜索树中不存在的元素，如果要插入的元素 val 已经存在于二叉搜索树中，那么就没有插入的必要了.
二叉搜索树插入新元素，同时还需要使整棵树保持二叉搜索树的性质。所以在插入过程中，我们依旧需要用类似于二分查找的形式来实现插入的操作。从树的根节点出发，如果当前节点为空，说明可以插入到这个位置；如果插入元素 val 与当前节点值相等，说明已经存在，直接 return；如果插入元素 val 小于当前节点值，那么递归往左寻找合适的插入位置；如果插入元素 val 大于当前节点值，那么递归往右寻找合适的插入位置.
我们还是用递归函数来实现这个插入的过程，也是创建二叉搜索树的过程。 假定函数名为 InsertBST ，则大致步骤为： （1）当前节点位置为空，可以插入，创建一个新节点 root = new Node(val) ； （2）当前节点值与插入元素值相等，直接 return ； （3）插入元素 val 小于当前节点值，则进行 InsertBST(root->left, val) ； （4）插入元素 val 大于当前节点值，则进行 InsertBST(root->right, val) .
//二叉排序树元素的插入
void Insert_BST(BinaryTree &root, Elemtype val){
if(!root){ //若为当前root为空
BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
node->val = val;
node->leftchild = node->rightchild = NULL;
root = node;
return;
}
if(root->val == val)
return; //当前值已经存在 则不插入
/* 递归写法 */
if(root->val > val)
Insert_BST(root->leftchild, val);
else
Insert_BST(root->rightchild, val);
}
由于删除节点为叶子结点，直接置 NULL 即可，删除完之后不会对整棵树满足二叉搜索树性质产生任何影响.
这一类删除的节点的特点为其只有一个子树，另一个子树为空。这种情况往往也是比较方便处理的.
当删除节点只有右子树时，为了维持二叉搜索树的特点，只需要将删除节点的右子树继承给其父节点就可以，并且做到了将该节点删除.
假定 root 为当前要删除的节点，直接 root = root->right .
当删除节点只有左子树时，为了维持二叉搜索树的特点，和上一种情况也类似，将左子树继承给其父节点.
假定 root 为当前要删除的节点，直接 root = root->left .
这一类删除的节点同时含有左子树和右子树，此时的处理是比较麻烦的，但是整理好思路就不难.
本质上，我们要找到当前删除的节点的右子树中的节点值最小的节点，也就是右边第一个大于当前删除节点的节点。我们用 s 来指向这个节点，后期我们将其作为代替当前删除的节点.
但是， s 情况的不同也会导致一些处理上的区别.
s 指向的是右子树中的最小的节点，如果右子树的左子树为空，也就是说右子树的根节点即右子树中最小的节点。那么此时 s 就指向这个右子树根节点，然后只需要将删除节点 root 的左子树继承给 s 的 left ，最后将 s 代替删除节点 root 就可以了。这样就可以保持二叉搜索树的性质.
（1）此时 s 就指向 root->right ； （2）将 root->left 继承给 s->left ； （3） s 代替删除节点， root = s .
s 指向的是右子树中的最小的节点，假如右子树的左子树不为空，那么我们首先要先一直向左搜索，直到右子树的最左边，即找到最左边的节点。而且这个最左边的节点一定是没有左子树的，但是可能存在右子树。为了能够顺利的让 s 代替删除节点 root ，根据 s 一定是其父节点的左子树的特点，我们需要先将 s 的右子树继承给其父节点 parent ，然后此时的 s 就形成一个单独的节点。最后将删除节点 root->left 赋给 s 的左子树，将 root->right 赋给 s 的右子树，将 root = s 完成代替操作.
为了将 s 的右子树继承给其父节点 parent ，在右子树中一直往左寻找最左边的节点时，我们需要定义 parent 来记录其父节点.
（1）在删除节点 root 的右子树中一直往左搜索，找到最左边的节点 s ； （2）将 s 的右子树继承给 parent ， parent->left = s->right ； （3）将 root 的左右子树继承给 s ， s->left = root->left, s->right = root->right ； （4）最后 root = s .
//二叉排序树元素的删除
void Delete_BST(BinaryTree &root, Elemtype val){
BinaryTree t = root, parent = NULL, s = NULL;
if(!t){ //要删除节点不存在
puts("要删除的节点不存在");
return;
}
//当前的root为要删除的节点
if(t->val == val){
if(!t->leftchild && !t->rightchild){ //要删除的节点是一个叶子结点 直接置NULL
root = NULL;
}
else if(!t->leftchild && t->rightchild){ //要删除的节点只有右子树，将其右子树的根节点代替删除节点
root = t->rightchild;
}
else if(t->leftchild && !t->rightchild){ //要删除的节点只有左子树，将其左子树的根节点代替删除节点
root = t->leftchild;
}
/* **个人认为最难的地方 采用迭代法** */
else{ //要删除的节点既有左子树，又有右子树
s = t->rightchild; //记录删除节点的右子树根节点
//找到右子树中最小的节点
if(!s->leftchild){ //如果此时的s没有左儿子，直接把删除节点的左子树变为此时s(删除节点右儿子)的左子树
s->leftchild = t->leftchild;
}else{
while(s->leftchild){ //找到删除节点的右子树中最左边的节点s 即第一个大于删除节点值的节点(后期将其代替删除节点的位置)
parent = s; //记录代替位置节点的父节点
s = s->leftchild;
}
parent->leftchild = s->rightchild;//若代替位置节点有右子树，把其右子树继承给父节点(重构删除节点的右子树)
s->leftchild = t->leftchild; //删除节点的左子树变为代替节点的左子树
s->rightchild = t->rightchild; //删除节点的右子树变为代替节点的右子树
}
root = s; //最后将当前s代替要删除的节点
}
free(t);
}
else if(val > t->val){
Delete_BST(t->rightchild, val); //向其右子树寻找要删除的节点
}
else if(val < t->val){
Delete_BST(t->leftchild, val); //向其左子树寻找要删除的节点
}
}
ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度.
其中 i 表示当前层级， numi 表示第 i 层的节点个数， nodesum 表示整颗二叉搜索树的节点个数.
//计算二叉树节点的个数
int Nodenum_of_BST(BinaryTree root){
if(!root)
return 0;
return Nodenum_of_BST(root->leftchild) + Nodenum_of_BST(root->rightchild) + 1;
}
其中 i 表示当前层级， supplei 表示第 i 层的要补全的节点个数， supplesum 表示整颗二叉搜索树的要补全的总节点个数.
double sum1 = 0, sum2 = 0;
//全局变量 sum1 = ∑(各层节点数 × 对应层级), sum2 = ∑(各层补全节点 × (对应层级-1)）
int n0 = 0, n1 = 0;
//全局变量 分别用于计算每一层叶子节点 和 度数为1的节点
int supplesum = 0;
//全局变量 计算补全的节点总数
//层次遍历 并利用队列计算二叉树每一层的节点个数
void Show_Level_Order(BinaryTree root){
if(!root)
return;
BinaryTree t = NULL;
int level = 1;
std::queue<BinaryTree> q;
q.push(root);
while(!q.empty()){
n0 = n1 = 0;
int n = q.size();
for(int i = 0; i < n; i++){
t = q.front();
q.pop();
printf("%d ", t->val);
if(t->leftchild) q.push(t->leftchild);
if(t->rightchild) q.push(t->rightchild);
if(!t->leftchild && !t->rightchild)
n0 ++ ; //度数为0的节点
if(!t->leftchild && t->rightchild || t->leftchild && !t->rightchild)
n1 ++ ; //度数为1的节点
}
printf("\n");
sum1 += n * level; //每一层节点个数*层级
sum2 += (n0 * 2 + n1) * level; //每一层下方需补全节点*层级
supplesum += (n0 * 2 + n1); //补全的节点个数
level++;
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<vector>
#include<queue>
#include<algorithm>
typedef int Elemtype;
typedef struct BiNode{
Elemtype val;
struct BiNode *leftchild, *rightchild;
}BiNode, *BinaryTree;
//递归 查找二叉排序树指定元素target
BinaryTree Search_BST(BinaryTree root, Elemtype target){
if(!root) //最后没有找到root为NULL
return NULL;
if(target > root->val) //root值小于target 往其右子树查找
return Search_BST(root->rightchild, target);
if(target < root->val) //root值大于target 往其左子树查找
return Search_BST(root->leftchild, target);
return root; //找到直接返回该节点
}
//二叉排序树元素的插入
void Insert_BST(BinaryTree &root, Elemtype val){
if(!root){ //若为当前root为空
BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
node->val = val;
node->leftchild = node->rightchild = NULL;
root = node;
return;
}
if(root->val == val)
return; //当前值已经存在 则不插入
/* 递归写法 */
if(root->val > val)
Insert_BST(root->leftchild, val);
else
Insert_BST(root->rightchild, val);
}
/* 迭代写法 */
/*
BinaryTree t = root, inroot = NULL;
//t为遍历指针 inroot记录要插入位置的父节点
while(t){
inroot = t;
t = (val < t->val) ? t->leftchild : t->rightchild;
}
if(val < inroot->val)
inroot->leftchild = node;
else
inroot->rightchild = node;
*/
//二叉排序树元素的删除
void Delete_BST(BinaryTree &root, Elemtype val){
BinaryTree t = root, parent = NULL, s = NULL;
if(!t){ //要删除节点不存在
puts("要删除的节点不存在");
return;
}
//当前的root为要删除的节点
if(t->val == val){
if(!t->leftchild && !t->rightchild){ //要删除的节点是一个叶子结点 直接置NULL
root = NULL;
}
else if(!t->leftchild && t->rightchild){ //要删除的节点只有右子树，将其右子树的根节点代替删除节点
root = t->rightchild;
}
else if(t->leftchild && !t->rightchild){ //要删除的节点只有左子树，将其左子树的根节点代替删除节点
root = t->leftchild;
}
/* **个人认为最难的地方 采用迭代法** */
else{ //要删除的节点既有左子树，又有右子树
s = t->rightchild; //记录删除节点的右子树根节点
//找到右子树中最小的节点
if(!s->leftchild){ //如果此时的s没有左儿子，直接把删除节点的左子树变为此时s(删除节点右儿子)的左子树
s->leftchild = t->leftchild;
}else{
while(s->leftchild){ //找到删除节点的右子树中最左边的节点s 即第一个大于删除节点值的节点(后期将其代替删除节点的位置)
parent = s; //记录代替位置节点的父节点
s = s->leftchild;
}
parent->leftchild = s->rightchild;//若代替位置节点有右子树，把其右子树继承给父节点(重构删除节点的右子树)
s->leftchild = t->leftchild; //删除节点的左子树变为代替节点的左子树
s->rightchild = t->rightchild; //删除节点的右子树变为代替节点的右子树
}
root = s; //最后将当前s代替要删除的节点
}
free(t);
}
else if(val > t->val){
Delete_BST(t->rightchild, val); //向其右子树寻找要删除的节点
}
else if(val < t->val){
Delete_BST(t->leftchild, val); //向其左子树寻找要删除的节点
}
}
/* 二叉排序树删除操作 个人认为最难地方 else情况的递归写法 */
//*******前面部分都一样
/*
else{
s = Search_BST_Min(t->rightchild); //找到右子树最小值的节点 即代替删除节点的节点s
t->rightchild = Delete_BST(t->rightchild, s->val);
//递归 对删除节点的右子树进行删除要代替节点的操作
s->leftchild = t->leftchild;
s->rightchild = t->rightchild;
root = s; //最后将s代替当前删除的节点
}
*/
//*******后面部分都一样
//二叉排序树的创建
void Create_BST(BinaryTree &root, std::vector<Elemtype> &v){
for(auto x : v) Insert_BST(root, x);
}
//中序遍历
void Show_Infix_Order(BinaryTree root){
if(!root)
return;
Show_Infix_Order(root->leftchild);
printf("%d ", root->val);
Show_Infix_Order(root->rightchild);
}
//计算二叉树节点的个数
int Nodenum_of_BST(BinaryTree root){
if(!root)
return 0;
return Nodenum_of_BST(root->leftchild) + Nodenum_of_BST(root->rightchild) + 1;
}
//计算二叉树最大深度
int Depth_of_BST(BinaryTree root){
if(!root)
return 0;
return std::max(Depth_of_BST(root->leftchild), Depth_of_BST(root->rightchild)) + 1;
}
double sum1 = 0, sum2 = 0;
//全局变量 sum1 = ∑(各层节点数 × 对应层级), sum2 = ∑(各层补全节点 × (对应层级-1)）
int n0 = 0, n1 = 0;
//全局变量 分别用于计算每一层叶子节点 和 度数为1的节点
int supplesum = 0;
//全局变量 计算补全的节点总数
//层次遍历 并利用队列计算二叉树每一层的节点个数
void Show_Level_Order(BinaryTree root){
if(!root)
return;
BinaryTree t = NULL;
int level = 1;
std::queue<BinaryTree> q;
q.push(root);
while(!q.empty()){
n0 = n1 = 0;
int n = q.size();
for(int i = 0; i < n; i++){
t = q.front();
q.pop();
printf("%d ", t->val);
if(t->leftchild) q.push(t->leftchild);
if(t->rightchild) q.push(t->rightchild);
if(!t->leftchild && !t->rightchild)
n0 ++ ; //度数为0的节点
if(!t->leftchild && t->rightchild || t->leftchild && !t->rightchild)
n1 ++ ; //度数为1的节点
}
printf("\n");
sum1 += n * level; //每一层节点个数*层级
sum2 += (n0 * 2 + n1) * level; //每一层下方需补全节点*层级
supplesum += (n0 * 2 + n1); //补全的节点个数
level++;
}
}
//计算二叉排序树的平均查找长度(查找成功的情况)
double ASL_Success(BinaryTree root){
return double(sum1 / Nodenum_of_BST(root));
}
//计算二叉排序树平均查找长度(查找失败的情况)
double ASL_Fail(BinaryTree root){
return double(sum2 / supplesum);
}
//递归验证二叉排序树 节点的左右边界
bool IsBST(BinaryTree root, int lower, int upper){
if(!root)
return true;
if(root->val <= lower || root->val >= upper)
return false;
return IsBST(root->leftchild, lower, root->val) && IsBST(root->rightchild, root->val, upper);
}
int main(){
BinaryTree T = NULL;
std::vector<Elemtype> v = {17, 12, 19, 10, 15, 18, 25, 8, 22};
Create_BST(T, v);
printf("创建二叉排序树 中序遍历结果: \n");
Show_Infix_Order(T);
printf("\n\n");
printf("验证当前二叉树是否为二叉排序树 \n");
if(IsBST(T, INT_MIN, INT_MAX))
puts("此二叉树为二叉排序树");
else
puts("此二叉树不是二叉排序树");
printf("\n");
int e;
printf("输入要查找的元素: ");
scanf("%d", &e);
if(Search_BST(T, e))
printf("找到该元素, 其地址为: %d\n", Search_BST(T, e));
else
puts("没有找到该元素");
printf("\n");
printf("输入要删除的元素: ");
scanf("%d", &e);
Delete_BST(T, e);
printf("\n进行删除操作后的二叉排序树 层次遍历: \n");
Show_Level_Order(T);
printf("\n\n");
printf("当前二叉排序树的最大深度为: %d\n", Depth_of_BST(T));
printf("\n");
printf("∑(各层节点数 × 当前层): %d\n", int(sum1));
printf("当前二叉搜索树节点个数: %d\n", Nodenum_of_BST(T));
printf("查找成功的平均查找长度为: %lf\n", ASL_Success(T));
printf("\n");
printf("∑(各层补全节点数 × (当前层 - 1)): %d\n", int(sum2));
printf("当前二叉搜索树需补全的节点个数: %d\n", supplesum);
printf("查找失败的平均查找长度为: %lf\n", ASL_Fail(T));
printf("\n");
system("pause");
}
最后此篇关于[数据结构]二叉搜索树(二叉排序树)的文章就讲到这里了,如果你想了解更多关于[数据结构]二叉搜索树(二叉排序树)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 7 年前。 Improve th
我在使用 fork 和 pipes 制作一个用于学习目的的简单程序时遇到了问题。我想要一个 child 向 parent 发送一些数据，然后这个( parent )再次将它发送给 child 。 结果
我正在制作一个需要同时做 3 件事的 python 脚本。什么是实现此目的的好方法，就像我听说的关于 GIL 的方法一样，我不再那么倾向于使用线程了。 脚本需要做的两件事将非常活跃，他们将有很多工作要
有没有办法运行sshd以便它可以(至少对于有限数量的登录)成功返回提示(可能是 busybox)，即使 fork 不可用(例如，PID 不足)？ 在我看来，这应该是可能的，例如，sshd 预 fork
我意识到 Bootstrap 将使用 v4 切换到 rem。但是，我使用的是当前版本 (v3)，我想使用 rem。 原因？我希望网站上有可以为最终用户缩放字体大小的按钮。我相信最好的实现方式是使用 r
我试图在这个程序中将信息从子进程传递到父进程。这是到目前为止的代码，仍在清理它: #include #include #include #include main() { char *
我试图理解 fork 在 C 中是如何工作的，但我在某个地方误解了一些东西。 我去年遇到了一位教授给我的测试，但我无法回复它:我们有 3 个任务(进程或线程)，伪代码如下: Th1 { display
我在使用 fork() 之类的东西时遇到了一些麻烦。 我正在开发一个 shell，用户可以在其中编写将像在普通普通 shell 中一样执行的命令。 我有一个像这样的主要功能: void Shell::
我有一个 Python 主进程，以及由主进程使用 os.fork() 创建的一组或多个 worker . 我需要将大型且相当复杂的数据结构从工作程序传递回主进程。您会为此推荐哪些现有库？ 数据结构是列
我对这个 fork 语句很陌生，我不知道 C 程序上的 fork 方法。你能告诉我这段代码的三个可能的输出是什么吗？ #include #include int main(void) {
for(i=0;i #include int main() { for(int i=0;i<2;i++) { if(fork()==0) { printf("Hi %d %d
背景 我正在用 C 语言编写一个共享库，与 LD_PRELOAD 动态链接，这意味着拦截和覆盖预加载它的应用程序的网络调用，例如 socket()、connect()、recv()、send()等 在
我是一名优秀的程序员,十分优秀！