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


 

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

83620. Расчет искусственного освещения методом коэффициента использования 43.18 KB
  1 где Е заданная минимальная освещенность лк; Кзап коэффициент запаса; коэффициент минимальной освещенности приближенно можно принимать z = 11 для люминесцентных ламп z = 115 для ламп накаливания и ДРЛ; S освещаемая площадь м2; Еср средняя освещенность лк; N число светильников намечается до расчета коэффициент использования светового потока источника света доли единиц. Если такое приближение не реализуется то корректируется число светильников. Если световой поток ламп в каждом светильнике составляет...
83621. Точечный метод расчета освещенности 93.26 KB
  Расположение контрольной точки А при размещении светильников по углам квадрата и В по сторонам прямоугольника 3 по пространственным изолюксам горизонтальной освещенности находится освещенность е от каждого светильника; 4 находится общая условная освещенность от всех светильников ∑е; 5 рассчитывается горизонтальная освещенность от всех светильников в точке А: Еа = F х μ 1000х kз х ∑е где μ коэффициент учитывающий дополнительную освещенность от удаленных светильников и отраженного светового потока kз коэффициент запаса. Порядок по...
83622. Порядок расчета рабочего освещения любого цеха 73.69 KB
  Наметим число светильников в ряду: шт. тогда расстояние от торцевых стен до крайнего светильника составит: Расстояние от крайних светильников до стены принимается 03L 05L в зависимости от наличия рабочих мест у стен. Выберем расстояние между рядами LB при этом необходимо учесть следующее условие: Примем LB = 4м; Расстояние от боковых стен до крайних светильников составит: 5. Число светильников в цехе: Размещение светильников представлено на рис.
83623. Расчет аварийного освещения 28.4 KB
  Оно должно быть достаточным для безопасного выхода людей из помещения и продолжения работы в помещениях и на открытых пространствах в тех случаях когда отключение рабочего освещения может вызвать пожар взрыв отравление газами парами длительное расстройство технологического процесса нарушение работы важнейших объектов водоснабжение электростанции узлы радиопередачи и т. Для аварийного освещения разрешается применять как лампы накаливания так и люминесцентные лампы последние при минимальной температуре воздуха не менее 10 С.75...
83624. Расчёт осветительной сети 34.54 KB
  Освещение безопасности предназначено для продолжения работы при аварийном отключении рабочего освещения. Светильники рабочего освещения и светильники освещения безопасности должны питаться от независимых источников. Устройство рабочего освещения обязательно во всех помещениях независимо от устройства в них других видов освещения. Светильники аварийного освещения рекомендуется по возможности выделять из числа светильников рабочего освещения.
83625. Картограмма нагрузок. Определение условного центра электрических нагрузок 56.37 KB
  Определение условного центра электрических нагрузок. Картограмма нагрузок. Для определения места положения ГПП ТП при проектировании системы электроснабжения на генеральный план промышленного предприятия наносится картограмма нагрузок которая представляет собой размещённые на генеральном плане окружности причём площади ограниченные этими окружностями в выбранном масштабе равны расчётным нагрузкам цехов.
83626. МОЛНИЕЗАЩИТА ПОДСТАНЦИЙ 32.29 KB
  Молниезащита Iкатегории Защита от прямых ударов молнии зданий и сооружений относимых по устройству молниезащиты к I категории должна выполняться отдельно стоящими стержневыми или тросовыми молниеотводами. Защита от прямых ударов молнии зданий и сооружений II категории с неметаллической кровлей должна быть выполнена отдельно стоящими или установленными на защищаемом объекте стержневыми или тросовыми молниеотводами обеспечивающими зону защиты в соответствии с требованиями табл. Установка молниеприемников или наложение молниеприемной сетки не...
83627. Условия и требования норм проектирования по выбору трансформаторов тока (встроенные или отдельно стоящие, 10% погрешность, чувствительность продольной дифференциальной защиты) 39.83 KB
  Трансформаторы тока предназначены для понижения первичного тока до стандартной величины и для отделения цепей измерения и защиты от первичных цепей высокого напряжения. Основные номинальные параметры трансформаторов тока: Номинальное напряжение линейное Uном кВ Номинальный первичный ток I1ном А Номинальный вторичный ток I2ном А 1 или 5 Номинальная вторичная нагрузка с коэффициентом мощности cosφ2=0.8 ВА Номинальный класс точности для измерений Номинальный класс точности для защиты Коэффициент трансформации...
83628. Требования нормами технологического проектирования и САНПИНом к городским подстанциям и электрическим сетям 32.97 KB
  Нормами технологического проектирования к городским ПС и электрическим сетям рассматриваются и регламентируются следующие разделы: 1 Общие положения общие указания обьем и состав проектной документации 2 Расчетные электрические нагрузки расчетные электрические нагрузки жилых зданий электрические нагрузки общественных зданий и промышленных предприятий электрические нагрузки распределительных линий до 1 кВ электрические нагрузки сетей 106 кВ и ЦП укрупненные показатели расхода электроэнергии коммунальнобытовых потребителей 3...