如何在二叉搜索樹中查找最小值？

我必須編寫一個客戶端方法，該方法使用給出的代碼返回對二進制搜索樹中具有最小值的節點中的信息的引用。如何在二叉搜索樹中查找最小值？

我不得不使用方法的此簽名：

高爾夫分鐘（BinarySearchTree樹）

這裏是我寫：

Golfer min(BinarySearchTree<Golfer> tree) 
    { 
     int treeSize = tree.reset(BinarySearchTree.INORDER); 
     int numNodes = 0; 
     for(int count = 1; count <= treeSize; count++) 
     { 
     if((tree.getNext(BinarySearchTree.INORDER).compareTo(maxValue)) <= 0) 
      numNodes = numNodes + 1; 
     } 
     return numNodes;  
    }

來源

2016-03-28 pyuntae

最小的值還是最小的鍵？ –

你有一個標記爲min的函數，但是你正在返回一個名爲numNodes的東西.....有一個提示。 – mwm314

@SashaSalauyou我重複檢查，並指出問題中的最小值。 – pyuntae

我猜你正在尋找高爾夫球手的最低分數

方法1：O（LG（n））的時間，因爲它運行在樹中的左側

public Golfer min(BinarySearchTree<Golfer> tree) { 
    BSTNode<Golfer> node = tree.root; 
    if (node == null) { 
     return null; 
    } 
    while (node.getLeft() != null) { 
     node = node.getLeft(); 
    } 
    return node.getInfo(); 
}

方法2：O（n）的時間，因爲它穿過所有在樹中的元素，以便遍歷

public Golfer min2(BinarySearchTree<Golfer> tree) { 
    int treeSize = tree.reset(BinarySearchTree.INORDER); 
    if (treeSize <= 0) { 
     return null; 
    } 
    return tree.getNext(BinarySearchTree.INORDER); 
}

這裏創建的是一些代碼來測試上面的代碼

public static void main(String[] args) { 
    BinarySearchTree<Golfer> bst = new BinarySearchTree<Golfer>(); 
    bst.add(new Golfer("A", 10)); 
    bst.add(new Golfer("B", 12)); 
    bst.add(new Golfer("C", 8)); 
    bst.add(new Golfer("D", 9)); 
    bst.add(new Golfer("E", 3)); 

    Golfer min = new Test().min(bst); 
    //Golfer min = new Test().min2(bst); 
    if (min != null) { 
     System.out.println("min name: " + min.name + ", min score: " + min.score); 
    } else { 
     System.out.println("Empty tree"); 
    } 
}

輸出：

min name: E, min score: 3

來源

2016-03-28 10:50:26 abhaybhatia

如何在二叉搜索樹中查找最小值？

回答

相關問題