java 二叉搜索树寻找第二小节点

Question

我正在尝试让该方法找到第二小的节点但是，当我找到最小的节点（没有正确的节点）我应该 return 节点的父节点以使其 "second" 最小。但是，我不知道要那样做......请大家帮帮我

public StringNode secondSmallest() {
    return secondSmallest(root);
}

private StringNode secondSmallest(StringNode x) {
    if(x==null);
    //base case: if the left node is null -> smallest
    if (x.getLeft()==null) {        
        //if there is only right child
        if(x.getRight()!=null) {
            return x.getRight();
        }
        //when there is no right node and smallest
        return x;
    }
    //keep finding left node
    else
        return secondSmallest(x.getLeft());

}

Answer 1

示例代码。

public interface Tree<K, V> {
       /**
     * Find the nth smallest element in the tree
     * 
     * @param nth
     * @return nth smallest element in the tree
     */
    public K findSmallest(int nth);
}

@Override


 public K findSmallest(int nth) {
    Node iterator = root;
    return traverseLeftParentRight(iterator, new AtomicInteger(nth));
  }



private K traverseLeftParentRight(Node iterator, AtomicInteger nth) {
    if (null == iterator || nth.get() == 0) {
      return null;
    }
    K value = traverseLeftParentRight(iterator.left, nth);
    // Found in the left subtree itself
    if (null != value) {
      return value;
    }
    if (nth.decrementAndGet() == 0) {
      return iterator.key;
    }
    // Check in the right subtree
    return traverseLeftParentRight(iterator.right, nth);
  }



  public static void main(String[] args) {
      // Create a BST
      Comparator comparator = integerComparator();
      Tree tree = new BinarySearchTree(comparator);
      fillData(tree);
      System.out.println("4thlest element " + tree.findSmallest(4));
   }

private static void fillData(Treetree) {
  tree.put(5, "value-5");
  for (int i = 0; i <= 10; i++) {
   tree.put(i, "value-" + i);
  }
 }

阅读这篇 Nth Samllest Element 文章了解完整详情。

java 二叉搜索树寻找第二小节点

java binary search tree finding second smallest node

java

binary-search-tree