- Двоичное дерево
- Типы двоичных деревьев
- Полное двоичное дерево
- Совершенное двоичное дерево
- Законченное двоичное дерево
- Вырожденное двоичное дерево
- Скошенное вырожденное дерево
- Сбалансированное двоичное дерево
- Представление двоичного дерева
- Примеры реализации
- Python
- Java
- Си
- С++
- Где используется
- Кодирование деревьев
- 3.10. Кодирование деревьев
Двоичное дерево
Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.
Типы двоичных деревьев
Полное двоичное дерево
Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.
Совершенное двоичное дерево
Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.
Законченное двоичное дерево
Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.
- Все уровни должны быть заполнены.
- Все листовые вершины склоняются влево.
- У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.
Вырожденное двоичное дерево
Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.
Скошенное вырожденное дерево
Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.
Сбалансированное двоичное дерево
Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.
Представление двоичного дерева
Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.
Примеры реализации
Python
# Двоичное дерево в Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Прямой обход дерева def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Центрированный обход дерева def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Обратный обход дерева def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Прямой обход дерева: ", end="") root.traversePreOrder() print("\nЦентрированный обход дерева: ", end="") root.traverseInOrder() print("\nОбратный обход дерева: ", end="") root.traversePostOrder()
Java
// Двоичное дерево на Java // Создание узла class Node < int key; Node left, right; public Node(int item) < key = item; left = right = null; >> class BinaryTree < Node root; BinaryTree(int key) < root = new Node(key); >BinaryTree() < root = null; >// Центрированный обход дерева public void traverseInOrder(Node node) < if (node != null) < traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); >> // Обратный обход дерева public void traversePostOrder(Node node) < if (node != null) < traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); >> // Прямой обход дерева public void traversePreOrder(Node node) < if (node != null) < System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); >> public static void main(String[] args) < BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Прямой обход дерева: "); tree.traversePreOrder(tree.root); System.out.print("\nЦентрированный обход дерева: "); tree.traverseInOrder(tree.root); System.out.print("\nОбратный обход дерева: "); tree.traversePostOrder(tree.root); >>
Си
// Обход дерева на Си #include #include struct node < int item; struct node* left; struct node* right; >; // Центрированный обход дерева void inorderTraversal(struct node* root) < if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); > // Прямой обход дерева void preorderTraversal(struct node* root) < if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); > // Обратный обход дерева void postorderTraversal(struct node* root) < if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); > // Создание нового узла struct node* createNode(value) < struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; > // Вставка потомка слева от родительской вершины struct node* insertLeft(struct node* root, int value) < root->left = createNode(value); return root->left; > // Вставка потомка справа от родительской вершины struct node* insertRight(struct node* root, int value) < root->right = createNode(value); return root->right; > int main() < struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Центрированный обход дерева\n"); inorderTraversal(root); printf("\nПрямой обход дерева\n"); preorderTraversal(root); printf("\nОбратный обход дерева\n"); postorderTraversal(root); >
С++
// Двоичное дерево на С++ #include #include using namespace std; struct node < int data; struct node *left; struct node *right; >; // Создание нового узла struct node *newNode(int data) < struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); > // Прямой обход дерева void traversePreOrder(struct node *temp) < if (temp != NULL) < cout data; traversePreOrder(temp->left); traversePreOrder(temp->right); > > // Центрированный обход дерева void traverseInOrder(struct node *temp) < if (temp != NULL) < traverseInOrder(temp->left); cout data; traverseInOrder(temp->right); > > // Обратный обход дерева void traversePostOrder(struct node *temp) < if (temp != NULL) < traversePostOrder(temp->left); traversePostOrder(temp->right); cout data; > > int main() < struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout
Где используется
- Для быстрого доступа к данным.
- В алгоритмах маршрутизации.
- Для реализации куч.
- В синтаксических деревьях.
Источник
Кодирование деревьев
Выделим в дереве какую-нибудь одну вершину, которую назовем корнем. Полученное дерево с выделенной вершиной называется корневым.
Для задания (с точностью до изоморфизма) корневых деревьев используют код из 0 и 1, который мы определим индуктивно.
Определение. Кодом корневого дерева с одним ребром является . Пусть деревья и с корнями a и b соответственно (см. рис.) имеют коды и . Тогда кодом дерева с корнем с является код , а кодом дерева с корнем — код .
Пример 1. Написать код дерева, изображенного на рисунке.
Справедливо следующее утверждение: для того, чтобы последовательность нулей и единиц являлась кодом некоторого дерева необходимо и достаточно, чтобы число нулей и единиц в этой последовательности было одинаковым, причем в любом начальном отрезке последовательности количество нулей было не меньше количества единиц.
Чтобы построить корневое дерево по коду из нулей и единиц, нужно разбить последовательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем. Если образованные таким образом пары пометить снизу кода фигурными скобками, то каждая такая скобка будет соответствовать ребру графа.
Пример 2. Построить дерево по коду .
Для задания помеченных деревьев, т.е. деревьев, вершины которых занумерованы, используют код из натуральных чисел.
Пусть дано помеченное дерево. Чтобы построить его код из натуральных чисел действуем следующим образом. Находим висячую вершину с наименьшим номером. Записываем номер смежной с ней вершины (это начало кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Для полученного в результате данной операции дерева находим висячую вершину с наименьшим номером, записываем номер смежной с ней вершины (это продолжение кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Так поступаем до тех пор, пока не останется последнее ребро.
Заметим, что длина кода из натуральных чисел на единицу меньше числа ребер и на две единицы меньше числа вершин данного дерева.
Пример 3. На рисунке изображено помеченное дерево. Его код .
Построение дерева по коду из натуральных чисел рассмотрим на примере кода . Прежде всего, заметим, что дерево, которое нам предстоит построить, имеет 8 вершин.
Будем преобразовывать последовательность 224466, действуя по следующей схеме. Вместо первого числа запишем наименьшее натуральное число, которое в этой последовательности не встречается, т.е. 1; получим последовательность 124466. Вместо второго числа в новой последовательности запишем наименьшее, не встречающееся в ней, т.е. 3; получим последовательность 134466, и т.д. Действуем так до тех пор, пока все числа в исходной последовательности не будут заменены. Расположим все последовательности друг под другом; под последней из них запишем код дерева. Выпишем пары вершин, записанные друг под другом в последних двух строчках: (12), (32), (24), (54), (46), (76). Каждая такая пара — это пара концов одного из ребер дерева. Этот список дополняем парой вершин, отсутствующих в предпоследней строчке, т.е. парой (6,8). Теперь строим дерево: отмечаем на плоскости точки – вершины дерева и соединяем их ребрами согласно списку (см. рисунок к примеру 3).
3.11. Остовы графа. Построение минимального остова
Напомним, что подграф графа , называется остовным подграфом, если .
Определение. Остовом обыкновенного графа называется его остовный подграф, являющийся деревом.
Пусть — обыкновенный граф. Упорядочим множество его вершин . Определим матрицу Кирхгофа графа , полагая:
где — матрица смежности графа, отвечающая данному упорядочению вершин.
Можно показать, что матрицы Кирхгофа обладают следующим свойством: алгебраические дополнения всех элементов любой из матриц Кирхгофа графа равны между собой.
Утверждение. Число остовов в связном неодноэлементном обыкновенном графе равно алгебраическому дополнению любого элемента его матрицы Кирхгофа.
Доказательство этого утверждения опустим.
Определение. Взвешенным графом будем называть совокупность объектов ,где тройка — граф и — отображение, называемое весовым.
Число называется весом ребра , число — весом графа .
Определение. Остов связноговзвешенного графа назовем минимальным остовом, если для любого остова выполнено неравенство .
Рассмотрим задачу о нахождении минимального остова в связном взвешенном графе.
Теорема (алгоритм Краскала). Пусть — связный взвешенный граф. — последовательность его остовных подграфов, заданная индуктивно следующим образом:
1. остовный подграф, множество ребер которого пусто.
2. Пусть — остовный подграф с множеством ребер . Тогда — остовный подграф с множеством ребер , где ребро выбирается из множества так, что выполнены два условия: а) добавление ребра не приводит к образованию циклов; б) из ребер, удовлетворяющих условию а), ребро обладает наименьшим весом.
Тогда последним элементом последовательности является минимальный остов графа .
Доказательство теоремы опустим.
Замечания. 1. Если граф несвязен, то по алгоритму Краскала строится остовный лес.
2. Если граф невзвешен, то, присваивая всем ребрам одинаковые веса, мы можем применить алгоритм Краскала для построения остова (остовного леса).
Пример 1. Построить остов минимального веса графа с множеством вершин ; множеством ребер ; отображением инцидентности , , , , , , , , и весовым отображением , , , , , , , .
Согласно алгоритму Краскала строим последовательность остовных подграфов:
с пустым множеством ребер;
Добавление к графу любого из оставшихся ребер графа ведет к образованию цикла. Таким образом, подграф c множеством ребер , — минимальный остов, вес которого равен .
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник
3.10. Кодирование деревьев
Выделим в дереве какую-нибудь одну вершину, которую назовем корнем. Полученное дерево с выделенной вершиной называетсякорневым.
Для задания (с точностью до изоморфизма) корневыхдеревьев используюткод из 0 и 1, который мы определим индуктивно.
Определение.Кодом корневого дерева с одним ребром является
.Пусть деревья
и
с корнямиa и b соответственно (см. рис.) имеют коды
и
.Тогда кодом дерева
с корнем с является код
, а кодом дерева
с корнем
— код
.
Пример 1. Написать код дерева, изображенного на рисунке.
Итак, код дерева —
.
Справедливо следующее утверждение:для того, чтобы последовательность нулей и единиц являлась кодом некоторого дерева необходимо и достаточно, чтобы число нулей и единиц в этой последовательности было одинаковым, причем в любом начальном отрезке последовательности количество нулей было не меньше количества единиц.
Чтобы построить корневое дерево по кодуиз нулей и единиц, нужно разбить последовательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем. Если образованные таким образом пары пометить снизу кода фигурными скобками, то каждая такая скобка будет соответствовать ребру графа.
Пример 2.Построить дерево по коду
.
Для задания помеченныхдеревьев, т.е. деревьев, вершины которых занумерованы, используют код из натуральных чисел.
Пусть дано помеченное дерево. Чтобы построить его код из натуральных чисел действуем следующим образом. Находим висячую вершину с наименьшим номером. Записываем номер смежной с ней вершины (это начало кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Для полученного в результате данной операции дерева находим висячую вершину с наименьшим номером, записываем номер смежной с ней вершины (это продолжение кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Так поступаем до тех пор, пока не останется последнее ребро.
Заметим, что длина кода из натуральных чисел на единицу меньше числа ребер и на две единицы меньше числа вершин данного дерева.
Пример 3.На рисунке изображено помеченное дерево. Его код
.
Построение дерева по коду из натуральных чиселрассмотрим на примере кода. Прежде всего, заметим, что дерево, которое нам предстоит построить, имеет 8 вершин.
Источник