如何返回BST中具有特定值的节点？

Question

我必须制作一个所谓的“命中平衡树”。不同之处在于，您可以看到，我的节点类有一个名为numberOfHits的实例变量，您可以随时调用包含方法或findNode方法的增量。这个练习的要点是让顶部的命中数最高的节点，所以树基本上重建自己（或旋转）。根具有最高的命中数。

我有一个关于我必须做出的方法的问题，它返回具有最高命中数的节点。我稍后需要它来让树自动旋转（我猜，至少这是该计划）。这是我的节点类。 （当然所有的干将）

public class HBTNode<T> { 


private HBTNode<T> left; 
private HBTNode<T> right; 
private T element; 
private int numberOfHits; 


public HBTNode(T element){ 
    this.left = null; 
    this.right = null; 
    this.element = element; 
    this.numberOfHits = 0; 
} 

我到目前为止是这样的：

public int findMaxCount(HBTNode<T> node) { 

    int max = node.getNumberOfHits(); 
    if (node.getLeft() != null) { 
     max = Math.max(max, findMaxCount(node.getLeft())); 
    } 
    if (node.getRight() != null) { 
     max = Math.max(max, findMaxCount(node.getRight())); 
    } 
    return max; 
} 

这工作得很好，但它返回一个integer.I需要返回的节点本身。因为我必须递归地做这件事，所以我决定找到最大的命中数，然后在另一个返回节点的方法中使用这个方法，就像这样（它可能真的效率很低，所以如果你有改进的提示，我正在听） ：

public int findMaxCount() { 
    return findMaxCount(root); 
} 


public HBTNode<T> findMaxCountNode(HBTNode<T> node) { 

    if (node.getNumberOfHits() == this.findMaxCount()) { 
     return node; 
    } 

    if (node.getLeft() != null) { 
     return findMaxCountNode(node.getLeft()); 
    } 
    if (node.getRight() != null) { 
     return findMaxCountNode(node.getRight()); 
    } 

    return null; 
} 

我把这样的方法：

public HBTNode<T> findMaxCountNode() { 
    return findMaxCountNode(root); 
} 

它返回null，即使我想应该没事的，我不是擅长递归所以很明显，我失去了一些东西。如果您有任何关于我的这个练习，我愿意接受任何帮助，也有新的建议。非常感谢。

测试代码：

public static void main(String[] args) { 


    HBTree<Integer> tree = new HBTree<Integer>(); 

    tree.add(50); 
    tree.add(25); 
    tree.add(74); 
    tree.add(19); 
    tree.add(8); 
    tree.add(6); 
    tree.add(57); 
    tree.add(108); 


    System.out.println(tree.contains(108)); //contains method increases the count by one 
    System.out.println(tree.contains(8)); 
    System.out.println(tree.contains(8)); 
    System.out.println(tree.contains(108)); 
    System.out.println(tree.contains(8)); 
    System.out.println(tree.contains(108)); 
    System.out.println(tree.contains(108)); 
    System.out.println(tree.contains(108)); 

    System.out.println(tree.findMaxCountNode()); 

} 

电流输出：true true true true true true true true null

预期输出：true true true true true true true true Element: 108 Left child: 6 //this is just a toString, doesn't matter at this point Right child: null Number of hits: 5

Answer 1

好像你的两个函数看起来应该像下面这样。什么我假设这里要说的是这些功能，这是本HBTNode类中定义的，旨在找到下面最高触及数节点本身：

public HBTNode<T> findMaxCountNode(HBTNode<T> node) { 
    return findMaxCountNode(node, node); 
} 

public HBTNode<T> findMaxCountNode(HBTNode<T> node, HBTNode<T> maxNode) { 

    HBTNode<T> currMax = (node.getNumberOfHits() > maxNode.getNumberOfHits()) ? node : maxNode; 

    if (node.getLeft() != null) { 
     currMax = findMaxCountNode(node.getLeft(), currMax); 
    } 

    if (node.getRight() != null) { 
     currMax = findMaxCountNode(node.getRight(), currMax); 
    } 

    return currMax; 
} 

public int findMaxCount(HBTNode<T> node) { 
    HBTNode<T> maxNode = findMaxCountNode(node); 
    if (maxNode != NULL) 
     return maxNode.getNumberOfHits(); 
    else 
     return -1; 
} 

让我知道，如果有任何问题，这是我的头顶，但我认为指出你的方法的“整数”版本应该只使用该方法的“节点查找”版本会很有帮助。你写的找到最大值值的方法与我在这里写的找到最大值节点非常相似。