Java二进制搜索树找到父级

本文介绍了Java二进制搜索树找到父级的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我正在研究一种寻找阳极母体的方法.我从根开始，然后沿着叶子走，只要它们不为空且不是子节点.

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

我的树是

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