İkili arama ağacında en küçük değer nasıl bulunur?

Question

Verilen kodları kullanarak, bir ikili arama ağacındaki en küçük değere sahip düğümdeki bilgilere bir başvuru döndüren bir istemci yöntemi yazmam gerekiyor. İşte

Ben yöntemin bu imzayı kullanmak zorunda ZIP FILE

geçerli:

Golfçü dakika (BinarySearchTree ağacı)

İşte

yazdım budur:

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

Answer 1

Sanırım aradığınızı tahmin ediyorum. hepsi geçiyor çünkü O (n) süresi: Minimum skor

Yöntem 1 ile Golfçü: O (lg (n)) zaman ağacın sol tarafı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(); 
} 

Yöntem 2 aşağı çalıştığından ağaçta elemanları Burada

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

sipariş kastetmek bir oluşturmak için yukarıdaki kodu test etmek için bazı kod

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

Çıktı:

min name: E, min score: 3