683
правки
Бинарное дерево: различия между версиями
Материал из WikiGrapp
→Литература
KEV (обсуждение | вклад) (Создана новая страница размером '''Бинарное дерево'''(Binary tree) - 1. Ордерево, растущее из [[ко...) |
KVN (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Бинарное дерево'''([[ | '''Бинарное дерево'''(''[[Binary tree]]'') — 1. [[Ордерево]], растущее из | ||
[[корень|корня]], причем из каждой [[вершина|вершины]] исходит | [[корень|корня]], причем из каждой [[вершина|вершины]] исходит | ||
не более двух [[дуга|дуг]], | не более двух [[дуга|дуг]], | ||
| Строка 6: | Строка 6: | ||
и левая дуги, выходит одна правая дуга, выходит одна левая | и левая дуги, выходит одна правая дуга, выходит одна левая | ||
дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется | дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется | ||
максимум <math>2^{h}</math>вершин. Поэтому ''' | максимум <math>2^{h}</math> вершин. Поэтому '''бинарное дерево''' [[высота дерева|высотой]] <math>d</math> имеет максимум | ||
<math>(2^{d+1} - 1)</math> вершин, а дерево с <math>n</math> вершинами имеет минимальную | <math>(2^{d+1} - 1)</math> вершин, а дерево с <math>n</math> вершинами имеет минимальную | ||
высоту <math>\log_{2} n</math>. | высоту <math>\log_{2} n</math>. | ||
[[Файл:Binary tree. | [[Файл:Binary tree.png|350px]] | ||
Другое название | Другое название — ''[[Двоичное дерево]]''. | ||
Иногда под ''' | Иногда под '''бинарным деревом''' просто | ||
понимается ордерево, из каждой вершины которого исходит не | понимается ордерево, из каждой вершины которого исходит не | ||
более двух дуг. См. [[m-Арное дерево|''<math>m</math>-Арное дерево'']]. | более двух дуг. См. [[m-Арное дерево|''<math>m</math>-Арное дерево'']]. | ||
2. Любая структура данных, используемая для представления ''' | 2. Любая структура данных, используемая для представления '''бинарного дерева'''. | ||
Каждая вершина в ней должна быть представлена указателями на левое и | Каждая вершина в ней должна быть представлена указателями на левое и | ||
правое поддеревья, а также на значение данных, связанное с этой | правое поддеревья, а также на значение данных, связанное с этой | ||
вершиной. Тогда ''' | вершиной. Тогда '''бинарное дерево''' можно представить как указатель его | ||
корня. | корня. | ||
==Литература== | ==Литература== | ||
* Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск. | |||
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991. | |||
[ | [[Категория:Деревья]] | ||
