二叉搜索树遍历问题
来源：6-1 为什么要研究树结构
MMXDH
2018-10-24
bobo老师，您好！刚买了您这门课，我想请教一下如何用BST实现从数组中获取前K个最小数，我想了很久一直没有思路😂，感谢！
写回答
1回答
-
在BST中找到第k小的树是一个很经典的面试问题：）
整体大概思路是：由于BST中，根节点的左子树的所有值都小于根节点；右子树的所有值都大于根节点。所以，我们要求整棵树的第k小元素，只要看根节点的左子树有多少个元素就好了。
如果根节点的左子树包含的元素个数left_num == k - 1，那么，根节点就是第k个元素！
如果根节点的左子树包含的元素个数left_num < k - 1，那么，整棵树的第k小元素在根节点的左子树中，我们继续找根节点的左子树的第k小元素就好了。
如果根节点的左子树包含的元素个数left_num > k - 1，那么，整棵树的第k小元素在根节点的右子树中，我们继续找根节点的右子树的第k - left_num - 1小元素就好了，这个数字是我们排除到了左子树的元素个数以及根节点：）
代码如下：（Java）
// Definition for binary tree: // class Tree<T> { // Tree(T x) { // value = x; // } // T value; // Tree<T> left; // Tree<T> right; // } // 递归计算二分搜索树t的节点个数 int num(Tree<Integer> t){ if(t == null) return 0; return 1 + num(t.left) + num(t.right); } // 求二分搜索树t的第k小元素 int kthSmallestInBST(Tree<Integer> t, int k) { // 计算t的左子树节点个数 int left = num(t.left); // 如果左子树节点个数 + 1(根节点)就是k，当前根节点就是结果 if(k == left + 1) return t.value; // 如果 k <= left，则继续在t的左子树寻找第k小元素 if(k <= left) return kthSmallestInBST(t.left, k); // 否则，在t的右子树寻找第k - left - 1小元素 return kthSmallestInBST(t.right, k - left - 1); }在上面的代码中，我们使用了一个子过程来计算一棵树的节点个数。但是，可以再建树的过程中，在Node里存储一个size，用于记录以当前Node为根节点的树的节点总数，并且在添加新节点或者删除节点的时候，对size进行维护。这样做，在计算第k小节点的时候，就不需要重复计算一棵树的节点总数了。可以试试看：）
上面的代码是获得第k小的节点。如果要想获得前k个节点，整体思路也是一致的，具体实现上要有一些小改动，有兴趣也可以试试看：）
加油！：）
032018-10-25
相似问题