二元排序树删除值小于value的节点

当同学去阿里巴巴考试时，他们需要编写代码:

现在有一个二进制排序树，每个节点保存一个int类型的值，删除值小于10的节点（该树可能不包含值10的节点），讨论这个想法，写算法.

不要拿出最初的错误想法并误导所有人. 我只能说我想简化一下. 我花了几天的空闲时间思考这个问题，最后编写了代码. 虽然我想了一会儿，但毕竟还是写的.

二叉树的常见问题和解决方案

【递归】二叉树的序列建立和遍历

用Java实现的二叉树结构

【非递归】二叉树的建立和遍历

二叉树和双指针的递归实现

我自己测试数据或绘制图片后，我觉得困难很少

1. 如果数据是这样的: 6,5,7,8,15，则根节点的值小于10，然后在右子树中有一个大于10的节点. 节点，您需要重新调整根节点

2. 如果数据是这样的: 6,5,7,8,15,14,9,8,13,11,10，也就是说，它开始小于10，然后右边的子树显示为大于10，导致峰值循环. 左子树中的节点少于10个. 实际上，这组数据基本上包含了核心代码的思想

代码思想: 如果当前节点小于10二叉排序树删除，则循环遍历右侧子树，直到找到第一个大于10的节点p，然后调整树结构，然后循环遍历p的左侧子树，直到找到另一个. 出现第一个小于10的节点，然后递归搜索左右子树，直到没有大于10的节点.

代码如下，其中标题要求删除的值是10. 当然，删除值小于val的节点更为普遍（如果节点值等于val，则也会删除该值）. 删除）. 另外，在创建树时为了方便测试代码，它是随机生成的二叉排序树删除，但是对于相同的值，它将被自动忽略，即树中所有节点的值都是唯一的:

#include

#include

#include

struct biTree {

struct biTree * lchild，* rchild;

int数据；

};

struct biTree * createBST（struct biTree * root，int val）{

if（root == NULL）{

root =（struct biTree *）malloc（sizeof（struct biTree））;

root-> data = val;

root-> lchild = root-> rchild = NULL;

返回根；

}

if（val 数据）root-> lchild = createBST（root-> lchild，val）;

否则if（val> root-> data）root-> rchild = createBST（root-> rchild，val）;

返回根；

}

void inOrder（结构biTree *根）{

如果（root == NULL）返回;

inOrder（root-> lchild）;

printf（“％d”，root->数据）；

inOrder（root-> rchild）;

}

int delVal（结构biTree ** root，int val）{

如果（root == NULL）返回0;

struct biTree * p = *根，* pre = *根;

struct biTree * q =（struct biTree *）malloc（sizeof（struct biTree））;

同时（1）{

int值=（*根）->数据;

同时（p && p->数据<= val）{

pre = p;

p = p-> rchild;

免费（预）；

}

if（值

否则q-> lchild = p;

while（p && p-> data> val）{

pre = p;

p = p-> lchild;

}

如果（p == NULL）中断;

q = pre;

}

返回1；

}

int main（）{

int i;

同时（1）{

int a [30];

struct biTree * root = NULL;

未签名的int；

=时间（0）;

孙子（）；

for（i = 0; i <10; i ++）{

a [i] = rand（）0 +1;

}

for（i = 0; i <10; i ++）{

printf（“％d”，[i]）；

}

printf（“ \ n”）;

for（i = 0; i <9; i ++）root = createBST（root，a [i]）;

inOrder（根）；

printf（“ \ n”）;

int val;

scanf（“％d”，＆val）; //输入一个值，所有小于该值的节点将被删除

delVal（＆root，val）;

inOrder（根）；

printf（“ \ n \ n”）;

root = NULL;

}

返回0；

}

本文将永久更新链接地址:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-192775-1.html