1

我正在实现一个在三叉树中插入和删除节点的 Java 程序。

我能够毫无问题地实现插入，但在实现删除操作时遇到了一些问题。

所以，我的问题是：

如果它有一个或多个子节点，如何从三叉树中删除一个节点？

如果您可以共享任何逻辑或伪代码来实现“删除”功能，那就太好了。

4

1 回答 1

1

我找到了解决方案。

假设n是我们要删除的节点，l是它的左孩子，r是它的右孩子，m是它的中间孩子。

  • 如果n是根节点，则 make n null。

  • 如果n不是根节点，则检查是否不是。如果是这样，只需在 上递归调用当前过程，因为值匹配：我们将删除最后一个匹配节点！mnullmmn

  • 如果m是null，那么我们有以下可能的情况：

    • 如果两者l和r都是null，则使父节点中的l和r值成为。mnnull

    • 如果只有一个节点，比如x，（l或者r）不是 null，则将x非空值替换为n的值，然后删除x。

    • 如果两者l 都不 r是， null则在 的左子树中找到最大值z的节点，并将的值替换为的节点，然后删除。nznz

于 2014-03-13T20:49:44.643 回答