pta二叉搜索树的结构

### 二叉搜索树的数据结构实现与原理 #### 1. 二叉搜索树的定义和性质 二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点具有以下属性： - 节点的左子树只包含键值小于该节点键值的节点。 - 节点的右子树只包含键值大于该节点键值的节点。 - 左子树和右子树也必须分别是二叉搜索树。 这些特性使得二叉搜索树非常适合用于快速查找、插入和删除操作[^2]。 #### 2. 判断是否为二叉搜索树 为了验证给定的二叉树是否为二叉搜索树，可以通过遍历整棵树并检查每一对父子节点的关系来确认。具体方法如下： ```cpp struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } bool helper(TreeNode* node, long minVal, long maxVal) { if (!node) return true; if (node->val <= minVal || node->val >= maxVal) return false; return helper(node->left, minVal, node->val) && helper(node->right, node->val, maxVal); } ``` 这段代码通过递归方式检查每个节点及其子节点是否满足二叉搜索树的要求[^1]。 #### 3. 插入新元素到二叉搜索树 向二叉搜索树中添加新的元素时，总是将其放置在一个合适的位置上，以保持原有的有序性。以下是C++中的一个简单的插入算法示例： ```cpp TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) return new TreeNode(val); // 如果当前为空，则创建一个新的结点作为根 if (val < root->val) root->left = insertIntoBST(root->left, val); // 小于则往左边走 else root->right = insertIntoBST(root->right, val); // 大于等于就往右边走 return root; // 返回更新后的树 } ``` 此过程会沿着路径向下直到找到适当位置为止，并在那里建立连接[^3]。 #### 4. 删除指定元素 当需要移除某个特定数值所在的节点时，情况稍微复杂一些。通常有三种情形要考虑：被删节点无子女；只有一个孩子；有两个孩子。这里提供了一种通用的方法处理这几种状况之一——即替换待删除节点与其最接近后继者之间的关系。 ```cpp TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; if (key < root->val) root->left = deleteNode(root->left, key); else if (key > root->val) root->right = deleteNode(root->right, key); else { // 找到了目标节点 if (!root->left) return root->right; if (!root->right) return root->left; auto temp = findMin(root->right); root->val = temp->val; root->right = deleteNode(root->right, temp->val); } return root; } // 辅助函数：寻找最小值节点 TreeNode* findMin(TreeNode* node){ while (node && node->left != NULL) node=node->left; return node; } ``` 上述逻辑确保了即使是在存在两个孩子的场景下也能正确维护整个结构不变形。