Информатика и технология программирования
если вершина дерева имеет индекс
Так, если вершина дерева имеет индекс n в массиве, то вершины левого и правого поддерева - 2*n и 2*n+1 соответственно. Головная вершина дерева имеет индекс, равный 1 . Кроме того, в таком массиве необходимо как-то обозначать пустые вершины (аналог указателя NULL).
Поиск в двоичном дереве требует количества сравнений, не превышающего максимальной длины ветви дерева, или максимальной длины цепочки его вершин. Следовательно, условием эффективности поиска в дереве является равенство длин его ветвей (сбалансированность). В самом крайнем случае дерево имеет одну ветвь и вырождается в односвязный список, в котором имеет место последовательный поиск. В идеальном случае, когда длины ветвей дерева отличаются не более, чем на 1 (сбалансированное дерево) и равны n или n-1 , при общем количестве вершин в дереве порядка " 2 в степени n " требуется не более n сравнений для нахождения требуемой вершины. Это соответствует характеристикам алгоритма двоичного поиска в упорядоченном массиве.
Таким образом, необходимым условием эффективного использования двоичного дерева для быстрого поиска является его сбалансированность. Поддержание сбалансированности при операциях включения и исключения является довольно трудной задачей.
Двоичное дерево может использоваться также для сортировки последовательности данных. Если производить включение в двоичное дерево последовательности элементов в порядке их поступления, то затем обычный рекурсивный обход этого дерева даст их упорядоченную последовательность:
//------------------------------------------------------bk55-07.cpp
// Рекурсивный обход двоичного дерева с выводом
// значений вершин в порядке возрастания
void Scan(btree *p)
{
if (p==NULL) return;
Scan(p->left);
cout << p->val << endl;
Scan(p->right);
}
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий