Рацеев С.М. Программирование на языке Си

{

ELEMENT *q; q = root;

for(; ; )

{

if (q == NULL) return;

if (q->key == x)

{

(q->count)++; return;

}

else if (q->key > x)

if (q->left == NULL)

{

q->left = Node(x); return;

}

else q = q->left; else

if (q->right == NULL)

{

q->right = Node(x); return;

}

else q = q->right;

}

}

int main( )

{

ELEMENT *root = NULL; int a;

scanf("%d", &a); if (a != 0)

{

root = Node(a); scanf("%d", &a);

281

while (a != 0)

{

Insert(root, a); scanf("%d", &a);

}

}

Display(root); return 0;

}

Пример 6. Ниже приводится рекурсивная и итеративная функция, которая определяет, присутствует ли элемент x в дереве поиска:

Пример 7. Написать функцию удаления вершины с заданным ключом x из дерева поиска.

При удалении вершины может возникнуть один из трех слу-

чаев:

282

вершины с ключом, равным x, нет;

вершина с ключом x имеет не более одного потомка;

вершина с ключом x имеет двух потомков.

Если удаляемая вершина является листом, то она удаляется, а соответствующий указатель в ее родительской вершине устанавливается в нулевое значение.

Если удаляемая вершина имеет только одного потомка, то она удаляется, а соответствующий указатель в ее родительской вершине устанавливается на этого потомка. В этом случае вершинапотомок занимает в дереве место удаленной вершины.

В третьем случае поступаем следующим образом. Пусть q – удаляемая вершина. Находим вершину Max левого поддерева вершины q с максимальным значением ключа. Вершина Max является самой правой вершиной левого поддерева вершины q. Затем заменяем ключ и счетчик вершины q на соответствующие значения вершины Max. После этого удаляем вершину Max.

283

Пример 8. Нахождение высоты произвольного бинарного дерева.

long Height(ELEMENT *q)

{

if (q == NULL) return -1;

else

{

long i, j;

i= Height(q->left);

j= Height(q->right); if (i > j)

284

return i+1; return j+1;

}

}

Пример 9. Определение количества элементов на k-м уровне дерева.

/* переменная level отвечает за номер уровня вершины q */ long Count(ELEMENT *q, long level, long k)

{

if (q == NULL || level > k) return 0;

else

if (level == k) return 1;

else return Count(q->left, level+1, k) + Count(q->right, level+1, k);

}

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

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

/* элемент бинарного дерева */ typedef struct ELEMENT

{

int data;

struct ELEMENT *left, *right; } ELEMENT;

/* вывод на экран очередного пути */ void PrintRoute(ELEMENT **a, long n)

285

{

long i;

for (i = 0; i < n; i++) printf("%d ", a[i]->data);

printf("\n");

}

/* обход элементов бинарного дерева и формирование путей */ void ObhodTree(ELEMENT *q, ELEMENT **a, long level)

{

if (q != NULL)

{

a[level] = q; /* записываем очередную вершину в массив a */ /* если вершина дерева является листом, то выводим

очередной путь на экран

*/

if (q->left == NULL && q->right == NULL) PrintRoute(a, level + 1);

else

{

ObhodTree(q->left, a, level + 1); ObhodTree(q->right, a, level + 1);

}

}

/* выделяем память для хранения вершин дерева, которые входят в состав очередного пути

*/

a = (ELEMENT **)malloc((h + 1)*sizeof(ELEMENT *));

286

ObhodTree(root, a, 0); free(a);

return 0;

}

II способ. Для решения данной задачи используем дополнительную структуру – двусвязный список, который будет содержать элементы очередного пути бинарного дерева. Функция ObhodTree() работает следующим образом. Если очередная вершина дерева q не нулевая, тогда

1)добавляем адрес вершины q в список;

2)если вершина q является листом, тогда печатаем список, иначе, если вершина q листом не является, тогда рекурсивно

вызываем функцию ObhodTree() для элементов левого поддерева вершины q, а затем для элементов правого поддерева данной вершины;

3) удаляем вершину q из списка.

#include<stdio.h>

#include<stdlib.h>

/* элемент бинарного дерева */ typedef struct TREE_ELEMENT

{

int data;

struct TREE_ELEMENT *left, *right; } TREE_ELEMENT;

/* элемент двусвязного списка */ typedef struct LIST_ELEMENT

{

TREE_ELEMENT *node;

struct LIST_ELEMENT *next, *prev; } LIST_ELEMENT;

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

void CreateHead(LIST_ELEMENT **head, LIST_ELEMENT **last)

{

287

*head = (LIST_ELEMENT *)malloc(sizeof(LIST_ELEMENT)); (*head)->prev = (*head)->next = NULL;

*last = *head;

}

/* добавление к списку вершины дерева t */

void AddToList(LIST_ELEMENT **last, TREE_ELEMENT *t)

{

LIST_ELEMENT *q;

q = (LIST_ELEMENT *)malloc(sizeof(LIST_ELEMENT)); q->node = t;

q->next = NULL; q->prev = *last; (*last)->next = q; *last = q;

}

/* печать списка (вывод на экран очередного пути) */ void PrintList(LIST_ELEMENT *head)

{

LIST_ELEMENT *q; q = head->next; while (q != NULL)

{

printf("%d ", q->node->data); q = q->next;

}

printf("\n");

}

/* удаление из списка последнего элемента */ void DeleteFromList(LIST_ELEMENT **last)

{

LIST_ELEMENT *q; q = *last;

(*last)->prev->next = NULL; (*last) = q->prev;

288

free(q);

}

/* обход элементов бинарного дерева и формирование путей */ void ObhodTree(TREE_ELEMENT *q, LIST_ELEMENT *head,

LIST_ELEMENT **last)

{

if (q != NULL)

{

AddToList(last, q);

if (q->left == NULL && q->right == NULL) PrintList(head);

else

{

ObhodTree(q->left, head, last); ObhodTree(q->right, head, last);

}

DeleteFromList(last);

}

}

int main( )

{

LIST_ELEMENT *head = NULL, *last = NULL; TREE_ELEMENT *root = NULL;

… /* создание бинарного дерева */ CreateHead(&head, &last); ObhodTree(root, head, &last);

return 0;

}

Пример 11. На каждом уровне бинарного дерева T целых чисел найти минимальный и максимальный элементы.

Пусть min и max – два динамических массива размера h+1, где h – высота дерева T, причем min[i] (max[i]) будет содержать минимальный (максимальный) элемент i-го уровня дерева T, i=0,1,…,h.

289