数据结构课程设计二叉排序树

### 数据结构课程设计：二叉排序树

#### 1. 实验目的
本实验旨在深入了解二叉排序树（BST, Binary Search Tree）的特点及其基本操作，包括插入、删除和查找节点。通过对这些操作的学习和实践，能够掌握如何利用二叉排序树有效地管理和查询数据。

#### 2. 实验环境配置
为了顺利完成本次实验，需提前准备好开发工具与测试平台。推荐使用Python作为编程语言，并确保环境中已安装必要的库文件[^1]。

#### 3. 二叉排序树简介
二叉排序树是一种特殊的二叉树形式，其左子树上的所有键值均小于根节点的键值；右子树上的所有键值则大于根节点的键值。这种特性使得二叉排序树非常适合用于快速检索特定数值的位置[^2]。

#### 4. 主要功能模块说明

##### (a) 创建二叉排序树
创建一个新的空二叉排序树实例，初始化为空状态。

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key


def insert(root, node):
    if root is None:
        return node
    
    if node.val < root.val:
        root.left = insert(root.left, node)
    else:
        root.right = insert(root.right, node)

    return root

##### (b) 查找指定元素
给定目标值key，在二叉排序树中寻找是否存在该值对应的节点。

def search(root, key):  
    if root is None or root.val == key: 
        return root  

    if root.val < key: 
        return search(root.right,key)  
    
    return search(root.left,key)   

##### (c) 删除某个节点
当需要移除某节点时，考虑到不同情况下的处理方式——如果待删节点无子女，则直接将其置为None；若有单侧孩子，则让孩子的父指针指向孙子；若有两个孩子，则找到后继者替代被删位置并调整连接关系。

def minValueNode(node):
    current = node
  
    while(current.left is not None): 
        current = current.left  
  
    return current   

def deleteNode(root, key): 
  
    if root is None: 
        return root  
  
    if key < root.val: 
        root.left = deleteNode(root.left, key) 
  
    elif(key > root.val): 
        root.right = deleteNode(root.right, key) 
  
    else: 

        if root.left is None : 
            temp = root.right  
            root = None 
            return temp  
              
        elif root.right is None : 
            temp = root.left  
            root = None
            return temp 
  
        temp = minValueNode(root.right) 
  
        root.val = temp.val 
  
        root.right = deleteNode(root.right , temp.val) 
    
    return root 

#### 5. 结果分析与讨论
通过上述代码实现了一个完整的二叉排序树模型，支持常见的增删查改四种基本操作。实际应用过程中可根据具体需求进一步优化性能或扩展其他高级特性，比如自平衡机制等。