二叉树排序树删除节点例子

二叉树是一种非常常用的数据结构，二叉排序树是在二叉树基础上进行的排序扩展，能够提高查找速度。而在实际使用过程中，我们有时候需要删除节点，本文将从多个角度分析二叉排序树删除节点例子。

一、概念解释

1. 二叉树：每个节点至多有两个子节点的树结构

2. 二叉排序树：在二叉树的基础上，对其进行排序扩展，每个节点的左子树上的节点都小于它，右子树节点都大于它

3. 删除节点：将指定节点从树中移除

4. 中序遍历：按照左子树深度优先，然后遍历根节点，最后遍历右子树的顺序输出二叉树所有节点的值

二、例子说明

以以下二叉排序树为例：

7

/ \

6 8

/ \ / \

4 5 2 9

若需删除节点8，删除后二叉排序树变为：

7

/ \

6 9

/ \ /

4 5 2

三、方法分析

二叉排序树的节点删除方法分为三种情况：

1. 叶子节点的删除：直接将父节点的对应子节点置为空即可。

以删除节点2为例，删除后二叉排序树变为：

7

/ \

6 8

/ \ / \

4 5 - 9

2. 只有一个子节点的删除：将该节点的子节点取代它的位置，然后删除该节点

以删除节点5为例，删除后二叉排序树变为：

7

/ \

6 8

/ / \

4 2 9

3. 有两个子节点的删除：找到该节点的右子树中的最小节点，将其值替换到被删除节点的位置上，然后删除那个最小节点。

以删除节点7为例，删除后二叉排序树变为：

8

/ \

6 9

/ \ /

4 5 2

四、代码展示

C++代码如下：

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

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

if (!root) return NULL;

if (root->val == key) {

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

else {

TreeNode* cur = root->right;

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

cur->left = root->left;

return root->right;

}

}

if (root->val > key) root->left = deleteNode(root->left, key);

else root->right = deleteNode(root->right, key);

return root;

}

五、总结

二叉排序树的节点删除操作虽然看似简单，但是要考虑到多种情况，如有两个子节点的删除需要找到替换节点、只有一个子节点的删除需要替换。同时，删除节点后还需要保证被删除节点的子节点被正确地连接上去。针对不同情况，我们可以采用不同的写法，如借助while循环寻找目标节点右子树的最小节点。最后，掌握二叉排序树的节点删除操作对于算法的学习和使用都是非常重要的。