删除二叉排序树的代码

二叉排序树是一种特殊的二叉树，它保证了左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点。在进行删除操作时，需要注意叶子节点和只有一个孩子的节点的情况。本文将从多个角度分析删除二叉排序树的代码，并给出全文摘要和3个关键词。

1. 递归删除

递归删除是一种常见的删除二叉排序树节点的方法。其主要思想是从根节点开始比较，找到要删除的节点后，分三种情况讨论：

（1）要删除的节点为叶子节点：直接删除该节点即可；

（2）要删除的节点只有一个孩子：将该节点的父节点指向该节点的孩子节点即可；

（3）要删除的节点有两个孩子：找到该节点的右子树中最小的节点（即比要删除的节点大的最小值），用该节点替换要删除的节点，在删除该最小节点时则回到（1）或（2）的情况。

递归删除的代码实现如下：

```c++

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;

else if (!root->right) return root->left;

TreeNode* minNode = findMin(root->right);

root->val = minNode->val;

root->right = deleteNode(root->right, root->val);

}

return root;

}

TreeNode* findMin(TreeNode* node) {

while (node->left) node = node->left;

return node;

}

```

2. 非递归删除

非递归删除是另一种实现删除二叉排序树节点的方法。其主要思想是使用一个指针p指向要删除的节点，并记录该节点的父节点parent。分三种情况讨论：

（1）要删除的节点为叶子节点：直接删除该节点即可；

（2）要删除的节点只有一个孩子：将该节点的父节点指向该节点的孩子节点即可；

（3）要删除的节点有两个孩子：找到该节点的右子树中最小的节点（即比要删除的节点大的最小值），用该节点替换要删除的节点，在删除该最小节点时则回到（1）或（2）的情况。

非递归删除的代码实现如下：

```c++

TreeNode* deleteNode(TreeNode* root, int key) {

if (!root) return nullptr;

TreeNode *p = root, *parent = nullptr;

while (p && p->val != key) {

parent = p;

if (key < p->val) p = p->left;

else p = p->right;

}

if (!p) return root;

if (p->left && p->right) {

TreeNode* minNode = p->right;

while (minNode->left) {

parent = minNode;

minNode = minNode->left;

}

p->val = minNode->val;

p = minNode;

}

TreeNode* child = nullptr;

if (p->left) child = p->left;

else if (p->right) child = p->right;

if (!parent) root = child;

else if (parent->left == p) parent->left = child;

else parent->right = child;

return root;

}

```

3. 删除的复杂度分析

删除二叉排序树节点的操作最坏情况下需要遍历整棵树，时间复杂度为O(n)，其中n为二叉树的节点数。平均情况下，二叉排序树高度为O(logn)，因此删除节点的操作平均时间复杂度为O(logn)。

4.