пользователей: 21209
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

I семестр:
» прг

Деревья

Дерево - связный граф без циклов, удовлетворяющий следующим условиям:

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

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

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

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

Пример размеченного бинарного дерева привед на рисунке ниже.

При работе с бинарным деревом его удобно рассматривать как рекурсивную структуру, состоящую из трех элементов:

           дерево = 
   вершина (элемент базисного типа) 
  дерево левое  
  дерево правое 

Поэтому многие алгоритмы для работы с деревом может быть представлены в рекурсивном виде, т.е. компактны и просты для понимания. Бинарное дерево не обязано содержать числовую информацию в качестве своей вершины. Информационная составляющая вершины может быть любого типа. Единственным условием является возможность применения операции сравнения '<' или '>' к вершинам дерева. Некоторые существенно упрощаются при наличии еще одного элемента в структуре дерева - родительской вершины. Единственная вершина дерева - корневая - не имеет родителя. Приведем некоторые из алгоритмов обработки дерева. Будем считать, что вершинам приписаны целые значения, а тип дерева задан структурой следующего вида

struct  tree		
фсо int  top ;             // значение вершины
 tree  * left   ;       // указатель на левой поддерево
 tree  * right  ;       // указатель на правое поддерево
 tree  * parent ;       // указатель на родительскую вершину
 tree(k)фсо top = k;
          left = right = parent = NULL; 
        фсз		// функция - конструктор, инициализирует поле top
 фсз;               	// заданным значением k, а указатели - значением NULL. 

Как отмечалось ранее, структуры могут иметь члены-функции, определяющие операции, которые могут выполняться над структурой. В данном случае использована одна специализированная функция - конструктор. Назначение консруктора - инициализация членов-данных структуры. Следует обратить внимание, что 
 -   имя конструктора совпадает с именем структуры, 
 - синтаксис объявления констуктора не содержит типа возвращаемого результата, так как имя конструктора уже задает тип  ( struct определяет пользовательский тип данных). 
 -  вызов любых членов-функций, в том числе и конструкторов, выполняется аналогично обращению к членам-данным,  то есть с использованием операций  '->'   и   '.'  .


20.08.2015; 01:16
хиты: 41
рейтинг:0
Гуманитарные науки
изобразительные искусства
каллиграфия
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь