在没有父母信息的情况下继承BST

问题描述：

我试图找到BST中的一个节点的继任者。以下是我的示例代码。在没有父母信息的情况下继承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找到没有父节点的中继器。谢谢！！！

您可以简单地搜索树中大于当前节点的最小节点。如果您有具有相同值的节点，事情会稍微复杂一些。 – nhahtdh 2013-02-28 13:34:38

答

这是后继函数的基本逻辑;前任职能类似，但相反。递归函数在搜索所请求密钥的树下降，如果跟随左子树，则每次跟踪当前树作为可能的后继者。如果它找到了密钥，它的后继是右子树的最小元素，通过追踪左子树找到它直到到达空节点。如果搜索到达空节点并因此未能找到密钥，树中的下一个最大密钥就是后继，在每次递归调用时保存的可能后继中找到后继。我最近在my blog上实现了这个算法。

你甚至不需要追逐。在遍历树时，只需跟踪最小的较大元素即可找到比当前元素大的元素。 – nhahtdh 2013-02-28 14:00:28

答

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

与数量最多的节点是小于或等于其继任者需要确定
编号最小的节点是严格量比较大的节点的值需要确定后继节点的值。

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

伪代码：

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：节点没有右子树。您需要检查具有相同值的所有节点的引用相等性。当您在树中找到节点时，从节点向上遍历回到根（您在堆栈中有这个节点），然后找到第一个左转的节点。

在没有父母信息的情况下继承BST

相关推荐