В общее меню Введение Основные инструкции Структурированные типы данных Подпрограммы Рекурсия Классы Динамические структуры данных Сортировка |
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями. В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево. Двоичное дерево поиска может быть либо пустым, либо оно обладает
таким свойством, что корневой элемент имеет большее значение узла, чем любой
элемент в левом поддереве, и меньшее или равное, чем элементы в правом
поддереве. Указанное свойство называется характеристическим свойством
двоичного дерева поиска и выполняется для любого узла такого дерева,
включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое
название двоичные деревья поиска получили по той причине, что скорость поиска в
них примерно такая же, что и в отсортированных массивах:
Пример. Для набора данных 9, 44, 0, –7, 10, 6, –12, 45 построить двоичное дерево поиска. Согласно определению двоичного дерева поиска число 9 помещаем в корень, все значения, меньшие его — на левое поддерево, большие или равные — на правое. В каждом поддереве очередной элемент можно рассматривать как корень и действовать по тому же алгоритму. В итоге получаем Выделим типовые операции над двоичными деревьями поиска:
Поскольку определение двоичного дерева рекурсивно, то все указанные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике именно такой вариант чаще всего и применяется). Отметим лишь, что использование рекурсии замедляет работу программы и расходует лишнюю память при её выполнении. Пусть двоичное дерево поиска описывается следующим типом struct BinTree{ BT inf; BinTree *L; BinTree *R; }; Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный. Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемых из них называются обход в прямом (префиксном) порядке, обход в обратном (постфиксном) порядке и обход во внутреннем порядке (или симметричный обход). Каждый из обходов реализуется с использованием рекурсии. Ниже приведены подпрограммы печати элементов дерева с использованием обхода двоичного дерева поиска в обратном порядке. void PrintTree(BinTree *T) { if (T) {PrintTree(T->L); cout << T->inf<< " "; PrintTree(T->R);} } Реализуем функцию, возвращающую 1, если элемент присутствует в дереве, и 0 — в противном случае. int Find(BinTree *Tree, BT x) { if (!Tree) return 0; else if (Tree->inf==x) return 1; else if (x < Tree->inf) return Find(Tree->L, x); else return Find(Tree->R, x); } По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным): 1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла); 2) узел, содержащий элемент x, имеет степень 2. Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0). Намного сложнее, если удаляемый узел имеет два поддерева. В этом случае нужно заменить удаляемый элемент самым правым элементом из его левого поддерева. Примечание. Если элемент повторяется в дереве несколько раз, то удаляется только первое его вхождение.
|
© Шестаков А.П., 2000-2007