java - Java二分探索木は親を見つけます

Question

アノードの親を見つける方法に取り組んでいます。私は根から始めて、葉がヌルでなく、子のノードでない限り、葉を下っていきます。

以下は私のコードです。何がうまくいかないかをテストしようとしているので、少し面倒です。

私が持っている木は

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

渡されるxは20なので、10が親ですが、実行すると22が親として出てきます。whileループが機能していないようですが、それはiveが書いた方法ですか？

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

Answer 1

別の方法で行います。現在のノードと現在の親ノードに渡される補助メソッドで再帰を実行します。これにより、すべてがはるかに簡単になります。

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

Answer 2

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

ここで、「データ」は検索する必要がある親ノードの値であり、R は BST のルート ノードです。pRoot は、BST の他の操作で使用したグローバル データ構造です。