Концепция бинарного дерева
Бинарное дерево представляет собой конечный набор узлов N (n> = 0). Этот набор является либо пустым набором (пустое двоичное дерево), либо состоит из корневого узла и двух двоичных деревьев, которые не пересекают друг друга, называемые корневым узлом и правым поддереем соответственно.
Характеристики бинарных деревьев
Каждый узел имеет не более двух подтереев, поэтому нет узлов с границей, превышающей 2 в бинарном дереве. Каждый узел в двоичном дереве является объектом, и каждый узел данных имеет три указателя, а именно указатели на родителя, левого ребенка и правого ребенка. Каждый узел подключен друг к другу через указатель. Отношения между связанными указателями-все отношения отца и ина.
Определение бинарных деревьев
Бинарный узел дерева определяется следующим образом:
Кода -копия выглядит следующим образом:
структура BinaryTreeNode
{
int m_nvalue;
BinaryTreeNode* m_pleft;
BinaryTreeNode* m_pright;
};
Пять основных форм бинарных деревьев
Пустое двоичное дерево
Есть только один корневой узел
Корневой узел имеет только левый поддерек
Корневой узел имеет только правильный поддерек
Корневой узел имеет как левый, так и правый поддерек
Есть только два случая для обычных деревьев с тремя узлами: два или три. Однако, поскольку бинарное дерево должно различать левое и правое, оно будет развиваться в следующие пять форм:
Специальное бинарное дерево
Наклонное дерево
Как показано во втором и третьем маленьком изображениях в предпоследней подзадне-картинке выше.
Полное двоичное дерево
В двоичном дереве, если у всех ветвей есть левые и правые подделы, и все листья находятся на одном слое, такое двоичное дерево называется полным бинарным деревом. Как показано на рисунке ниже:
Полное двоичное дерево
Полностью двоичное дерево означает, что последний слой полон слева, правая сторона может быть полна или нет, а остальные слои полны. Бинарное дерево с глубиной K и несколькими узлами 2^K - 1 представляет собой полное двоичное дерево (полное двоичное дерево). Это дерево с глубиной К и без места.
Характеристики полностью двоичного дерева:
Листовые узлы могут появляться только в двух самых низких слоях.
Самый низкий лист должен быть сконцентрирован в непрерывном положении слева.
В предпоследнем слое, если есть листовые узлы, они должны находиться в непрерывных положениях справа.
Если степень узла составляет 1, то узел имеет только левый ребенок.
Для бинарных деревьев с тем же деревом узлов полное двоичное дерево имеет наименьшую глубину.
Примечание. Полное двоичное дерево должно быть полностью бинарным деревом, но полностью двоичное дерево может быть не полным бинарным деревом.
Алгоритм выглядит следующим образом:
Кода -копия выглядит следующим образом:
bool is_complete (дерево *корень)
{
очередь Q;
Дерево *PTR;
// Выполните приоритет приоритета (иерархический обход) и также положите нулевые узлы в очередь
Q.push (root);
while ((ptr = q.pop ())! = null)
{
Q.push (ptr-> слева);
Q.push (ptr-> right);
}
// Определите, есть ли еще узлы, которые не были доступны
While (! Q.is_empty ())
{
ptr = q.pop ();
// Если есть не нулевые узлы, которые не доступны, дерево имеет пустоту и является неполным бинарным деревом.
if (null! = ptr)
{
вернуть ложь;
}
}
вернуть истину;
}
Свойства бинарных деревьев
Свойство 1 бинарного дерева: на уровне бинарного дерева есть не более 2^(i-1) узлов (i> = 1)
Свойство 2 двоичного дерева: двоичное дерево с глубиной k имеет не более 2 узлов k-1 (k> = 1)
Последовательная структура хранения двоичных деревьев
Последовательная структура хранения двоичного дерева состоит в том, чтобы использовать одномерный массив для хранения каждого узла в двоичном дереве, а местоположение узлов может отражать логическую связь между узлами.
Бинарный список ссылок
Поскольку метод последовательного хранения не очень применим, мы должны рассмотреть структуру хранения цепи. Согласно международной практике, хранилище бинарных деревьев обычно принимает структуру хранения цепи.
Каждый узел двоичного дерева имеет не более двух детей, поэтому это естественная идея разработать поле данных и два поля указателя для него. Мы называем такой связанный список двунарно связанным списком.
Прохождение бинарных деревьев
Перенос бинарного дерева относится к доступу ко всем узлам в бинарном дереве в определенном порядке из корневого узла, так что каждый узел доступ к одному узел один раз и только один раз.
Есть три способа пересечения бинарных деревьев следующим образом:
(1) Переоборудование предварительного заказа (DLR), сначала доступ к корневому узлу, затем пересекает левый поддерек и, наконец, пересекает правый поддерек. Сокращенный корень - слева - справа.
(2) Тонверс в порядке (LDR), сначала пересекайте левый поддерек, затем получите доступ к корневому узлу и, наконец, пройдите правый поддерек. Сокращенная примечание: лево-правом.
(3) Пост-заказ обход (LRD), сначала пересекающий левый поддерек, затем пройдя правый поддерев и, наконец, доступ к корневому узлу. Сокращенный левый правый корень.
Преамбула
Если двоичное дерево пустое, пустая операция возвращается. В противном случае, сначала обратитесь к корневому узлу, затем пройдите левый поддерек в предыдущем порядке, а затем пройдите правый поддерево в предыдущем порядке.
Порядок обхода: abdhiejcfkg
Кода -копия выглядит следующим образом:
// Точный обход
предварительный заказ функции (узел) {
if (! node == null) {
putstr (node.show ()+ "");
предварительный заказ (node.left);
предварительный заказ (node.right);
}
}
Обычный обход:
Если дерево является пустым, пустая операция возвращается, в противном случае оно начинается с корневого узла (обратите внимание, что корневой узел не доступен сначала), а левый поддерек корневого узла пересекается в среднем порядке, затем доступ к корневому узлу доступен, и, наконец, правый поддерек пересекается в среднем порядке.
Порядок обхода: hdibejafkcg
Кода -копия выглядит следующим образом:
// Использование рекурсивного метода для реализации обхода среднего порядка
функция inorder (node) {
if (! (node == null)) {
inorder (node.left); // сначала добавить в левый поддерек
putstr (node.show ()+ ""); // снова добавить в корневой узел
inorder (node.right); // Последний доступ к правой поддерево
}
}
Пост-заказ обход:
Если дерево пустое, пустая операция возвращается. В противном случае левые и правые подтерей пересекаются слева направо, чтобы получить доступ к левой и правой подтережам, и, наконец, получить доступ к корневому узлу.
Порядок обхода: hidjebkfgca
Кода -копия выглядит следующим образом:
// пост-заказ
Функция послепорядка (узел) {
if (! node == null) {
Postorder (node.left);
Postorder (node.right);
putstr (node.show ()+ "");
}
}
Реализовать дерево бинарного поиска
Дерево бинарного поиска (BST) состоит из узлов, поэтому мы определяем объект узла узла следующим образом:
Кода -копия выглядит следующим образом:
Функциональный узел (данные, слева, справа) {
this.data = data;
this.left = left; // Сохранить ссылку левого узла
this.right = верно;
this.show = show;
}
функция show () {
вернуть это.data; // Показать данные, сохраненные в узле
}
Найдите максимальные и минимальные значения
Поиск минимальных и максимальных значений на BST очень прост, потому что меньшие значения всегда находятся на левом детском узле и ищут минимальное значение на BST, просто пройдите левое детское дерево, пока не будет найден последний узел
Найти минимальное значение
Кода -копия выглядит следующим образом:
функция getMin () {
var current = this.root;
while (! (current.left == null)) {
current = current.left;
}
вернуть current.data;
}
Этот метод пересекает один за другим вдоль левого поддерева BST, пока он не пройдет до самого левого узла BST, который определяется как:
Кода -копия выглядит следующим образом:
current.left = null;
В настоящее время значение, сохраненное в текущем узле, является минимальным значением
Найти максимальное значение
Поиск максимального значения на BST требует прохождения правого поддерека до тех пор, пока не будет найден последний узел, а значение, сохраненное на этом узле, является максимальным значением.
Кода -копия выглядит следующим образом:
функция getMax () {
var current = this.root;
while (! (current.right == null)) {
ток = current.right;
}
вернуть current.data;
}