53492

Построение таблицы по бинарному дереву поиска

Доклад

Информатика, кибернетика и программирование

Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку

Русский

2014-04-01

22.96 KB

1 чел.

Построение таблицы по бинарному дереву поиска

Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева. Узлы дерева могут быть пронумерованы по следующей схеме (см. рис. 9)

 

 Рис. 9 Схема нумерации узлов двоичного дерева

 

Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что, однако, не нарушает указанного порядка, так как их номера не используются. При такой системе нумерации в дереве каждый узел получает уникальный номер.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые правое и левое поддеревья.

Почти полное бинарное дерево определяется как бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

Пример: Построение таблицы по бинарному дереву поиска для массива

-5,41,8,16,31,3,15,-2,5,11

1

-5

0

2

0

2

41

3

0

1

3

8

6

4

2

4

16

7

5

3

5

31

0

0

4

6

3

8

9

3

7

15

10

0

4

8

-2

0

0

6

9

5

0

0

6

10

11

0

0

7


 

А также другие работы, которые могут Вас заинтересовать

73221. Екологічна безпека як складова національної безпеки Основні поняття та завдання, що вирішує дисципліна 105 KB
  Екологічна безпека як складова національної безпеки Основні поняття та завдання що вирішує дисципліна. Сутність обєкти субєкти екологічної безпеки Мета задачі та структура курсу його місце та значення у підготовці фахівців з екології. Становлення та розвиток екологічної безпеки. Критерії та ознаки екологічної безпеки.
73222. Оплата труда на предприятиях 1.43 MB
  Организация оплаты труда определяется 3мя взаимосвязанными факторами: 1 нормированием труда которое определяет основу для расчета ЗП 2 тарифной системой которая включает: тарифную ставку тарифную сетку и тарифный квалификационный справочник и определяет правильность оценки количества и качества труда 3 формами и системами оплаты труда устанавливающими порядок расчета ЗП по категориям сотрудников. До начала экономических реформ регулирование заработной платы в нашей стране осуществлялось в централизованном порядке: все тарифные...
73223. Себестоимость продукции 3.47 MB
  Себестоимость продукции является нижним пределом цены а также выполняет много других функций. Себестоимость транспортной продукции это текущие затраты предприятия на производство и реализацию продукции выраженные в денежной форме. Производственная себестоимость затраты связанные с производством продукции включая общепроизводственные и общехозяйственные расходы.
73224. Управление персоналом на предприятиях 804.02 KB
  Рабочие Служащие это категория работников в деятельности которых преобладают те или иные виды умственного труда. разрабатывают и внедряют в производство новые виды продукции технологические процессы технические и экономические нормативы формы и методы организации производства и труда; обеспечивают производство необходимой документацией материалами оснасткой ремонтным и другим обслуживанием; проводят анализ показателей деятельности предприятия разрабатывают и реализуют мероприятия по их улучшению. В формуле отражается одна из норм...
73225. Введение в экономику предприятий транспорта 1.3 MB
  Материальное производство включает: Промышленность; Сельское и лесное хозяйство; Грузовой транспорт; Связь обслуживающая материальное производство; Строительство; Торговля; Общественное питание; Информационно-вычислительное обслуживание и др. В процессе работы транспорта не создается новая продукция а осуществляется перемещение грузов пассажиров с одного пункта в другой. В процессе перевозок грузов с ними не происходят не физические не химические изменения а происходит лишь изменение их местонахождения по отношению к...
73226. Основные фонды предприятий транспорта 899.56 KB
  Классификация основных фондов предприятия По роли в производственном процессе: Активные: машины и оборудование силовые машины измерительные прибор вычислительная техника инструмент Пассивные: здания строения сооружения передаточные устройства транспорт пх инвентарь. Для производственных предприятий в том числе и предприятий транспорта типичный состав основных фондов следующий: Здания и строения административные здания производственные строения склады и т. Племенной скот Соотношение отдельных групп основных фондов в их общем...
73227. Оборотные средства предприятий 951.72 KB
  Фонды обращения это средства производства непосредственно обслуживающие стадию реализации продукции. подготовка новых видов производства арендная плата подписка К фондам обращения относятся средства обслуживающие процесс реализации продукции: Готовая продукция на складе Товары отгруженные заказчикам но еще не оплаченные ими товары в пути Средства в расчетах Денежные средства в кассе предприятия и на счетах в банках. Норматив оборотных средств то объем ресурсов в денежном выражении которые предназначены для формирования...
73228. Поняття й види джерел права. Джерела та форми права 30.56 KB
  Джерела та форми права. Поняття й види джерел права. Джерело форма права це способи зовнішнього вираження і закріплення норм права що виходять від держави і які мають загальнообовязкове значення.
73229. ДЕРЖАВНІ ТА НАЦІОНАЛЬНІ УКРАЇНСЬКІ СИМВОЛИ 88.5 KB
  Обладнання: карта України; зображення українського державного прапора та гербатризуба; малюнки із зображеннями калини віночка писанки рослинсимволів тощо; ватманський аркуш з кросвордом Україна; аудіоапаратура; свічка. Бучин ської Моя Україна. Приспів: Є на світі моя країна де червона цвіте калина Гори ріки і полонини це моя Україна. Є на світі одна країна найчарівніша як перлина В моїм серці вона єдина це моя Україна.