用于删除二进制搜索树中的节点的伪代码和条件

Question

我正在尝试编写一个函数来从二叉树中删除一个节点.我还没有对该函数进行编码,我正在尝试考虑删除节点时应考虑的不同条件.我猜可能的条件是:

1. 该节点没有子节点

2. 该节点有一个孩子

3. 该节点有2个孩子

在每种情况下,执行删除功能的算法是什么？

Answer 1

这是你在任何有关算法的标准教科书中都能找到的东西,但是我们假设你对不平衡的情况感兴趣(平衡树通常在删除后执行一些称为"旋转"的重新平衡操作)并使用"明显的"数据结构(tree_node结构)保存值和两个指向其他指针tree_node):

1. 没有子节点:释放节点保留的内存并设置指向它的父节点子链接NULL;
2. 一个子节点:释放节点保留的内存,并将指向它的父节点子链接设置为其唯一子节点的地址;
3. 两个孩子:这确实是"复杂"的案例.找到左子节点的最右边节点(或右子节点的最左边节点),取其值,删除它(它是"case 1",因此很容易并且可以递归完成)并将当前节点的值设置为那个节点之一.这是O(tree_height) = O(n),但这不是问题(至少在理论上),因为这将无法找到节点的复杂性.