Нахождение k-го наименьшего значения в BST

Question

Вот что я должен найти k-е наименьшее значение в двоичном дереве поиска:

struct treeNode 
{
   int data;
   struct treeNode *left, *right:
};

int rank(stuct treeNode* ptr, int k)
{
   if(node == NULL)
    return root; 

   while(ptr->left != NULL) {
     ptr = ptr->left;
     return rank(ptr->left)
   }
}

Это явно не правильно. Не предоставив решения, кто-то может направить меня в правильном направлении, как я могу решить эту проблему? У меня проблемы с выяснением, как я могу найти k-й наименьший элемент в BST.

Answer 1

BST - это отсортированное двоичное дерево, обход по порядку (левое поддерево, текущий узел, правое поддерево) даст отсортированные значения узлов. Чтобы найти k-й наименьший узел, просто выполните обход по порядку со счетчиком. Счетчик начинается с 0, при каждом обходе узла увеличивайте его на единицу, когда он достигает k, узел является k-м наименьшим.

Answer 2

Если у вас есть размеры каждого из поддеревьев, это может быть выполнено без необходимости считывать данные в массив (или иным образом обходить дерево) и считать. Если вы не держите информацию о размере под рукой, вам понадобится вспомогательная функция для расчета размера.

Основная идея, выяснить, что является индексом текущего узла. Если это меньше, чем k, вам нужно искать левое поддерево Если оно больше, чем k, ищите справа смещение узлов, отсчитываемых от левого и текущего. Обратите внимание, что это по сути то же самое, что и поиск через обычный BST, за исключением того, что в этот раз мы ищем по индексу, а не по данным. Какой-то псевдокод:

if size of left subtree is equal to k:
    // the current node is kth
    return data of current node
else if size of left subtree is greater than k:
    // the kth node is on the left
    repeat on the left subtree
else if size of left subtree is less than k:
    // the kth node is on the right
    reduce k by the size of the left subtree + 1 // need to find the (k')th node on the right subtree
    repeat on the right subtree

Чтобы проиллюстрировать это, рассмотрите это дерево с отмеченными индексами (даже не беспокойтесь о данных, так как это не важно при поиске):

        3
      /   \
     2     6
    /     / \
   0     4   7
    \     \
     1     5

Предположим, мы хотим найти второе (k = 2).
Начиная с 3, размер левого поддерева равен 3.
Он больше k, поэтому перейдите к левому поддереву.
Размер левого поддерева равен 2.
k также равно 2, поэтому текущий узел должен быть вторым.

Предположим, мы хотим найти четвертое (k = 4).
Начиная с 3, размер левого поддерева равен 3.
Это меньше чем l, поэтому установите новое k равным 0 (k '= 4 - (3 + 1)) и перейдите к правому поддереву.
Начиная с 6, размер левого поддерева равен 2.
Это больше, чем k '(0), поэтому перейдите к левому поддереву.
Размер левого поддерева - 0.
k 'также равно 0, поэтому текущий узел должен быть четвертым.

Вы поняли.

Answer 3

Это должно работать:

int rank(struct treeNode* n,int k,int* chk)
    {
    if(!n) return -1;
    int _chk = 0;
    if(!chk) chk = &_chk;

    int t = rank(n->left,k,chk);
    if(t>=0) return t;

    if(++*chk > k) return n->data;

    int t = rank(n->right,k,chk);
    if(t>=0) return t;
    return -1;
    }

вызов как rank(root,k,0)