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


 

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

82081. Будь природі сином, будь природі другом 75 KB
  Так до лісу Надається слово довідковому бюро. Ліс це сукупність землі рослинності в якій домінують дерева та чагарники тварин мікроорганізмів та інших природних компонентів що в своєму розвитку взаємопов’язані впливають один на одного і навколішне середовище.
82082. Твоє життя – твій вибір 98 KB
  Закласти бажання і прагнення залишатися здоровими на довгі роки життя; пропагувати здоровий спосіб життя формувати національну свідомість учнів та їх екологічну культуру переконати у необхідності берегти здоров’я яке потрібне для побудови нової держави.
82083. Несміливе дитя Підгір’я (літературно-історичний проект Марійка Підгірянка: грані суспільного буття, професійної діяльності) 53.5 KB
  Хоча Марійка Підгірянка давно вже в засвітах, вона і далі залишається талановитим послом і речником рідного народу у Королівстві дітей. Разом з її словом вони вчаться любити життя, в якому є багато цінносте, та найголовніші з них – Бог, Мати, Україна. А свої поезії підписує просто – Марійка Підгірянка.
82084. ВІД РЕМЕСЛА ДО ТВОРЧОСТІ 63.5 KB
  Які народні промисли можна зустріти на території нашого району 1 ведучий: Іскорка таланту схована при народженні в душі кожної людини. 2 ведучий: Кожна особистість в чомусь неповторна і виразна. 1 ведучий: Ми поговоримо про народні ремесла та умільців які вкладають у них часточку своєї душі.
82085. Теоретические основы прогнозирования банкротства МУП «Уфаводоканал» 820.5 KB
  Государственное регулирование отношений несостоятельности банкротства до 29 мая 2004 г. 257 Об обеспечении интересов РФ как кредитора в делах о банкротстве и в процедурах банкротства ФСФО РФ как орган исполнительной власти упразднен и функции уполномоченного органа по представлению в делах...
82086. Пути повышения эффективности маркетинговой деятельности ООО «Принт – Экспресс» с применением Интернет 756.5 KB
  Общая характеристика деятельности ООО Принт Экспресс. Основные направления маркетинговой деятельности ООО Принт Экспресс. Эффективность маркетинговой деятельности ООО Принт Экспресс. Теоретические и методологические аспекты повышения эффективности маркетинговой деятельности.
82087. ОСОБЕННОСТИ ФУНКЦИОНИРОВАНИЯ РАЗВЛЕКАТЕЛЬНОЙ ТЕЛЕПРОГРАММЫ В РАДИОЭФИРЕ (НА ПРИМЕРЕ ПЕРЕДАЧИ «BEAUTYTIME» ООО ИК «МЕДИА-ЦЕНТР») 854.5 KB
  Новизна дипломной работы заключается в создании четкой структурированной классификации развлекательных программ на телевидении и радио, на основе классификаций некоторых исследователей, а также собственных наблюдений.
82088. Формування нормативного мовлення семикласників у процесі вивчення розділу «Дієслово» 297.5 KB
  Важливу роль в цьому процесі відіграє знайомство з частинами мови. Часті порушення орфоепічних акцентуаційних словотвірних граматичних норм української літературної мови в усному і писемному мовленні школярів вимагають комплексної цілеспрямованої роботи над нормами української літературної мови.
82089. Расчет трансформаторной подстанции 110/10кВ «Жулдыз» 1.28 MB
  Для обеспечения этого энергетиками создана надежная и экономичная система распределения электроэнергии на всех ступенях применяемого напряжения с максимальным приближением высокого напряжения к потребителям.