如何返回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; 
} 

讓我知道，如果有任何問題，這是我的頭頂，但我認爲指出你的方法的「整數」版本應該只使用該方法的「節點查找」版本會很有幫助。你寫的找到最大值值的方法與我在這裏寫的找到最大值節點非常相似。