求BST中第K个最小的元素

给定一棵 BST，请在这棵 BST 上查找其对应的升序序列中的第 k 个元素（即第 k 小元素）。如下图的 BST，如果 k=3，那么所求节点为 10，如果 k=5，那么所求节点为 14。

解法一：中序遍历法，我们用一个栈作为辅助进行中序遍历，在遍历过程中，对出栈次数进行计数，出栈 k 次时即找到我们要的节点。算法复杂度为 O(n)，n 为树的节点总数，算法描述如下：

/* initialization */
pCrawl = root
set initial stack element as NULL (sentinal)

/* traverse upto left extreme */
while(pCrawl is valid )
   stack.push(pCrawl)
   pCrawl = pCrawl.left

/* process other nodes */
while( pCrawl = stack.pop() is valid )
   stop if sufficient number of elements are popped.
   if( pCrawl.right is valid )
      pCrawl = pCrawl.right
      while( pCrawl is valid )
         stack.push(pCrawl)
         pCrawl = pCrawl.left

C 实现

#include <stdio.h&g

最后

以上就是勤奋黑裤为你收集整理的求BST中第K个最小的元素的全部内容，希望文章能够帮你解决求BST中第K个最小的元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。