伪代码，并在二叉搜索树删除节点的条件(Pseudo Code and conditions for

我试图写一个函数从二叉树删除一个节点。我还没有编码功能着呢，我试着换位思考一下不同的条件，我应该考虑删除节点。我猜测可能的条件是：

该节点有没有孩子
该节点有一个孩子
该节点有2个孩子

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

Answer 1:

这是你会发现在关于算法的任何标准教科书，但是让我们假设你有兴趣在不平衡的情况下（平衡树通常进行一些再平衡操作称为“旋转”去除后），您使用“明显的”数据结构（一tree_node结构中保存的值和两个指向其他tree_node ）：

没有孩子 ：由节点释放内存持有，并设置指出它作为父母的子链接NULL ;
一个孩子 ：由节点释放内存持有，并设置指出它作为唯一的孩子的地址父项的子链接;
两个孩子 ：这确实是一个“复杂”的情况。找到左子中最右边的节点（或右子的最左边的节点），取它的价值，将其删除（这是“情况1”，所以很容易，并且可以完成递归），并设置当前节点的值该节点中的所述一个。这是O(tree_height) = O(n) ，但它不是一个问题（至少在理论上），因为这将是neverthless的找到一个节点的复杂性。

Answer 2:

请问您的树有什么附加属性？它是一个AVL？

如果不是，有一些非常明显和直接的方式做你想要什么（这将取决于你的数据表示，随着Vitalij说）。

而如果它是例如AVL，也有做一些众所周知的方法（维基百科将更多有关该主题的告诉你）

Answer 3:

第一个任务是找到节点是否存在，这将搜索和休息期间你的条件是正确的完成。

叶节点：设置父的孩子（右/左）为NULL。
有一个孩子：只需设定节点的孩子被删除其父母的孩子。
有两个孩子：基本上要重新排序的整个子树在这里通过寻找新的孩子要删除的节点修剪子树。

Answer 4:

假设你正在处理的一般二叉树，做到以下几点，

节点没有儿童安全即它是叶：方便地将其删除..
节点有一个孩子 - 使节点的父被删除其孩子的父母，然后删除该节点。即，如果A->Parent = B; C->Parent = A; A->Parent = B; C->Parent = A; 和A必须被删除，则1.使C->Parent = B ; 2.删除A ;
棘手的是....，替换节点必须由右子树工作的最左子删除或左子树的最右边的树，要么会做...因为它可以看到这个样子，

当一个节点被删除，它必须通过满足一些性能上的节点进行更换......可以说，如果我们的二叉树表示排序号（升序）中序遍历，然后删除节点都应由一些节点替换无论是它的子树。这应该是值比剩余的左子树总体上比剩余的右子树整个更大和更小的（剩余装置调整被删除的节点成功后剩余的子树）。只有两个这样的节点存在，则右子树，或左边的一个的最右边的节点的最左边的叶。

因此，从任何一个替换删除节点就足够了...！

Answer 5:

删除给出一个键从二叉搜索树的时间。可能等于键被插入到现有节点的左侧分支。请注意，插入策略也将影响进行了删除

BinarySearchTree - 删除

Node Delete(Node root, Key k)
1  if (root == null) // failed search
2    return null;
3  if (k == root.key) // successful search
4    return DeleteThis(root);
5  if (k < root.key) // k in the left branch
6    root.left = Delete(root.left, k);
7  else // k > root.key, i.e., k in the right branch
8    root.right = Delete(root.right, k);
9  return root;

Node DeleteThis(Node root)
1  if root has two children
2    p = Largest(root.left); // replace root with its immediate predecessor p
3    root.key = p.key;
4    root.left = Delete(root.left, p)
5    return root;
6  if root has only left child
7    return root.left
8  if root has only right child
9    return root.right
10  else root has no children
11   return null

Node Largest(Node root)
1  if root has no right child
2    return root
3  return Largest(root.right)

文章来源: Pseudo Code and conditions for deleting a Node in Binary Search Tree