Как найти N-й элемент в двоичном дереве поиска?

У меня есть двоичное дерево поиска в C, цель в настоящее время состоит в том, чтобы найти N-й элемент в дереве. Я пытаюсь сделать это рекурсивно, однако это не имеет первостепенного значения. У меня есть доступ к количеству узлов под любым заданным узлом (включительно).

Я попробовал этот блок кода:

TreeNode* findNthElement(int N, TreeNode* tree) {
  static int count = 0;
  printf("nodeCount: %d\nN: %d\nCount: %d\n", tree->nodeCount, N, count);//debug
  //null case
  if (tree == NULL) {
    return NULL;
  }
  //recursion
  if (count <= N) {
    findNthElement(N, tree->left);
    count++;
    if (count == N) {
      count = 0;
      return tree;
    }
    findNthElement(N, tree->right);
  }
}

Предполагается, что это рекурсивная функция для выполнения моей задачи, но значение count всегда равно 0, даже если оно статично. Я также пытался инициализировать счетчик вне функции и сбрасывать его на 0 в случае успеха или неудачи, но это также не удалось.

Отредактируйте вопрос, чтобы предоставить минимальный воспроизводимый пример. Уточните утверждение «значение count всегда равно 0»: как вы наблюдали значение count и когда?

Eric Postpischil 16.11.2022 21:18

Не используйте static int для хранения информации в рекурсивной функции. Если вам нужна дополнительная информация в вызове, вы должны передать ее в качестве аргумента. Но, в этом случае, вам не потребуется дополнительная информация. Чтобы найти N-й элемент (начиная с 1-го, а не с 0-го): пусть L и R будут номерами узлов в левом и правом поддеревьях. Если N больше, чем количество узлов в текущем дереве, N-го узла нет. В противном случае, если N ≤ L, N-й узел является N-м узлом левого поддерева. В противном случае, если N равно L+1, это текущий узел. В противном случае это (N-L-1)-й узел правого поддерева.

Eric Postpischil 16.11.2022 21:28
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
2
137
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

этот код мне неизвестен, но, может быть, count++ нужно пройти перед рекурсией? Потому что вы вызываете рекурсию, не увеличивая количество в своем коде. Пример:

if (count <= N) {
    count++;
    findNthElement(N, tree->left);

чтобы найти n-й наименьший элемент в BST, вы можете применить логику следующим образом:

using System.Collections.Generic;
public int smallElement(int k)
{
    Node<T> node = Root;
    int count = k;
    int sizeOfSubTree =0;
    
    while (node != null)
    {
        sizeOfSubTree = node.SizeOfLeftSubTree();
        if (sizeOfSubTree +1 == count)
        {
            return node.Value;
        }
        else if (sizeOfSubTree +1 < count)
        {
            node=node.Right;
            count -= sizeOfSubTree +1 ;
            
        }
        else
        {
            
            node = node.Right;
        }
        
    }
    return -1;
    
    
}

вы также можете проверить следующие ресурсы, чтобы получить помощь:

обход по порядку для нахождения n-го узла

Найдите k-й наименьший узел в двоичном дереве поиска (BST)

надеюсь, это может помочь вам.

Я считаю, что это неправильный язык, мой парень. Похоже на C#. ОП спрашивает о C.

Jason 16.11.2022 21:15

Вам вообще не нужно определять count как статический, вы можете напрямую увеличивать параметр и вызывать рекурсивно, пока N == count. Всякий раз, когда вы вызываете функцию, даже рекурсивно, в стеке памяти создается новая переменная count.

TreeNode* findNthElement(int N, TreeNode* tree, int count) {
    TreeNode * nthTree = NULL;
    if (tree == NULL) 
        return NULL;

    //Found the Nth element
    if (count == N){
       return tree;
    }
    
    //Not using ++count just for clarity
    //First it will check left subtree, if its Nth then return it else go right
    nthTree = findNthElement(N, tree->left, count+1); //Recursive call for left node

    //Recursive call for right node
    return (nthTree == NULL) ? findNthElement(N, tree->right, count+1) : nthTree; 
     
}

Как это может работать? Предположим, у нас есть бинарное дерево с левым поддеревом, содержащим только A, корнем, содержащим B, и правым поддеревом, содержащим C. Если мы используем обычные числа с отсчетом от нуля, A — 0-е, B — 1-е, а C — 2-е. Если вызывающая сторона хочет 1-й узел и вызывает findNthElement(1, tree, 0), count == N терпит неудачу, поэтому подпрограмма выполняет рекурсивные вызовы, ни один из которых не может найти B.

Eric Postpischil 16.11.2022 21:34

@EricPostpischil, когда N == Count терпит неудачу, программа вызывает функцию с левым поддеревом (здесь A), а также увеличивает счетчик на единицу в аргументах. Итак, теперь в этом вызове N == count истинно, и он вернет узел A.

Muhammad Zeeshan 16.11.2022 21:37

А - неправильный ответ. 1-й узел - это B, а не A

Eric Postpischil 16.11.2022 21:38

@EricPostpischil, это тоже зависит от заказа до / в / после. я воспринял это как неупорядоченный обход

Muhammad Zeeshan 16.11.2022 21:39

Кроме того, findNthElement(N, tree->left, count+1); не может ничего вернуть вызывающей стороне текущего экземпляра функции. Единственными операторами return в коде в этом ответе являются return tree; и return NULL;, поэтому он может возвращать только переданные tree или NULL.

Eric Postpischil 16.11.2022 21:40

@EricPostpischil да, это была ошибка, я обновил это, чтобы возвращать значения

Muhammad Zeeshan 16.11.2022 21:50
Ответ принят как подходящий

Ваш код игнорирует узел, возвращаемый рекурсивным вызовом, поэтому, если этот рекурсивный вызов нашел целевой узел, вызывающая сторона не знает об этом. Более того, после вызова findNthElement(N, tree->right) ничего не возвращается.

Кроме того, вы не должны использовать статический счетчик. Логику подсчета можно удовлетворить, уменьшив значение, которое будет передано в качестве N-аргумента рекурсивному вызову.

Вот реализация:

TreeNode* findNthElement(int n, TreeNode* tree) {
    if (tree == NULL) {
        return NULL;
    }
    int currentNum = tree->left == NULL ? 1 : tree->left->nodeCount + 1;
    return n == currentNum ? tree // Found it!
         : n <  currentNum ? findNthElement(n, tree->left) 
                           : findNthElement(n - currentNum, tree->right);
}

Мы могли бы рассмотреть возможность удаления || tree->nodeCount < n. В этом случае произойдет рекурсия к правому поддереву, которое в конечном итоге вернет null на листе. Это меняет проверку tree->nodeCount < n в каждом вызове (обычно) на напрасный обход, когда проверка была бы истинной (вероятно, редко).

Eric Postpischil 16.11.2022 22:28

Согласованный. Убрал это условие. Спасибо, Эрик. Я думаю, по тем же причинам мы могли бы удалить и условие n < 1.

trincot 16.11.2022 22:31

Это сработало после редактирования! Спасибо за помощь тринкот и Эрик!

The Rodeo Expert 16.11.2022 22:40

Другие вопросы по теме