c - 在节点中有多个元素的B树中递归查找第k个最小元素

假设我们有下面的b-树

我想创建一个算法，以便找到第k个最小元素。我试着实现这篇link中所写的内容，但我发现没有一个解决方案适合这种树。
到目前为止，我已经做到了，这对最后一个分支的元素来说是很好的

i <-0
function kthSmallestElement(Node node, int k)
    if(branch[i] != NULL) then
        size<-branch[i].size();
    if(k < size) then
        i++;
        call the function recursively for new branch[i], k
    else if(k > size) then
        k-=size
        i++;
        call the function recursively for new branch[i], k
    else if (k==size) then
        print branch[i]->entry[k-1]
    else
        print brach[i-1]->entry[k-1]
end function

我已经用C语言实现了这个算法

#define MAX 4      /* maximum number of keys in node. */
#define MIN 2      /* minimum number of keys in node */

typedef int Key;

typedef struct {
   Key key;
   int value;     /* values can be arbitrary */
} Treeentry;


typedef enum {FALSE, TRUE} Boolean;

typedef struct treenode Treenode;

struct treenode {
  int count;     /* denotes how many keys there are in the node */
    /*
        The entries at each node are kept in an array entry
          and the pointers in an array branch
    */
  Treeentry entry[MAX+1];
  Treenode *branch[MAX+1];
};

int i = 0;
int size = 0;
void FindKthSmallestElement(Treenode *rootNode, int k){
  if(branch[i] != NULL) //since the node has a child
    size = branch[i] ->count;
    if(k < size){
      i++;
      FindKthSmallestElement(branch[i], k);
    }else if(k > size){
      k-=size;
      i++;
      FindKthSmallestElement(branch[i], k);
    }else if (k==size)
      printf ("%d", branch[i]->entry[k-1].key);
    else
      printf ("%d", brach[i-1]->entry[k-1].key);
}

你能建议我在这个问题上应该做些什么，以便对每一个第k个最小的元素都有一个有效的输出吗？我倾向于认为这个问题不能递归地解决，因为每个节点中都有多个条目。把它做成这样的堆树是明智的吗？

最佳答案

这个问题可以递归地解决。您只需要让函数返回两个值：
第k个最小的键（或指向它的指针），如果它有k个或更多的键。
如果树的密钥少于k，则为树的大小。
递归是通过调用（根）节点的每个子树上的函数来实现的，从最左边到最右边，并使用不同的（递减的）参数k：
让原始树/当前树为r，通过调用r最左边子树上的函数（k与r receives相同）开始递归。
如果在R的子树上调用函数成功地返回第k个最小键，那么这就是答案并返回它。
如果在r的某个子树t上调用函数找不到第k个最小键，而是返回一个t大小的a，比如n（如果t是最右边的子树，那么r有少于k个项，返回r的大小（通过求其所有子树的大小和r根中键的数目之和可以找到r的大小）。
如果n==k-1，则第k个最小键是紧靠t右边的键
如果n显然，你必须考虑到树的根不再有子树的最终条件。从概念上讲，允许包含0键的空子树可能更容易处理。