2

在尝试从二叉树中删除该节点有 2 个子节点的节点时，我很难思考如何修复适当的指针。

我理解基本概念，我基本上只是在修复指针时遇到了麻烦......

所以，基本上，我的删除功能已经基本完成，每个案例都已经在工作（就我的广泛测试而言，一切正常），我只缺少有 2 个孩子的案例节点。假设我们在else if处理该案例的内部：

我将在那里有 2 个指针，currPtr它保存要删除的节点，prevPtr它保存父节点。我还有一个名为的变量fromLeft，它定义了currPtr父级是来自左指针还是右指针prevPtr。然后，我调用了另一个名为的函数extractMin(Tree *t)，该函数提取了树中的最小值。如果我用currPtr->right作为参数调用此函数，将从树中提取 的后继者currPtr（该函数将从树中删除它，修复指针并返回节点指针）。后继指针将保存在tempPtr.

这是我的树的结构： 

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

以及提取功能的代码：

Tree *extractMin(Tree *tree) {
    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if(prevPtr) prevPtr->left = currPtr->right;

    // inorder successor
    return currPtr;
}

上面的代码缺少树只有一个节点的情况，即根节点，它不能正常工作，也不会检查树是否有任何节点，但是，当树有几个节点时它可以工作节点。

那么，如何修复else if节点删除的必要指针？另外，请记住，树节点上的leftandright指针将始终指向某处或 be NULL。

顺便说一句，我想做这个迭代。

4

3 回答 3

3

更新：因此，您希望通过将节点替换为其直接顺序后继或前任来保持节点的顺序。

假设下面的树是有序的。节点的顺序是：

H < D < I < B < J < E < K < A < F < M < C < N < G < O

您想删除一个有两个子节点的节点 (A)。您可以提取节点的有序前驱 (K) 或后继 (F) 子节点来代替原始节点。让我们选择继任者。你是这样找到它的：你遍历 C 的左孩子，直到找到一个没有左孩子的；这是 A 的直接中序继承者。

       A
   B       C
 D   E   F   G
H I J K   M N O

所以F被拉上去，A的左子树没有被触及。但是，现在 M 也应该被拉起来，成为 C 的左孩子（这是在你的 中完成的extractMin()）。

在所有重新排列之后，你得到

       F
   B       C
 D   E   M   G
H I J K     N O

在代码中，这是我的解决方案。我添加了一个 NULL 检查来extractMin()简化调用者代码，所以我不需要else if.

更新 extractMin()以涵盖tree没有孩子的情况。

Tree *extractMin(Tree *parent, Tree *tree) {
    if (!tree) return NULL;

    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if (prevPtr) {
        prevPtr->left = currPtr->right;
    } else if (parent) {
        parent->right = currPtr->right;
    }

    // inorder successor
    return currPtr;
}

// prevPtr is the parent, currPtr is the node to be deleted
Tree *successor = extractMin(currPtr, currPtr->right);
successor->left = currPtr->left;
successor->right = currPtr->right;
if (fromLeft) {
    prevPtr->left = successor;
} else {
    prevPtr->right = successor;
}
// Now currPtr can be destroyed

请注意，此代码未经测试，所以我不保证任何事情:-)

请注意，像这样重复删除可能会使树不平衡（即，某些路径会比其他路径长得多）。二叉排序树以这种方式进行删除，但也使用重新平衡来使树接近理想状态（每个叶子都处于同一级别，就像我上面的第一个示例一样）。

于 2010-02-18T20:34:58.893 回答
1

教科书的答案是用它最左边的后代替换有问题的节点。

                6
         3             8
     2      4      7      9
   1          5             10

如果我们想去掉3，我们可以用4代替它，然后将5拉到4所在的孔中。我们总是可以做到这一点，它会保留中序遍历。

好的。查看您的代码，这就是您想要的：

//in your function
    else if (/*has 2 nodes*/) {
        currPtr->item = extractMin(currPtr->right, &(currPtr->right))->item;
    }

Tree *extractMin(Tree *tree, Tree ** back) {
    Tree *currPtr = tree;

    while(currPtr->left) {
        back    = &(currPtr->left);
        currPtr = currPtr->left;
    }

    *back = currPtr->right;

    // inorder successor
    return currPtr;
}

** 参数允许我们处理使用已删除节点的直接右孩子的情况：

     3   <--deleting this node
   /   \   <--back points to this edge.
  2     4   <--extractMin is called on this node and returns this node,
         \
          5   <-- (*back) now points to this node.

在 2 种情况下考虑新的 ExtractMin。

  1. 在第一种情况下，我们至少循环一次。如果我们在代码中留下了prevPtr，我们会在循环之后看到，back == &(prevPtr->left); （例如修改*back 将修改prevPtr->left）。因此，它与您上面的代码相同。
  2. 在第二种情况下，我们不通过循环。在这种情况下，back指向我们无法以任何其他方式获得的链接（除非我们修改 extractMin 以开始更高级别）。

另一种思考方式是 (*back) 总是指向 currPtr（花点时间检查一下），所以如果我们要删除 currPtr，back 指向我们需要修改的边。

于 2010-02-18T21:10:45.197 回答
0

如果您对此很认真，请查看 AVL 树：

http://en.wikipedia.org/wiki/AVL_tree

它们实施起来可能很棘手，但由于您在插入和删除时执行的轮换，它们会保持平衡。

于 2010-02-19T02:34:28.477 回答