Пример программы, реализующей бинарное дерево

Бинарные деревья

Дерево — это иерархическая структура данных, состоящая из элементов (вершин, или узлов), которые связаны между собой отношениями типа «родительская вершина – дочерняя вершина». Определить дерево с вершинами типа T можно следующим образом:

это либо пустое дерево, не содержащее ни одной вершины;
либо некоторая вершина типа T, соединенная ветвями с конечным числом отдельных деревьев с вершинами типа T (эти деревья называются поддеревьями).

Чаще всего дерево изображается в виде графа, вершинами которого являются вершины дерева, а ребрами — его ветви. Начальная вершина дерева, называемая корнем, изображается в верхней части графа, и считается, что она находится на нулевом уровне. Вершина Y, расположенная ниже вершины X и соединенная с ней ветвью, называется непосредственным потомком вершины X, или ее дочерней вершиной (а вершина X, соответственно, — непосредственным предком вершины Y, или ее родительской вершиной). Если вершина X находится на уровне K, то считается, что все ее непосредственные потомки находятся на уровне K + 1. На графе, изображающем дерево, все вершины одного уровня располагаются на одной горизонтали. Номер максимального уровня дерева называется глубиной (или высотой) дерева. Если вершина не имеет потомков, то она называется терминальной вершиной, или листом. Нетерминальная вершина называется внутренней. Число непосредственных потомков внутренней вершины дерева называется степенью этой вершины. Максимальная степень всех вершин дерева называется степенью дерева. Дерево называется упорядоченным, если все непосредственные потомки любой вершины упорядочены.

Определение дерева имеет исключительно рекурсивную природу.

Особым видом деревьев являются бинарные деревья. Бинарное дерево с вершинами типа T можно определить следующим образом:

это либо пустое дерево, не содержащее ни одной вершины;
либо некоторая вершина типа T, соединенная ветвями с двумя бинарными деревьями с вершинами типа T (эти деревья называются левым и правым поддеревом).

Рисунок 1 – Бинарное дерево

Способы обхода дерева

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

Хотя три элемента (корень, левое поддерево, правое поддерево) можно упорядочить шестью способами, обычно используются те способы, в которых левое поддерево обрабатывается до правого. Каждый из этих трех способов перебора вершин дерева имеет свое название. Порядок перебора «левое поддерево – корень – правое поддерево» называется инфиксным (симметричный обход), вариант «корень – левое поддерево – правое поддерево» — префиксным (прямой обход), а вариант «левое поддерево – правое поддерево – корень» — постфиксным (обход снизу).

Рисунок 2 – Инфиксный порядок перебора: «a b c d e f g»

Рисунок 3 – Префиксный порядок перебора: «d b a c f e g»

Рисунок 4 – Постфиксный порядок перебора: «a c b e g f d»

Пример программы, реализующей бинарное дерево

#include stdafx.h

#include conio.h

#include windows.h

struct BTree *stree(struct BTree *root, struct BTree *r, char info);

struct BTree *dtree(struct BTree *root, char key);

struct BTree

{

char info;

struct BTree *left;

struct BTree *right;

};

int _tmain(int argc, _TCHAR* argv[])

{

struct BTree *root = NULL;

SetConsoleOutputCP(1251);

SetConsoleCP(1251);

root = stree(root,root,’d’);

root = stree(root,root,’b’);

root = stree(root,root,’a’);

root = stree(root,root,’c’);

root = stree(root,root,’f’);

root = stree(root,root,’g’);

root = stree(root,root,’e’);

root = dtree(root, ‘b’);

root = dtree(root, ‘d’);

root = dtree(root, ‘a’);

root = dtree(root, ‘c’);

root = dtree(root, ‘e’);

root = dtree(root, ‘f’);

root = dtree(root, ‘g’);

_getch();

return 0;

}

struct BTree *stree(struct BTree *root, struct BTree *r, char info)

{

if(!r)

{

r = new struct BTree;

r-left = NULL;

r-right = NULL;

r-info = info;

if(!root)

return r;

if(infoinfo)

root-left = r;

else

root-right = r;

return r;

}

if(infoinfo)

stree(r,r-left,info);

else

stree(r,r-right,info);

return root;

}

struct BTree *dtree(struct BTree *root, char key)

{

struct BTree *p,*p2;

if(!root) return root;

if(root-info == key) {

if(root-left == root-right){

free(root);

return 0;

}

else if(root-left == NULL) {

p = root-right;

free(root);

return p;

}

else if(root-right == NULL) {

p = root-left;

free(root);

return p;

}

else {

p2 = root-right;

p = root-right;

while(p-left) p = p-left;

p-left = root-left;

free(root);

return p2;

}

if(root-info right = dtree(root-right, key);

else root-left = dtree(root-left, key);

return root;

}

Варианты заданий к практической работе №1

Вариант 1

1.)Дано число N (0) и набор из N чисел. Создать бинарное упорядоченное дерево (в котором левое поддерево содержит вершины, меньшие или равные корню, а правое содержит вершины, большие корня), содержащее N вершин со значениями из исходного набора.

2.)Вывести значения всех вершин дерева в префиксном порядке (вначале выводится значение корня, затем – содержимое левого поддерева в префиксном порядке, затем – содержимое правого поддерева в префиксном порядке).

3.)Вывести количество вершин дерева, значение которых равно значению, введенному с клавиатуры.