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

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

Навигация