java - 堆的搜索函数

Question

我创建了一个通用的二叉堆 (MaxHeap)，在其中我必须根据节点中存在的值搜索特定节点。我已经使用 Pre-OrderTraversal 来实现搜索函数，并且它应该给出顺序为 n 的运行时间，其中 n 是堆中的节点数。我的代码似乎不起作用。它永远不会进入 preOrderT 函数中存在的第二个“else if”。您能否建议可以对其进行哪些更改？

我的节点类已定义为包含一个整数键(根据其排列堆)、一个通用对象值以及对父级、leftChild 和 rightChild 的引用。

public Node<E> search(E p){
    Node<E> N;

    N= preOrderT(root, p);
    return N;
}

public Node<E> preOrderT(Node<E> N, E p){
    Node<E> M=null;

    if (N.value==p) M=N;
    else if (M==null && N.leftChild!=null){ M=preOrderT(N.leftChild, p);}
    else if (M==null && N.rightChild!=null){ M=preOrderT(N.rightChild, p);}
    return M;
}

Answer 1

问题是，如果存在 leftChild，那么您永远不会给它机会检查 rightChild。相反，在检查完 leftChild 后，如果尚未找到该值，请检查 rightChild。