Бинарное дерево и двусвязный список: как удалить узлы?
Задача состояла в том, чтобы удалить из бинарного дерева натуральных числовых значений все значения, кратные заданному k
. Вот само дерево из кода:
1 / \ 2 3 / \ / 4 5 8 / \ / \ 6 7 9 10
В коде используются
структура для описания бинарного дерева,
стандартная очередь queue
при печати узлов дерева "по уровням" и
конвертирование бинарного дерева в двусвязный список и обратно для "чистки" вершин.
Не факт, что будет предсказуемо работать при любом k
, корректное удаление вершин из дерева - вообще задача непростая, но могут пригодиться, по меньшей мере, заполнение и вывод дерева из программки. Запускалось в консоли Studio 2015.
#include <iostream> #include <queue> #include <algorithm> using namespace std; struct node { //структура для бинарного дерева int data; //вершина дерева node *left, *right; //указатели на левого и правого потомков }; node *newnode (int data) { //создание новой вершины node *temp = new node; //у структуры тоже есть конструктор! temp->data = data; temp->left = temp->right = NULL; return temp; } void printTree (node* root) { //печать уровней дерева в консоль if (!root) return; queue <node*> q; //используем стандартную очередь для удобства q.push(root); while (!q.empty()) { int n = q.size(); while (n--) { node* temp = q.front(); q.pop(); cout << temp->data << " "; if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); } cout << endl; } } void binTreeToDblLinkList (node* root, node*& head) { //конвертирование бинарного дерева в двусвязный список if (root == NULL) return; static node* left = NULL; binTreeToDblLinkList(root->left, head); if (left == NULL) head = root; else { root->left = left; left->right = root; } left = root; binTreeToDblLinkList(root->right, head); } void deletenode (node*& head, node* del) { //удалить одну вершину из двусвязного списка if (head == NULL || del == NULL) return; if (head == del) head = del->right; if (del->right != NULL) del->right->left = del->left; if (del->left != NULL) del->left->right = del->right; free(del); //если освобождаем память физически } void removeKeys(node*& head, int k) { //удалить вершины, кратные k, из двусвязного списка if (head == NULL) return; node* current = head; node* right; while (current != NULL) { if (current->data % k == 0) { right = current->right; deletenode (head, current); current = right; } else current = current->right; } } node* dblLinkListToBinTree (node*& head, int n) { //конвертирование двусвязного списка в бинарное дерево if (n <= 0) return NULL; node* left = dblLinkListToBinTree(head, n / 2); node* root = head; root->left = left; head = head->right; root->right = dblLinkListToBinTree(head, n - n / 2 - 1); return root; } node* removeMultiplesUtil(node* root, int k) { //удалить вершины, кратные k, из бинарного дерева node* head = NULL; binTreeToDblLinkList(root, head); removeKeys(head, k); node* temp = head; int n = 0; while (temp) { ++n; temp = temp->right; } return dblLinkListToBinTree(head, n); } void removeMultiples(node*& root, int k) { //Основная функция задачи if (!root) return; root = removeMultiplesUtil(root, k); } int main() { int k = 2; //будем удалять из исходного дерева вершины, кратные этому значению //Формируем дерево: node *root = newnode(1); node * r2 = root->left = newnode(2); node * r3 = root->right = newnode(3); r2->left = newnode(4); r2->right = newnode(5); r2->left->left = newnode(6); r2->left->right = newnode(7); r3->left = newnode(8); r3->left->left = newnode(9); r3->left->right = newnode(10); cout << "Source binary tree:" << endl; printTree(root); removeMultiples(root, k); cout << "Updated binary tree:" << endl; printTree(root); cin.get(); return 0; }
14.02.2019, 14:19 [1903 просмотра]