二叉搜索树中第k大和第k小结点

查找二叉搜索中第k大和第k小结点 解法

构建二叉树

public class BSTNode> {
    T key;
    BSTNode left;
    BSTNode right;
    BSTNode parent;

    public BSTNode(T key, BSTNode parent, BSTNode left, BSTNode right) {
        this.key = key;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

中序遍历

   private static void inOrder(BSTNode tree, ArrayList nodeList) {
        if (tree != null) {
            inOrder(tree.left, nodeList);
            nodeList.add(tree);
            inOrder(tree.right, nodeList);
        }

    }

查找第k大结点

 
    public static BSTNode findMaxKNode(BSTNode tree, int k) {
        if (tree == null || k < 1) return null;
        // 中序遍历tree
        ArrayList nodeList = new ArrayList();
        inOrder(tree, nodeList);
        if (nodeList.size() < k) return null;
        return nodeList.get(k-1);
    }

查找第k小结点

 
    public static BSTNode findMinKNode(BSTNode tree, int k) {
        if (tree == null || k < 1) return null;
        // 中序遍历tree
        ArrayList nodeList = new ArrayList();
        inOrder(tree, nodeList);
        if (nodeList.size() < k) return null;
        return nodeList.get((nodeList.size()-k));
    }