0

我正在研究一种找到阳极父级的方法。我从根开始，然后沿着叶子向下走，只要它们不为空而不是子节点。

下面是我的代码，它有点乱，因为我试图测试它看看出了什么问题。

我拥有的树是

        10
      /    \
     2     20
      \   / \
       3 18 22
            /
           21

传入的 x 是 20，所以 10 是父级，但是当我运行它时，22 会作为父级出现。while 循环似乎不起作用，是我写的方式吗？

public Node<E> findParent(E x)
{
Node<E> node = root;

System.out.println("node is " + node.getData() + " before the search");
System.out.println("The value of x is " + x);
System.out.println("The value of node.getRight is " + node.getRight().getData());
boolean test = !node.getRight().getData().equals(x);
System.out.println("does nodes data equal x " + test);
while(((node!=null) && (node.getLeft()!=null) && (!node.getLeft().getData().equals(x))) || 
 ((node != null) && (node.getRight()!=null) && (!node.getRight().getData().equals(x))))
{ System.out.println("why didnt it stop");
    if(x.compareTo(node.getData()) < 0)
    {
        node = node.getLeft();
    }
    else
    {
        node = node.getRight();
    }
}
 System.out.println("node is " + node.getData() + " after the search");
return node;
}
4

3 回答 3

6

我会做不同的事情：在传递当前节点和当前父节点的辅助方法中进行递归。它使一切变得更加简单：

public Node<E> findParent(E x) {
    return findParent(x, root, null);
}

public Node<E> findParent(E x, Node<E> node, Node<E> parent)
{
    if (node == null) {
        return null;
    } else if (!node.getData().equals(x)) {
        parent = findParent(x, node.getLeft(), node);
        if (parent == null) {
            parent = findParent(x, node.getRight(), node);
        }
    }
    return parent;
}
于 2013-03-03T00:10:21.327 回答
0 
private static void myparent(int data, Node R) 
{
    if( (R.left!=null && R.left.data == data) || (R.right!=null) &&(R.right.data == data) )
    {
        pRoot = R;
        return;
    }
    if (R.data <= data)
        myparent(data, R.right);
    else
        myparent(data, R.left);
}

其中“Data”是我们需要搜索其父节点的节点的值，R 是 BST 的根节点。pRoot 是我在 BST 的其他操作中使用的全局数据结构。

于 2015-08-05T23:10:27.843 回答
-1

这只是伪代码。当您在一个节点时x，检查左右节点中的键（要找到其父节点的子节点）。如果它们匹配，那么您已经在父级。如果不是，则可以安全地朝元素的方向移动并再次执行。

请注意，我们在继续之前检查下一个级别。

while(node!=null){

  if(node.left==key || node.right==key) return node;

  if(key<node.data) node=node.left;

  else node=node.right;

  return null;
}
于 2016-04-06T19:49:37.967 回答