Node поиск в стеке Binary Tree overflows

Ответ 1

Да! Для дерева с уровнем 300 000 избегайте рекурсии. Проведите дерево и найдите значение итеративно, используя цикл.

Двоичное представление дерева поиска

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

Просто чтобы прояснить проблему дальше. Ваше дерево имеет глубину n = 300.000 уровней. Таким образом, в худшем случае Дерево двоичного поиска (BST) придется посещать ВСЕ узлов дерева. Это плохая новость, потому что худший случай имеет алгоритмическую O (n) временную сложность. Такое дерево может иметь:

2300.000 узлов = 9.9701e + 90308 узлов (приблизительно).

9.9701e + 90308 узлов - это экспоненциально массивное количество узлов для посещения. С этими числами становится настолько понятным, что переполняется стек вызовов.

Решение (итеративный способ):

Я предполагаю, что ваше объявление Node class/struct является классическим стандартным целым числом BST. Затем вы можете адаптировать его, и он будет работать:

struct Node {
    int data;
    Node* right;
    Node* left;
};

Node* find(int v) {
    Node* temp = root;  // temp Node* value copy to not mess up tree structure by changing the root
    while (temp != nullptr) {
        if (temp->data == v) {
            return temp;
        }
        if (v > temp->data) {
            temp = temp->right;
        }
        else {
            temp = temp->left;
        }
    }
    return nullptr;
}

Взяв этот итеративный подход, избегает рекурсии, тем самым избавляя вас от необходимости рекурсивно находить значение в таком большом дереве с помощью стека программных вызовов.

Ответ 2

Простой цикл, в котором у вас есть переменная типа Node *, которую вы установили в следующий node, затем снова запустите...
Не забывайте, что значение, которое вы ищете, не существует!

Ответ 3

Вы можете реализовать рекурсию, не используя стек вызовов, а определенный пользователем стек или что-то подобное; это можно сделать с помощью существующего шаблона stack. Подходом будет иметь цикл while, который выполняет итерацию до тех пор, пока стек не будет пуст; поскольку существующая реализация использует поиск по глубине, устранение рекурсивных вызовов можно найти здесь.

Ответ 4

Когда дерево, которое у вас есть, является двоичным деревом поиска, и все, что вы хотите сделать, это поиск node в нем, который имеет определенное значение, тогда все просто: рекурсии не требуется, вы можете это сделать используя простую петлю, как указывали другие.

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

Итак, чтобы избежать рекурсии, вам нужно реализовать стек в куче С++. Вам нужно объявить новый класс StackElement, который будет содержать один член для каждой локальной переменной, который имеет ваша исходная рекурсивная функция, и один член для каждого параметра, который принимала ваша оригинальная рекурсивная функция. (Вы можете уйти с меньшим количеством переменных-членов, вы можете беспокоиться об этом после того, как получите код для работы.)

Вы можете хранить экземпляры StackElement в коллекции стека или просто иметь в каждом из них указатель на его родительский элемент, тем самым полностью реализуя стек.

Итак, вместо вашей функции, которая рекурсивно вызывает себя, она будет просто состоять из цикла. Ваша функция входит в цикл с инициализацией текущего StackElement с информацией о корневом каталоге node вашего дерева. Его родительский указатель будет нулевым, что является еще одним способом сказать, что стек будет пустым.

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

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

Когда вы найдете node, который вы искали, вы просто выходите из цикла.

В качестве альтернативы, если node вашего существующего дерева поддерживает a) ссылку на свои "родительские" node и b) пользовательские данные (где вы можете сохранить флаг "посещенный" ), тогда вам не нужно реализовать свой собственный стек, вы можете просто пересечь дерево на месте: на каждой итерации вашего цикла вы сначала проверяете, является ли текущий node node, который вы искали; если нет, то вы перечисляете детей, пока не найдете тот, который еще не был посещен, а затем вы посещаете его; когда вы достигаете листа, или node, чьи дети все были посещены, затем вы возвращаетесь назад, следуя ссылке на родителя. Кроме того, если у вас есть свобода уничтожить дерево, когда вы его проходите, вам даже не нужна концепция "пользовательских данных": как только вы закончите с дочерним node, вы освободите его и сделаете его нулевым.

Ответ 5

Ну, это можно сделать хвостом рекурсивным за счет одной дополнительной локальной переменной и нескольких сравнений:

Node* find(int v){
  if(value==v)
    return this;
  else if(!right && value<v)
    return NULL;
  else if(!left && value>v)
    return NULL;
  else {
    Node *tmp = NULL;
    if(value<v)
      tmp = right;
    else if(value>v)
      tmp = left;
    return tmp->find(v);
  }
}

Ответ 6

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

Это то, что вам нужно соответствующее базовое условие. Что-то похожее:

if (treeNode == NULL)
   return NULL;

В общем, обход дерева выполняется таким образом (в C):

void traverse(treeNode *pTree){
  if (pTree==0)
    return;
  printf("%d\n",pTree->nodeData);
  traverse(pTree->leftChild);
  traverse(pTree->rightChild);
}