Бинарное дерево: различия между версиями
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. | |||
[ | [[Категория:Деревья]] | ||
Текущая версия от 15:03, 16 сентября 2018
Бинарное дерево(Binary tree) — 1. Ордерево, растущее из корня, причем из каждой вершины исходит не более двух дуг, помеченных как правая или левая дуга. Другими словами, возможны следующие комбинации: выходят правая и левая дуги, выходит одна правая дуга, выходит одна левая дуга, нет выходящих дуг. На уровне [math]\displaystyle{ h }[/math] бинарного дерева имеется максимум [math]\displaystyle{ 2^{h} }[/math] вершин. Поэтому бинарное дерево высотой [math]\displaystyle{ d }[/math] имеет максимум [math]\displaystyle{ (2^{d+1} - 1) }[/math] вершин, а дерево с [math]\displaystyle{ n }[/math] вершинами имеет минимальную высоту [math]\displaystyle{ \log_{2} n }[/math].
Другое название — Двоичное дерево. Иногда под бинарным деревом просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. [math]\displaystyle{ m }[/math]-Арное дерево.
2. Любая структура данных, используемая для представления бинарного дерева. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда бинарное дерево можно представить как указатель его корня.
Литература
- Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск.
- Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
- Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.
