二叉搜索树（BST）的基本概念

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树结构，其中每个节点都有一个键值，并满足以下性质：

• 左子树性质：对于任一节点，其左子树中的所有节点的键值均小于该节点的键值。
• 右子树性质：对于任一节点，其右子树中的所有节点的键值均大于该节点的键值。
• 递归性质：每个节点的左右子树也分别为二叉搜索树。

二叉搜索树的节点结构

在C++中，我们可以使用一个类来表示二叉搜索树的节点。一个典型的节点包括下面几个组成部分：

struct TreeNode {  
    int key; // 节点的键值  
    TreeNode* left; // 指向左子树的指针  
    TreeNode* right; // 指向右子树的指针  
    // 构造函数  
    TreeNode(int val) : key(val), left(nullptr), right(nullptr) {}  
};  

二叉搜索树的基本操作

1. 插入节点：
   插入元素首先需要从根节点开始，顺序比较键值，依次进入左子树或右子树，直至找到插入位置。

   TreeNode* insert(TreeNode* node, int key) {  
      if (node == nullptr) {  
          return new TreeNode(key); // 找到插入位置  
      }  
      if (key < node->key) {  
          node->left = insert(node->left, key);  
      } else if (key > node->key) {  
          node->right = insert(node->right, key);  
      }  
      return node; // 返回未改变的节点指针  
   }  

2. 查找节点：
   类似于插入操作，从根节点出发，比较键值，递归搜索左右子树。

   TreeNode* search(TreeNode* node, int key) {  
      if (node == nullptr || node->key == key) {  
          return node;  
      }  
      if (key < node->key) {  
          return search(node->left, key);  
      } else {  
          return search(node->right, key);  
      }  
   }  

二叉搜索树的特性

• 时间复杂度：对于高度为h的树，插入、删除、查找操作的平均时间复杂度为O(h)。在最坏情况下（如退化为链表时，高度为n），时间复杂度为O(n)。
• 平衡性：为了避免极端情况退化为链表，通常使用自平衡的树结构（如AVL树、红黑树）来维持效率。

小结

这是对二叉搜索树基本知识的初步介绍，包括节点的结构定义、插入和查找操作。二叉搜索树因其高效的搜索、插入和删除操作，在各类计算机应用中被广泛使用。后续内容将会介绍二叉搜索树的删除操作及其优化策略。