Нерекурсивный обход бинарного дерева без стека
Единственное, что смог найти по теме — обход Морриса, но данный алгоритм временно преобразует дерево в «прошитое» дерево, поэтому не подходит.
@VladD: Это не диссертация, я хочу разобраться с упражнением из книги Кормена. По условию константа ограничена глобально.
1 ответ 1
static void Walk(Node node) < Node lastNode = null; while (node != null) < if (lastNode == node.Parent) < if (node.Left != null) < lastNode = node; node = node.Left; continue; >else lastNode = null; > if (lastNode == node.Left) < Output(node); if (node.Right != null) < lastNode = node; node = node.Right; continue; >else lastNode = null; > if (lastNode == node.Right) < lastNode = node; node = node.Parent; >> > Но, строго говоря, в BST ссылки на родителя нет, и обойти его без модификации дерева и с лимитом на память нельзя.
@DarkGenius очень легко. Алгоритим в процессе обхода дерева из N нод может находится в N различных состояниях. т.к. дерево модифицировать нельзя, то для описания состояния требуется дополнительной памяти log2(N) бит. Приведенный выше алгоритм не попадает под требования — он не заработает на количестве нод > 2^32 — т.к. он хранит состояние как int32.
@DarkGenius ну а если расход памяти log2(N) бит приемлем (читерство!), то достаточно просто написать функцию, которая будет идти по дереву, считать ноды (нерекурсивно), и выводить N-ю ноду. И вызвать ее с параметром от 1 до N. Т.е. теоретически лимит будет нарушаться, но на практике — нет (потому что такое дерево просто не влезет в память).
Эээ. Ну то, что указатель 32-битный, это читерство немного. Дерево с к-вом узлов > 2^32 нельзя даже представить в указанном виде, не то что обойти, т. к. на каждый узел должен быть указатель.
Источник
Дерево без рекурсии
В этой статье я покажу двоичное дерево без рекурсии. Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.
Итак, начнем. Допустим есть задачка, получить много данных и вывести совпадения. Я нашел одно решение с рекурсией в интернете и понял как это сделать просто. Мне понравилось это решение, но мы знаем что рекурсия заполняет стек и если будет большая вложенность, то будет много выходов из функций. Я захотел попробовать сделать такой алгоритм, который не нуждается в рекурсии. Я буду писать на C, потому что это такой язык, который могут понять все.
Первым делом определим структуру.
Здесь number это число, по которому будет идти сортировка node. Count это количество совпадений. Step нужен будет для вывода совпадений в консоль, он будет определять, было ли вхождение в этот node или нет.
Делаем глобальную ссылку на корень дерева.
Теперь добавляем нашу функцию по вставке чисел, она выглядит немного по другому — например теперь в отличие от рекурсивной функции, она не требует адрес структуры.
static void add_node (const int number) < register struct node *prev = NULL; register unsigned long left = 0; register struct node *p = root; while (1) < if (p == NULL) < p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; if (prev) < if (left) prev->left = p; else prev->right = p; p->parent = prev; > if (root == NULL) < root = p; p->parent = NULL; > return; > prev = p; if (p->number > number) < left = 1; if (p->left && p->number < p->left->number) < register struct node *up = p; register struct node *down = p->left; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->left = down; return; > p = p->left; > else if (p->number < number) < left = 0; if (p->right && p->number > p->right->number) < register struct node *up = p; register struct node *down = p->right; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->right = down; return; > p = p->right; > else if (p->number == number) < p->count++; return; > > > Я указал локальные переменные как регистры, чтобы хоть чуточку быстрее работало. Если посмотреть через дизассемблер, то можно увидеть, что у 64 битного проца хватает регистров.
[0x00401080]> s sym.add_node [0x00401166]> pd 30 ;-- add_node: 0x00401166 55 push rbp 0x00401167 4889e5 mov rbp, rsp 0x0040116a 4155 push r13 0x0040116c 4154 push r12 0x0040116e 53 push rbx 0x0040116f 4883ec18 sub rsp, 0x18 0x00401173 897ddc mov dword [rbp - 0x24], edi 0x00401176 41bc00000000 mov r12d, 0 0x0040117c 41bd00000000 mov r13d, 0 0x00401182 488b1dcf2e00. mov rbx, qword [obj.root] ; [0x404058:8]=0 0x00401189 4885db test rbx, rbx ┌─< 0x0040118c 7559 jne 0x4011e7 Теперь добавление происходит без рекурсии. Далее надо пройтись по дереву и посмотреть есть ли совпадения. Такое тоже возможно не применяя рекурсию. Вот код.
static void find_matches ( ) < register struct node *n = root; register nm = 0; register n->step = 0; while (n) < if (n->step == 0 && n->count > 1) < printf ("%ld: %ld\n", n->number, n->count); nm++; > n->step = 1; if (n->left && n->left->step == 0) < n = n->left; continue; > else if (n->right && n->right->step == 0) < n = n->right; continue; > else if (n->step == 1) < if (n->left) n->left->step = 0; if (n->right) n->right->step = 0; n = n->parent; if (n && n->step == 1 && n->parent == NULL) < n->step == 2; continue; > else if (!n) break; > if (n->step == 1 && n->parent == NULL) break; > >Да, она выглядит больше во много чем рекурсивная функция, но это цена за реализацию поиска в одном цикле. Я использовал step переменную, чтобы определять, где уже указатель был, а где не был.
Теперь посмотрите полный код.
static void add_node (const int number) < register struct node *prev = NULL; register unsigned long left = 0; register struct node *p = root; while (1) < if (p == NULL) < p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; if (prev) < if (left) prev->left = p; else prev->right = p; p->parent = prev; > if (root == NULL) < root = p; p->parent = NULL; > return; > prev = p; if (p->number > number) < left = 1; if (p->left && p->number < p->left->number) < register struct node *up = p; register struct node *down = p->left; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->left = down; return; > p = p->left; > else if (p->number < number) < left = 0; if (p->right && p->number > p->right->number) < register struct node *up = p; register struct node *down = p->right; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->right = down; return; > p = p->right; > else if (p->number == number) < p->count++; return; > > > В целом я не видел проблем рекурсивной функции на миллион элементов или 10 миллионов, но возможно, что алгоритм, который я буду использовать, привел в этой статье, возможно будет даже лучше рекурсивной функции. Но для этого надо произвести расчёты, которые я только учусь делать.
Я поменял статью, дерево теперь сбалансированное.
Источник
C++ Симметричный обход бинарного дерева без рекурсии
Добрый день! Есть нерекурсивная функция, которая выполняет симметричный обход дерева. Вместо стека использовал деки.
struct BinaryTree < int Data; BinaryTree* Left; BinaryTree* Right; >; //создание бинарного дерева void Make_Binary_Tree(BinaryTree** Node, int n) < BinaryTree** ptr; //вспомогательный указатель srand(time(NULL) * 1000); while (n >0) < ptr = Node; while (*ptr != NULL) < if ((double)rand() / RAND_MAX < 0.5) ptr = &((*ptr)->Left); else ptr = &((*ptr)->Right); > (*ptr) = new BinaryTree(); cout > (*ptr)->Data; n--; > > // функция нерекурсивного обхода void SymmetricOrder_BinaryTree_Loop(BinaryTree* Node) < deque stack; do < while (Node != NULL) < stack.push_back(*Node); Node = Node->Left; > if (stack.size() > 0) < *Node = stack.back(); stack.pop_back(); printf("%3ld", Node->Data); Node = Node->Right; > > while (stack.size() > 0); > int main() < struct BinaryTree *nodes = < 0 >; struct BinaryTree *root = nodes; Make_Binary_Tree(&root, 8); SymmetricOrder_BinaryTree_Loop(root); system("pause"); return 0; > То есть цикл выходит за пределы дерева и указывает на пустую ячейку. По алгоритму так и должно быть, но видимо как-то по-другому реализовано. Как можно исправить, чтобы работало?
"Alexander Kagalchuk Какой смысл этого объявления struct BinaryTree *nodes = < 0 >; если переменная nodes не используется?
1 ответ 1
завершает свою работу, когда Node становится равным NULL .
Однако в последующем блоке кода предложения с if
вы разыменовываете этот указатель, который равен NULL .
В результате программа имеет неопределенное поведение.
Помимо этого имеется также логическая ошибка. Представьте, что корневой узел дерева имеет только правого потомка. Тогда в стек изначально будет занесен только этот корневой узел. В предложении с if этот узел будет извлечен из стека
В результате стек окажется пустым. И на этом завершится весь внешний цикл
несмотря на то, что корневой узел имеет правого потомка.
Также непонятно, почему вы используете стандартный контейнер std::deque в то время, как в стандарте C++ уже определен адаптер контейнера std::stack .
Также в стеке незачем хранить сами узлы. Достаточно хранить указатели на них.
Ниже приведена демонстрационная программа, которая показывает, как функция вывода дерева может быть реализована.
#include #include #include #include struct BinaryTree < int Data; BinaryTree *Left; BinaryTree *Right; >; void Make_Binary_Tree( BinaryTree **Node, size_t n ) < std::srand( ( unsigned int )std::time( nullptr ) ); for ( ; n != 0; n--) < while ( *Node != nullptr ) < if ( std::rand() % 2 == 0 ) < Node = &( *Node )->Left; > else < Node = &( *Node )->Right; > > *Node = new BinaryTree(); std::cout > ( *Node )->Data; > > // функция нерекурсивного обхода void SymmetricOrder_BinaryTree_Loop( const BinaryTree *Node ) < std::stackstack; while ( Node != nullptr || !stack.empty() ) < while ( Node != nullptr ) < stack.push( Node ); Node = Node->Left; > std::cout Data Right; stack.pop(); > > int main()
Вывод программы на консоль может выглядеть следующим образом
Введите значение узла: 1 Введите значение узла: 2 Введите значение узла: 3 Введите значение узла: 4 Введите значение узла: 5 1 2 5 4 3 Этот вывод соответствует следующему представлению дерева
Источник