Блог

Вот что мне нужно, чтобы найти 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.

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

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

Основная идея, выяснить, каков индекс текущего узла. Если оно меньше 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
  

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

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

Вы поняли идею.

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

 int rank(struct treeNode* n,int k,int* chk)
    {
    if(!n) return -1;
    int _chk = 0;
    if(!chk) chk = amp;_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)