0

我试图在 BST 中找到一个节点的有序后继者。下面是我的示例代码。

public TreeNode getInorderSuccesor(TreeNode t)
{

    if(t == null)
    {
        return null;
    }

    if(t.getRight()!=null)
    {
        t = t.getRight();
        while(t.getLeft()!=null)
        {
            t = t.getLeft();
        }
        return t;
    }
    else
    {
        TreeNode parent = t.getParent();

        while(parent!=null && parent.getLeft() != t)
        {
            t = parent;
            parent = t.getParent();
        }
        return parent;
    }
}

请让我知道它是否会失败。如果有些人可以共享算法/代码/ sudocode 以找到没有父节点的中序继任者，还有一件事。谢谢！！！

4

2 回答 2

0

如果树中的节点具有唯一值，那么这很简单。你只需要找到：

  • 小于或等于需要确定后继节点值的最大节点数
  • 最小编号的节点严格大于需要确定后继节点的值。

后一个节点将是答案。第一个节点可用于检查输入节点是否为树中的有效节点。

伪代码：

function inOrderSuccessor(val, tree):
    (left, right) = findRange(val, tree.rootnode, null, null)

    if (left.val != val):
        throw Error("No node with specified value")

    return right


function findRange(val, currnode, left, right):
    if (currnode == null):
        return (left, right)

    if (currnode.val <= val):
        return findRange(val, currNode.right, currnode, right)
    else:
        return findRange(val, currNode.right, left, currnode)

如果树中的节点可能具有重复值，则有序后继节点的定义不是很好。有必要知道何时给定一个节点，如何区分具有相同值的不同节点。您是否真正引用了树中的节点？

在棘手的情况下，您只是简单地获得一个节点的引用，并且树中还有其他具有相同值的节点，那么有两种情况：

  • 情况1：节点有右子树，那么你只需要找到右子树中最小的元素。
  • 情况2：节点没有右子树。您需要检查具有相同值的所有节点的引用相等性。当你在树中找到节点时，从节点向上遍历回到根（你在堆栈中有这个），并找到第一个左转的节点。
于 2013-02-28T14:38:11.343 回答
0

这是后继功能的基本逻辑；前任功能类似，但相反。递归函数沿着树向下搜索请求的键，如果每次跟随左子树，则跟踪当前树作为可能的后继树。如果它找到键，它的后继是右子树的最小元素，通过追逐左子树直到到达一个空节点找到。如果搜索到达空节点并因此无法找到键，则树中的下一个最大键是后继，在每次递归调用时保存的可能后继中找到。我最近在我的博客上实现了这个算法。

于 2013-02-28T13:53:08.727 回答