如何在二叉搜索树中找到最小值？

rks48beu 于 2021-07-13 发布在 Java

关注(0)|答案(1)|浏览(377)

我必须编写一个客户机方法，使用给定的代码，以二叉搜索树中最小的值返回对节点中信息的引用。
这是压缩文件
我必须用这个方法签名：
golfer min（二叉树）
以下是我写的：

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

Java binary-search-tree

来源：https://stackoverflow.com/questions/36260262/how-to-find-smallest-value-in-a-binary-search-tree

1条答案

按热度按时间

uz75evzq1#

我猜你在找得分最低的高尔夫球手
方法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

赞(0）回复(0）举报 2021-07-13

我来回答

如何在二叉搜索树中找到最小值？

1条答案

相关问题

热门标签

最新问答