函数 returns 二叉搜索树中的第 k 个值

Question

我需要编写一个函数，return在二叉搜索树中获取第 k 个值

例如，如果这是二叉搜索树：

                                  50
                                 /  \
                               46    58
                              / \    / \
                            32  48  53  67

那么如果 k=3 那么函数应该 return 48

因为48在他的尺码中排在第三位。

32,46,48,50,53,58,67.

我的想法是以某种方式使用 inorder 但我被困了很多小时，我认为这不应该很难，我需要一个伪代码或比我的代码更好的代码。

这是我在 JAVA eclipse 中所做的：

private static void k_val_inorder(TreeItem x,int k)
{       
    if (x != null&&k!=0)
    {
        k_val_inorder(x.getLeft(),k--);
        System.out.print(x.getKey()+" ");
        k_val_inorder(x.getRight(),k--);        
    }   

}

有什么想法吗？

Answer 1

给定 TreeNode class 来实现一个二叉树：

public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int data) {
        this.data = data;
    }
}

给定二叉树的中缀遍历：

public void inFix(TreeNode root, List<Integer> inFixRep) {
    if (root != null) {
        inFix(root.left, inFixRep);
        inFixRep.add(root.data);
        inFix(root.right, inFixRep);
    }
}

以上方法填充一个List<Integer>。该列表包含给定二叉树的中缀表示。要获取第 k 个节点，只需获取列表的第 (k-1) 个元素，如 inFixRep.get(k-1).

Answer 2

Inorder 有效但是是线性的，这可以在 log(n) 时间内实现。如果你跟踪节点的子树中包含的节点数，那么你可以在对数时间安排一个函数到运行。在 python 中，它看起来像这样：

def select(node, k):
    if node == null:
        return null
    t = node.left == null ? 0 : node.count
    if t > k:
        return select(node.left, k)
    if t < k:
        return select(node.right, k-t-1)
    return node.data

编辑：

它在平衡树的 log(n) 时间内工作，但对于标准 BST，最坏情况下的时间仍然是线性的。尽管如此，它在一般情况下还是比 inorder 快。

函数 returns 二叉搜索树中的第 k 个值

function that returns the k-th value in binary search tree

java

binary-tree

binary-search-tree