1

因为代码太长，所以链接在这里-> http://pastebin.com/jXgbE6bB 因为我不擅长递归，所以我找不到适合这个问题的递归函数。
（PSI 是这个论坛的新手，我知道我会有很多讨厌的评论，比如为什么不去找关于递归和其他事情的教程，但相信我，我已经做了所有事情，但我就是无法理解递归）
我的问题是二叉搜索树中给定元素的有序后继的递归函数是什么？
我做到了这一点，但它只是返回它应该打印的节点的父节点：

public E getSuccessor(BNode<E> t, E x) {
    if(t.left!=null && x.equals(t.info)){
        return t.left.info;
    }
    else if(x.compareTo(t.info)<0){
        return (getSuccessor(t.left, x));
    }
    else {
        return (getSuccessor(t.right, x));
    }
}

public E getSuccessor(E x) {
    return getSuccessor(root, x);
}
4

1 回答 1

2

给定节点的中序后继是该节点右子树中的最低节点。否则，将在树的简单顺序遍历中打印下一个节点。

  1. 如果节点有一个右孩子，这个解决方案被简化为在右子树中找到最小的节点。
  2. 如果节点没有右子节点，也没有父指针，我们需要从树的根开始，按照我们的方式来识别这个后继节点。

这是解决此问题的递归方法。在调用该方法时，将 root 作为树的根，需要其后继节点作为 t 和 null 作为后继节点，因为该方法将计算它。类似于以下内容 -

BinaryTreeNode 后继=tree.inorderSuccessor(root,node,null);

public BinaryTreeNode<Type> inorderSuccessor(BinaryTreeNode<Type> root,BinaryTreeNode<Type> t,BinaryTreeNode<Type> successor)
{
    if(root==null)
        return null;
    if(root.element==t.element)
    {
        if(root.right!=null)
            return findMin(root.right);
        else
            return successor;
    }
    int cmp=t.element.compareTo(root.element);

    if(cmp < 0)
        return inorderSuccessor(root.left,t,root);
    else
        return inorderSuccessor(root.right,t,successor);
}

public BinaryTreeNode<Type> findMin(BinaryTreeNode<Type> t)
{
    if(t==null)
        return t;
    while(t.left!=null)
        t=t.left;
    return t;
}
于 2014-12-14T13:26:07.043 回答