БлогNot. Бинарное дерево и двусвязный список: как удалить узлы?

Бинарное дерево и двусвязный список: как удалить узлы?

Задача состояла в том, чтобы удалить из бинарного дерева натуральных числовых значений все значения, кратные заданному 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 просмотра]


теги: c++ учебное ошибка памятка алгоритм

К этой статье пока нет комментариев, Ваш будет первым