Удаление элемента из дерева

Рассмотрим удаление элемента из дерева поиска (рис. 16). Следует учитывать следующие случаи:

1. Узла с требуемым ключом в дереве нет.

2. Узел с требуемым ключом является листом, т. е. не имеет потомков.

3. Узел с требуемым ключом имеет одного потомка.

4. Узел с требуемым ключом имеет двух потомков.

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

Во втором случае нужно заменить адрес удаляемого элемента нулевым. Для этого нужно выполнить обход дерева и заменить адрес удаляемого элемента нулевым. Например, при удалении элемента с ключом 7 мы меняем левое адресное поле элемента с ключом 8 на 0.

Третий случай похож на второй, т. к. мы должны заменить адресное поле удаляемого элемента адресом его потомка. Например, при удалении элемента с ключом 8 мы меняем левое адресное поле элемента с ключом 9 на адрес элемента с ключом 7.

Самым сложным является четвертый случай, т .к. возникает вопрос каким элементом мы должны заменить удаляемый элемент. Этот элемент должен иметь два свойства. Во-первых, он должен иметь не более одного потомка, а во-вторых, мы должны сохранить упорядоченность ключей, т. е. он должен иметь ключ либо не меньший, чем любой ключ левого поддерева удаляемого узла, либо не больший, чем любой ключ правого поддерева удаляемого узла. Таким свойством обладают два узла: самый правый узел левого поддерева удаляемого узла и самый левый узел правого поддерева удаляемого узла. Любым из них и можно заменить удаляемый элемент. Например, при удалении узла 9 его можно заменить узлом 12 (самый левый узел правого поддерева удаляемого узла).

Для удаления будем использовать рекурсивную функцию.

/*вспомогательная переменная для удаления узла, имеющего двух потомков*/

point *q;

Point* Del(Point* r)

{

/*удаляет узел, имеющий двух потомков, заменяя его правым узлом левого поддерева*/

if (r->right!=0) r=Del(r->right);//идем в правое поддерево

else //дошли до самого правого узла

{

    //заменяем этим узлом удаляемый

    q->key=r->key;

    q=r;

    r=r->left;

}

return r;

}

Point* Delete(Point*p, int KEY)

{

//Point*q;

if(p) //ищем узел

    if (KEY<p->key)//искать в левом поддереве

         p->left=Delete(p->left,KEY);

    else if (KEY>p->key)//искать в правом поддереве

         p->right=Delete(p->right,KEY);

    else //узел найден

    {

         //удаление

         q=p;//запомнили адрес удаляемого узла

// узел имеет не более одного потомка слева

         if(q->right==0)

              p=q->left;//меняем на потомка

         else

//узел имеет не более одного потомка справа

              if(q->left==0)

              p=q->right;//меняем на потомка

              else //узел имеет двух потомков

                   p->left=Del(q->left);

              delete q;

    }

    return p;

}

Обработка деревьев с помощью рекурсивного обхода

Задача 1. Найти количество четных элементов в дереве.

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

//количество четных элементов в дереве

void kol(Point *p, int &rez)

{

if(p)

{

kol(p->left,rez);

if(p->key%2==0)rez++;

kol(p->right, rez);

}

}

Задача 2. Найти количество отрицательных элементов в дереве.

Решается аналогично предыдущей.

//количество отрицательных элементов в дереве

void quantity_otr(int a,int &k)

{

if(a<0)k++;

}

void kol(Point *p,void (*ptr)(int,int&), int &rez)//итератор

{

if(p)

{

kol(p->left,quantity_otr,rez);

ptr(p->key,rez);

kol(p->right, quantity_otr,rez);

}

}

Препроцессорные средства

Стадии и команды препроцессорной обработки

Назначение препроцессора – обработка исходного текста программы до ее компиляции (можно назвать первой фазой компиляции). Инструкции препроцессора называют директивами. Они начинаются с символа #.

На стадии обработки директив препроцессора возможно выполнение следующих действий:

1. Замена идентификаторов заранее подготовленными последовательностями символов (#define).

2. Включение в программу текста из указанных файлов (#include).

3. Исключение из программы отдельных частей (условная компиляция).

4. Макроподстановка, т. е. замена обозначения параметризируемым текстом.

Директива #define

Директива #define имеет несколько модификаций. Они предусматривают определение макросов или препроцессорных идентификаторов, каждому из которых ставится в соответствие некоторая последовательность символов. В последующем тексте программы препроцессорные идентификаторы заменяются на заранее оговоренные последовательности символов.

#define идентификатор строка_замещения

Таблица 2. Пример работы директивы define

С помощью #define удобно определять размеры массивов

Таблица 3. Пример работы директивы define

Те же возможности в С++ обеспечивают константы, определенные в тексте программы. Поэтому в С++ по сравнению с классическим С #define используется реже.

void main() //использование констант в С++

{

const int N=10;

const int M=100;

int matr[N][N];

double mas[M]

}

Включение текстов из файлов

Для включения текста из файла используется команда #include. Она имеет две формы записи:

#include <имя_файла>

#include “имя_файла”

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

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

Заголовочные файлы оказываются эффективным средством при модульной разработке крупных программ, в которых используются внешние объекты (переменные, массивы, структуры), глобальные для нескольких частей программы. Описание таких объектов помещается в одном файле, который с помощью директивы include включается во все модули, где необходимы эти объекты.

//файл tree. h

//дерево и функции для его формирования и печати

#include <iostream.h>

struct Point

{

int key;

Point*left,*right;

};

Point* first(int d)//формирование первого элемента дерева

{

Point* p=new Point;

p->key=d;

p->left=0;

p->right=0;

return p;

}

Point* Add(Point*root,int d)//добавление элемента d в дерево поиска

{

Point*p=root,*r;

bool ok=false;

while(p&&!ok)

{

  r=p;

  if(d==p->key)ok=true;

  else

       if(d<p->key)p=p->left;//пойти в левое поддерево

       else p=p->right;//пойти в правое поддерево

}

if(ok) return p;//найдено, не добавляем

//создаем узел

Point* New_point=new Point();//выделили память

New_point->key=d;

New_point->left=0;

New_point->right=0;

if(d<r->key)r->left=New_point;

else r->right =New_point;

return New_point;

}

void Show(Point*p,int level)

{

if(p)

{

  Show(p->left,level+5);

  for(int i=0;i<level;i++)cout<<" ";

  cout<<p->key<<"\n";

  Show(p->right,level+5);

}

}

//Файл с основной программой

#include <iostream.h>

#include "tree.h"

void main()

{

int n,k;

cout<<"n?";

cin>>n;

Point *root=first(10);//первый элемент

for(int i=0;i<n;i++)

{

  cout<<"?";

  cin>>k;

  Add(root,k);

}

Show(root,0);

}

Препроцессор добавляет текст файла tree.h в файл, в котором расположена основная программа и как единое целое передает на компиляцию.

Условная компиляция

Для условной компиляции используются следующие команды:

Общая структура применения директив условной компиляции следующая:

# if условие текст1

#else текст2

#endif

Конструкция #else текст2 необязательна. текст1 включается в компилируемый текст только при истинности проверяемого условия. Если условие ложно – то при наличии директивы else на компиляцию передается текст2, если эта директива отсутствует, то при ложном условии текст1 просто опускается.

Различие между форматами команд #if следующее:

1. Директива #if константное_выражение проверяет значение константного выражения. Если оно отлично от нуля, то считается, что проверяемое условие истинно.

2. В директиве #ifdef препроцессорный идентификатор проверяется, определен ли с помощью директивы #define идентификатор, помещенный после #ifdef. Если идентификатор определен, то текст1 используется компилятором.

3. В директиве #ifndef препроцессорный идентификатор проверяется обратное условие: истинным считается неопределенность идентификатора. Если идентификатор не определен, то текст1 используется компилятором.

Файлы, которые предназначены для препроцессорного включения, обычно снабжают защитой от повторного включения. Такое повторное включение может произойти, если несколько модулей, в каждом из которых подключается один и тот же файл, объединяются в общий текст программы. Такими средствами защиты снабжены все заголовочные файлы стандартной библиотеки (например, iostream.h).

Схема защиты от повторного включения:

//Файл с именем filename включается в другой файл

#ifndef _FILE_NAME

….//включаемый текст файла filename

#define _FILE_NAME 1

#include <…>//заголовочные файлы

<текст модуля>

#endif

_FILE_NAME – зарезервированный для файла filename препроцессорный идентификатор, который не должен встречаться в других текстах программы.