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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Бинарное дерево'''(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>.


[[Файл:Binary tree.jpg]]
[[Файл:Binary tree.png]]


Другое название --- [[Двоичное дерево|''Двоичное дерево'']].
Другое название --- [[Двоичное дерево|''Двоичное дерево'']].
Иногда под '''Б.д.''' просто
Иногда под '''бинарным деревом''' просто
понимается ордерево, из каждой вершины которого исходит не
понимается ордерево, из каждой вершины которого исходит не
более двух дуг. См.  [[m-Арное дерево|''<math>m</math>-Арное дерево'']].
более двух дуг. См.  [[m-Арное дерево|''<math>m</math>-Арное дерево'']].


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

Версия от 13:24, 7 июня 2010

Бинарное дерево(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. Любая структура данных, используемая для представления бинарного дерева. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда бинарное дерево можно представить как указатель его корня.

Литература

[Кнут],

[Евстигнеев/85],

[Евстигнеев-Касьянов/94],

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

[Словарь]