Бинарное дерево: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
'''Бинарное дерево'''([[Binary tree|Binary tree]]) - 1. [[Ордерево|Ордерево]], растущее из
'''Бинарное дерево'''(''[[Binary tree]]'') 1. [[Ордерево]], растущее из
[[корень|корня]], причем из каждой [[вершина|вершины]] исходит
[[корень|корня]], причем из каждой [[вершина|вершины]] исходит
не более двух [[дуга|дуг]],
не более двух [[дуга|дуг]],
Строка 6: Строка 6:
и левая дуги, выходит одна правая дуга, выходит одна левая
и левая дуги, выходит одна правая дуга, выходит одна левая
дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется
дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется
максимум <math>2^{h}</math>вершин. Поэтому '''бинарное дерево''' [[высота дерева|высотой]] <math>d</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>.
Строка 12: Строка 12:
[[Файл:Binary tree.png|350px]]
[[Файл:Binary tree.png|350px]]


Другое название --- [[Двоичное дерево|''Двоичное дерево'']].
Другое название — ''[[Двоичное дерево]]''.
Иногда под '''бинарным деревом''' просто
Иногда под '''бинарным деревом''' просто
понимается ордерево, из каждой вершины которого исходит не
понимается ордерево, из каждой вершины которого исходит не
Строка 23: Строка 23:
корня.
корня.
==Литература==
==Литература==
[Кнут],  
* Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск.
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев/85],
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
   
   
[Евстигнеев-Касьянов/94],
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.


[Касьянов-Поттосин], 


[Словарь]
[[Категория:Деревья]]

Текущая версия от 12:13, 24 октября 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].

Binary tree.png

Другое название — Двоичное дерево. Иногда под бинарным деревом просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. [math]\displaystyle{ m }[/math]-Арное дерево.

2. Любая структура данных, используемая для представления бинарного дерева. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда бинарное дерево можно представить как указатель его корня.

Литература

  • Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск.
  • Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
  • Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.