Деревья

Массивы и списки являются линейными структурами данных. Списки обеспечивают последовательный доступ к элементам. В некоторых случаях необходим нелинейный порядок объектов, где элементы могут иметь несколько наследников (например, фамильное дерево).

Дерево – нелинейная рекурсивная структура, которая состоит из узлов и ветвей и имеет направление от корня к внешним узлам, называемым листьями. Лист – узел, не имеющий потомков. Каждый узел дерева является корнем поддерева, которое определяется данным узлом и всеми потомками этого узла. Глубина дерева есть максимальный уровень любого его узла или есть длина самого длинного пути от корня до листа.

Бинарное дерево – ориентированное дерево, каждый узел которого имеет 0, 1 или 2 потомка. Бинарное дерево имеет характерную особенность, заключающуюся в том, что значение в любом узле его левого поддерева меньше, а значение в любом узле его правого поддерева больше значения в его родительском узле. Используя рекурсивные функции: включения элемента в бинарное дерево и отображения дерева на экране, можно отсортировать входную последовательность данных по выбранному ключу.

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

Набор функций для работы с бинарным деревом:

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

struct btree

{

char string[N]; // строка для хранения операнда или знака операции

struct btree *left, *right;

};

1. Функция определяет баланс скобок в строке.

int Is_Balance (char *s, int left, int right)

{

for (int i = left, counter = 0; i <= right; i++)

{ if (s[i] == '(') counter ++;

if (s[i] == ')') { counter --; if (counter < 0) return 0;}

}

if (counter == 0) return 1;

return 0;

}

2. Функция находит в строке позицию знака бинарной операции.

int Is_Operation (char *s, int left, int right)

{

int x = 0, counter = 0;

for (int i = left; i <= right; i++)

switch (s[i])

{ case '(' : counter ++; break;

case ')' : counter --; break;

case '+':

case '-' : if (counter == 0) { x = i; break;}

case '*' :

case '/' : if (counter == 0)

if((x == 0)||(s[x] == '*')||(s[x] == '/')) x = i;

}

return x;

}

3. Функция построения бинарного дерева.

void Build_Btree (char *str, int left, int right, btree **q)

{

int i, z, length;

*q = new btree;

if ((str[left] == '(') && (str[right] ==')')) // Можно отбросить скобки?

if (Is_Balans (str, left + 1, right - 1)) { left ++; right --;}

z = Is_Operation (str, left, right);

// Записываем операнд в лист дерева (тривиальный случай)

if (z == 0)

{ length = right - left + 1;

(*q) -> left = (*q) -> right = NULL;

strncpy ((*q) -> string, &str[l], length);

(*q) -> string[length] = '\0';

return;

}

// Записываем в вершину знак операции (декомпозиция общего случая)

(*q) -> string[0] = str[z];

(*q) -> string[1] = '\0';

Build_Btree (str, left, z - 1, &(*q) -> left);

Build_Btree (str, z + 1, right, &(*q) -> right);

}

4. Функция обхода дерева (вычисление выражения).

int Calculate (btree *p)

{

int x, y;

if (isdigit (p -> string[0])) return (atoi (p -> string));

x = Calculate (p -> left); y = Calculate (p -> right);

switch (p -> string[0])

{

case '+' : return (x + y);

case '-' : return (x - y);

case '*' : return (x * y);

case '/' : if (y == 0) return 0; return (x / y);

}

}

5. Функция обхода дерева (вывод постфиксной формы выражения).

void Postfix_Form (btree *p)

{

if (p == NULL) return;

Postfix_Form (p -> left);

Postfix_Form (p -> right);

printf ("%s ", p -> string);

}

Дата добавления: 2014-11-14; просмотров: 276; Нарушение авторских прав

Мы поможем в написании ваших работ!