Java二进制搜索树找到父级 [英] java binary search tree find parent

问题描述

我正在研究一种寻找阳极母体的方法.我从根开始，然后沿着叶子走，只要它们不为空且不是子节点.

下面是我的代码，它有点混乱，因为我正在尝试对其进行测试以查看发生了什么问题.

我的树是

        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;
}

解决方案

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

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;
}

im working on a method to find the parent of anode. I start at the root and then go down the leaves as long as they are not null and not the node of the child.

below is my code, its a little messy because im trying to test it to see whats going wrong.

The tree that i have is

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

The x that is being passed in is 20 so 10 is the parent but when i run it 22 comes out as the parent. the while loop seems to not be working, is it the way ive written it?

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;
}

解决方案

I would do it differently: do the recursion in an auxiliary method that is passed the current node and the current parent node. It makes everything much simpler:

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;
}

这篇关于Java二进制搜索树找到父级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！