Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
О СНОВНЫЕ ОПЕРАЦИИ С БИНАРНЫМИ ДЕРЕВЬЯМИ
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
- Bu sahifa navigatsiya:
- Листинг 4.1. Класс узла
- Листинг 4.2. Класс дерева
|
4.2. О
СНОВНЫЕ ОПЕРАЦИИ С БИНАРНЫМИ ДЕРЕВЬЯМИ Дерево является динамической структурой данных. В процессе выпол- нения программы деревья создаются и модифицируются путем добавления и удаления узлов, а также изменения их информационной части. Поэтому узел дерева определяется как структура, содержащая информационную часть и два поля-ссылки, связанные с левым и правым поддеревьями данного узла. При отсутствии соответствующих поддеревьев эти поля получают значение null . В листинге 4.1 приведено описание класса узла дерева с включением дополнительных полей, которые необходимы для графического представле- ния дерева на форме. Листинг 4.1. Класс узла public class Node// узел { public object data;// значение ключа public Node left; // ссылка на левое поддерево public Node right; // ссылка на правое поддерево public int x; public int y; public bool visit; // признак выделенности узла public int count; // счетчик повторений значений public Node(Node left, Node right, object data, // конструктор int x, int y) } На основе этого класса можно создать класс дерева (листинг 4.2). Все методы этого класса – рекурсивны. Листинг 4.2. Класс дерева class MyTree { Node top; // вершина дерева 7 / 23 77 public Node SelectNode; // выделенный узел public Bitmap bitmap; // канва для рисования public class Node // класс узла const int step = 30; const int Geom = 1; Graphics g; Pen MyPen; SolidBrush MyBrush; Font MyFont; public void Search(int val) // поиск и вставка public Node FindNode(int x, int y) // поиск по координатам Node FindNodeVal(int val) // поиск по значению public void Insert(object data, int x,int y) // вставка void DeSelect() // снятие признака посещения public void Delta(Node p, int dx, int dy) // смещение поддерева public void Delete(Node p) // удаление узла public void Draw() // изображение де- рева } Динамический способ представления дерева – не единственно возмож- ный: дерево можно также представить с помощью массива. Элементы масси- ва будут содержать значения узлов дерева, а с помощью индексов можно ус- тановить структуру дерева. Так, в первом элементе i=1 хранится значение корня. Элемент с i=2 хранит значение левого сына корня, элемент с i=3 хра- нит значение правого сына корня. И так для любого элемента с индексом i индекс его левого сына равен 2×i, а правого — 2×i+1. Индекс отца будет равен i/2. Однако так можно хранить деревья со строго определенной структу- рой. Ниже будет рассмотрен пример сортировки частично упорядоченным де- ревом, представленным массивом. Для деревьев произвольной формы в массив приходится заносить специальные значения, соответствующие null, если у какого-то узла отсутствует тот или иной сын, или для каждого узла хранить 8 / 23 78 индексы его сыновей. Так, в таблице 4.1 приведен массив, хранящий дерево, представленное на рисунке 4.1. Верхняя строка содержит индексы массива, вторая строка — значения ключей, а третья и четвертая строки — индексы ле- вого и правого сыновей. Значение 0 соответствует отсутствию сына. Таблица 4.1 Дерево, представленное с помощью массива Download 1.85 Mb. Do'stlaringiz bilan baham: 
|