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


 

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

71309. Судебно-психологическая экспертиза 182 KB
  Основная задача СПЭ сводится к оказанию помощи суду органам предварительного следствия в более глубоком изучении специальных вопросов психологического содержания входящих в предмет доказывания по уголовным делам или являющихся составными элементами гражданско-правовых споров а также...
71310. Судебная психология 240 KB
  Судебное разбирательство как стадия уголовного процесса следует за предварительным следствием. В ходе судебного разбирательства суд должен в полном объеме проанализировать версию предварительного следствия, а также все возможные взаимосвязи событий и обстоятельств дела.
71311. Психология юридического труда 313 KB
  В кабинете следователя ничто не должно отвлекать допрашиваемого. Кабинет следователя должен быть хорошо освещен. Процессуальная самостоятельность следователя прокурора судьи в пределах определяемых законом предполагает высокий уровень ответственности волевых качеств и организаторских способностей.
71312. Основы обеспечения информационной безопасности в ОВД 153.5 KB
  Основной проблемой информационного общества сегодня является проблема защиты информации от ее утечки искажения блокирования систем и средств передачи информации а так же защита сведений конфиденциального характера и государственной тайны.
71313. Государственная политика в сфере информатизации общества и информационной безопасности 141.5 KB
  Необходимо так же сказать, что федеральный орган исполнительной власти в сфере внутренних дел обеспечивает полиции возможность использования информационно-телекоммуникационной сети Интернет, автоматизированных информационных систем, интегрированных банков данных...
71314. Нормативно-правовое обеспечение информационной безопасности 184.5 KB
  Имеет право обрабатывать данные о гражданах необходимые для выполнения возложенных на нее обязанностей с последующим внесением полученной информации в банки данных о гражданах далее банки данных. Полиция обеспечивает защиту информации содержащейся в банках данных...
71315. Мифы в современном искусстве 13.92 KB
  Зато очень активно использовался язык жестов звуков мимики. Так маленькие дети рожденные от немца русского и даже нигерийца легко найдут общий язык сидя в песочнице. Они умудрились создать свою систему общения не понимая чужой язык.
71316. Логические операции с объемом и содержанием понятия 49.5 KB
  Логический (контекстный) анализ деления понятия направлен на выявление скрытых элементов языковых конструкций в данном случае на формулирование основания когнитивной операции классифицирования на моделирование экспертной оценки речевой коммуникативной ситуации формируются аналитические...
71317. Понятие – смысловая единица речевой коммуникации 48.5 KB
  Логические характеристики понятия как формы мысли: объем и содержание понятия. Владение опытом логического анализа терминологии Умение выявлять в текстовой информации семантические единицы логического анализа Умение различать конкретные абстрактные собирательные понятия...