C 语言中移除 BST 范围外的键

本文探讨了在 BST 中删除超出指定范围的键的问题，并提供了一个 C 语言的实现。熟练掌握根据特定标准（如范围限制）操作 BST 对于各种应用至关重要，包括算法设计和数据库管理。通过使用本文介绍的方法，开发人员可以有效、高效地处理这些场景，同时保持数据结构的完整性。

引言

二叉搜索树（BST）是计算机科学中的基本数据结构，广泛用于搜索、插入和删除等操作。我们经常需要操作 BST 来删除超出预定范围的键。数据过滤、搜索性能优化以及在规定边界内保持数据完整性等应用都依赖于此操作。本文将探讨删除 BST 中超出给定范围的键的概念、其重要性以及一种 C 语言的实现方法。

BST 是一种二叉树，其中每个节点最多有两个子节点：左子节点和右子节点。BST 的主要特性是：对于给定的每个节点：

• 左子树中的所有键都小于该节点键。
• 右子树中的所有键都大于该节点键。
• 这种内置特性使得插入、删除和搜索操作更加高效。

问题陈述

给定一个二叉搜索树和一个范围 [min, max]，目标是删除二叉搜索树中不在此范围内的任何键。

方法

为了解决这个问题，我们可以通过深度优先（中序遍历）遍历 BST 来递归地将每个节点的键与指定范围进行比较。如果键超出范围，我们将删除该节点并修改树。

以下是算法的摘要：

• 迭代地顺序遍历 BST。
• 验证每个节点的键是否在指定范围内。
• 如果键小于所需最小值，则删除该节点及其左子树。
• 如果键大于最大值，则删除该节点及其右子树。
• 持续遍历，直到检查完所有节点。

代码

输出

代码解释

节点结构： BST 中的节点由代码定义的结构 `node` 表示。除了整数键之外，它还包含指向每个节点左右子节点的指针。

newNode 函数： `newNode` 函数将新创建节点的左右指针初始化为 NULL，并使用提供的键值对其进行初始化。它返回指向新创建节点的指针。

removeOutsideRange 函数： 此函数接受两个整数作为范围的最小值和最大值，还接受 BST 的根。它通过递归遍历树来删除键不在指定范围内的节点。如果键小于最小值，则会销毁该节点及其以正确子节点为根的子树。类似地，如果节点的键大于最大值，则会删除该节点及其以左子节点为根的子树。

inorder 函数： 它通过对 BST 进行中序遍历来对节点键进行排序。

main 函数： `main` 函数创建一个示例 BST。然后，在按顺序访问 BST 时，通过调用 `removeOutsideRange` 函数删除超出指定范围的节点。为了验证删除过程，最后再次遍历 BST 并打印其内容。