Рекурсивное добавление в дерево

Содержание

Рекурсивное добавление\удалением элементов в дерево
1 ответ 1
Похожие
Подписаться на ленту
Двоичное дерево поиска — рекурсивная реализация
Замена циклов на рекурсию
Рекурсивные операции с пересборкой дерева

Рекурсивное добавление\удалением элементов в дерево

Собственно, само дерево выше. Не могу написать рекурсивную вставку и удаление. Итеративный вариант сделал. А вот с рекурсией проблемы.

void Insert(Node *node, int info) < if (node == nullptr) < node = new Node(); node->info = info; > else < if (info >root->info) < Insert(root->right, info); > else if (info < root->info) < Insert(root->right, info); >; > >

BinarySearchTree tree = new BinarySearchTree(); tree->Insert(tree->GetNode(), 10);

Имена переменных исправил. Функцию тоже, однако все равно, после вставки, корень дерева указывает на NULL

1 ответ 1

Проблема может быть в том, что у вас никогда не меняется переменная root класса BinarySearchTree . Исправить это можно, например, передавая в функцию insert не указатель на вершину дерева ( Node *node ), а ссылку на указатель ( Node *&node ).

class BinarySearchTree < private: struct Node < Node *left = nullptr; Node *right = nullptr; int key; Node(int key) : key(key) <>>; static void insert(Node *&node, int key) < if (node == nullptr) < node = new Node(key); >else < if (key < node->key) < insert(node->left, key); > else if (key > node->key) < insert(node->right, key); > // если key == node->key, то такой ключ уже есть в дереве, поэтому мы ничего не делаем > > Node *root = nullptr; public: void insert(int key) < insert(root, key); >>; int main()

Подписаться на ленту

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Источник

Двоичное дерево поиска — рекурсивная реализация

Теги: Двоичное дерево поиска. БДП. Рекурсивные алгоритмы работы с двоичным деревом поиска. Узел без ссылки на родителя.

Д ля двоичного дерева, как и для списка, можно дать простое рекурсивное определение. Двоичное дерево либо пусто, либо состоит из узла, каждая ветвь которого является деревом. Под пустым деревом будем понимать NULL. Соответственно, его наследников либо нет (тогда указатель равен NULL), либо наследники являются узлами, у каждого из которых есть свои наследники. В двоичном дереве поиска элемент меньше корня находятся слева, а больше — справа. Этот порядок сохраняется и далее, так что каждый из наследников корневого узла также является двоичным деревом поиска. Соответственно, если мы применяем какой-то алгоритм к дереву, он же может быть применён и к поддереву, так как оно продолжает обладать всеми теми же свойствами.

Реализовать операции поиска, вставки и удаления рекурсивно можно двумя способами. Первый, самый простой, заменить все циклы на рекурсивный вызов. Таким образом, все операции, где текущий узел подменяется на своего правого или левого потомка, заменяется на вызов функции с соответствующим аргументом.

Второй подход несколько иной. Вместо вставки и удаления будем производить ПЕРЕСБОРКУ дерева. Так как новых узлов при этом не будет создаваться, то утечки памяти происходить не будет.

Замена циклов на рекурсию

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

void insertRec(Node **root, Node* parent, T value) < Node *tmp = NULL; //Если это корень, то у него нет родителя if (*root == NULL) < *root = getNode(value, parent); return; >tmp = (*root); if (CMP_GT(value, tmp->data)) < insertRec(&(tmp->right), tmp, value); > else if (CMP_LT(value, tmp->data)) < insertRec(&(tmp->left), tmp, value); > else < exit(2); >>

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

Node* getByValueRec(Node* root, T value) < if (!root) < return NULL; >if (CMP_GT(root->data, value)) < getByValueRec(root->left, value); > else if (CMP_LT(root->data, value)) < getByValueRec(root->right, value); > else < return root; >>

Поиск минимального и максимального элемента также тривиальны

Node* findMaxNodeRec(Node *root) < if (root == NULL) < exit(4); >if (root->right) < return findMaxNodeRec(root->right); > return root; > Node* findMinNodeRec(Node* root) < if (root == NULL) < exit(3); >if (root->left) < return findMinNodeRec(root->left); > return root; >

Удаление элемента выглядит похоже на итеративное удаление. Здесь также будем передавать указатель на родителя в качестве одного из аргументов.

void removeNodeRec(Node *target, T value, Node *parent) < if (target == NULL) < return; >if (CMP_GT(target->data, value)) < removeNodeRec(target->left, value, target); > else if (CMP_LT(target->data, value)) < removeNodeRec(target->right, value, target); > else < if (target->left && target->right) < >else if (target->left) < Node* localMax = findMaxNodeRec(target->left); target->data = localMax->data; removeNodeRec(target->left, localMax->data, target); > else if (target->right) < if (target->left == parent) < parent->left = target->right; > else < parent->right = target->right; > free(target); > else < if (parent->left == target) < parent->left = NULL; > else < parent->right = NULL; > free(target); > > >

Заметьте: теперь нам вообще не нужен указатель на родительский элемент! Каждый раз мы храним указатель на родителя в предыдущем вызове, передавая его в качестве аргумента в следующий, поэтому в определении узла можно отказаться от использования parent. Заодно нужно переписать функцию getNode, чтобы она не получала указатель на родителя.

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

Рекурсивные операции с пересборкой дерева

П ри рекурсивной пересборке дерева мы не нуждаемся в указателе на родителя. Родитель «при нас», это текущий элемент, так что мы можем контролировать дельнейшие действия.

Определение узла и функции, которая возвращает новый узел.

typedef int T; #define CMP_EQ(a, b) ((a) == (b)) #define CMP_LT(a, b) ((a) < (b)) #define CMP_GT(a, b) ((a) >(b)) typedef struct Node < T data; struct Node *left; struct Node *right; >Node; Node *getNode(T value) < Node* tmp = (Node*) malloc(sizeof(Node)); tmp->left = tmp->right = NULL; tmp->data = value; return tmp; >

Функция вставки нового элемента возвращает новое дерево. Это дерево построено из старого, в которое добавлен новый узел. Причём процесс пересборки в тоже время производит поиск места, в которое нужно произвести вставку.

Если функция получает NULL в качестве аргумента, то она возвращает новый узел. Если узел больше значения, которое мы хотим вставить, то левой ветви присваиваем значение, которое возвращает наша же функция insert, то есть она «дособирает» левую ветвь. Аналогично, если значение узла меньше, то мы «дособираем» правую ветвь и возвращаем узел.

Node* insert(Node* root, T value) < if (root == NULL) < return getNode(value); >if (CMP_GT(root->data, value)) < root->left = insert(root->left, value); return root; > else if (CMP_LT(root->data, value)) < root->right = insert(root->right, value); return root; > else < exit(3); >>

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

Когда мы доходим до конца дерева, то логично закончить работу и вернуть NULL.

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

if (CMP_GT(root->data, value)) < root->left = deleteNode(root->left, value); return root; > else if (CMP_LT(root->data, value)) < root->right = deleteNode(root->right, value); return root; > else < //Магия здесь >>

Если же мы наткнулись на узел, который хотим удалить, то есть несколько ситуаций.

if (root->left && root->right) < //Заменить значение текущего узла на максимум левой подветви //Удалить максимум левой подветви //Вернуть собранное значение >else if (root->left) < //Удалить узел и вернуть его левую подветвь >else if (root->right) < //Удалить узел и вернуть его правую подветвь >else < //Удалить узел и вернуть NULL >

Node* deleteNode(Node* root, T value) < if (root == NULL) < return NULL; >if (CMP_GT(root->data, value)) < root->left = deleteNode(root->left, value); return root; > else if (CMP_LT(root->data, value)) < root->right = deleteNode(root->right, value); return root; > else < if (root->left && root->right) < Node* locMax = findMaxNode(root->left); root->data = locMax->data; root->left = deleteNode(root->left, locMax->data); return root; > else if (root->left) < Node *tmp = root->left; free(root); return tmp; > else if (root->right) < Node *tmp = root->right; free(root); return tmp; > else < free(root); return NULL; >> >

Функции нахождения узла, максимум и минимума не изменятся.

Всё ещё не понятно? – пиши вопросы на ящик