2

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

  1. 该节点没有子节点

  2. 该节点有一个孩子

  3. 该节点有 2 个孩子

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

4

5 回答 5

5

这是您在任何有关算法的标准教科书中都可以找到的内容，但假设您对不平衡情况感兴趣（平衡树通常在移除后执行一些称为“旋转”的重新平衡操作）并且您使用“明显”数据结构（一种tree_node结构保存值和两个指向 other 的指针tree_node）：

  1. 无子节点：释放节点持有的内存，并将指向它的父节点的子链接设置为NULL；
  2. 一个子节点：释放节点持有的内存，并将指向它的父节点的子链接设置为其唯一子节点的地址；
  3. 两个孩子：这确实是一个“复杂”的案例。找到左孩子的最右边的节点（或右孩子的最左边的节点），取其值，将其移除（是“case 1”，所以很简单，可以递归完成）并将当前节点的值设置为该节点之一。这是O(tree_height) = O(n)，但它不是问题（至少在理论上），因为这将是查找节点的复杂性。
于 2012-09-03T21:08:35.590 回答
1

你的树有任何额外的属性吗？是AVL吗？

如果没有，有一些非常明显和直接的方法可以做你想做的事（这将取决于你的数据表示，正如 Vitalij 所说）。

例如，如果它是 AVL，还有一些众所周知的方法可以做到这一点（维基百科会告诉你更多关于该主题的信息）

于 2012-09-03T20:48:42.660 回答
1

第一个任务是查找节点是否存在，这将在搜索期间完成，并且您的其余条件是否正确。

  1. 叶节点：将父节点的子节点（右/左）设置为 NULL。

  2. 有一个子节点：只需将要删除的节点的子节点设置为其父节点的子节点。

  3. 有两个孩子：基本上必须通过为要删除的节点找到新的孩子来修剪子树来重新排序整个子树。

于 2012-09-03T20:52:09.593 回答
1

假设您正在处理一般二叉树，请执行以下操作，

  1. 节点没有子节点-即它是叶子：方便地删除它..

  2. 节点有一个子节点 - 将要删除的节点的父节点设为其子节点的父节点，然后删除该节点。即，如果A->Parent = B; C->Parent = A;并且A必须删除，则 1. Make C->Parent = B；2.删除A；

  3. 棘手的一个....是的，将要删除的节点替换为右子树的最左边的子树，或者替换为左子树的最右边的树，都可以......因为可以这样看，

当一个节点被删除时，它必须被一个满足某些属性的节点替换......假设我们的二叉树在中序遍历中表示排序数字（按递增顺序），那么被删除的节点应该被某个节点替换它的任何一个子树。这应该大于整个剩余的左子树，并且小于整个剩余的右子树（剩余意味着在成功调整删除节点后剩余的子树）。只有两个这样的节点存在，右子树的最左边的叶子，或者左边的最右边的节点。

因此，从任一节点替换已删除的节点就足够了……！！

于 2012-09-03T21:24:21.753 回答
1

从二叉搜索树中一次删除一个给定的键。可能的相等键被插入到现有节点的左分支中。请注意，插入策略也会影响删除的执行方式

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)
于 2018-09-26T08:35:43.360 回答