Бинарное дерево

Материал из WikiGrapp
Перейти к:навигация, поиск

Бинарное дерево(Binary tree) — 1. Ордерево, растущее из корня, причем из каждой вершины исходит не более двух дуг, помеченных как правая или левая дуга. Другими словами, возможны следующие комбинации: выходят правая и левая дуги, выходит одна правая дуга, выходит одна левая дуга, нет выходящих дуг. На уровне h бинарного дерева имеется максимум 2^{h} вершин. Поэтому бинарное дерево высотой d имеет максимум (2^{d+1} - 1) вершин, а дерево с n вершинами имеет минимальную высоту \log_{2} n.

Binary tree.png

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

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

Литература

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