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


 

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

12366. Измерение магнитной проницаемости ферромагнетика индукционным методом 249 KB
  Лабораторная работа № 11 Измерение магнитной проницаемости ферромагнетика индукционным методом 1. Цель работы: Измерить магнитные проницаемости образцов стали и феррита индукционным методом. 2. Магнитные свойства вещества. Нейтральные молекулы и атомы веществ
12367. Измерение магнитного поля постоянного кольцевого магнита 226 KB
  Лабораторная работа № 10 Измерение магнитного поля постоянного кольцевого магнита 1. Цель работы. Измерить магнитное поле на оси постоянного кольцевого магнита и рассчитать его параметры. 2. Магнитные свойства вещества. Постоянные магниты. Нейтральные молекулы
12368. Магнитное поле Земли. Измерение горизонтальной составляющей магнитного поля Земли 141 KB
  Измерение горизонтальной составляющей магнитного поля Земли. Цель работы: измерение горизонтальной составляющей магнитного поля Земли. Магнитное поле Земли. Магнитное поле Земли подобно полю равномерно намагниченного шара. Полюса м
12369. Измерение магнитного поля на оси катушек Гельмгольца 247.5 KB
  Лабораторная работа № 8 Измерение магнитного поля на оси катушек Гельмгольца 1. Цель работы: измерение магнитного поля на оси катушек Гельмгольца индукционным методом. 2. Магнитные поля токовых систем. Магнитное поле постоянных токов изучалось Био и Саваром окон...
12370. Изучение магнитного поля на оси соленоида 280.5 KB
  Лабораторная работа № 7 Изучение магнитного поля на оси соленоида 1. Цель работы: экспериментальное исследование магнитного поля на оси соленоида. 2. Магнитные поля токовых систем. Магнитное поле постоянных токов изучалось Био и Саваром окончательная формулировк...
12371. Измерение магнитного поля прямолинейного проводника с током 228 KB
  Лабораторная работа № 6 Измерение магнитного поля прямолинейного проводника с током 1. Цель работы: экспериментальное исследование магнитного поля прямолинейного проводника с током индукционным методом. 2. Магнитные поля токовых систем. Магнитное поле постоян
12372. Совершенствование обслуживания покупателей в ООО «Армина» 1.11 MB
  Исследование сущности обслуживания и показателей его качества; рассмотреть особенности организации и дать оценку эффективности обслуживания в магазинах ООО «Армина»; выявить основные направления совершенствования обслуживания покупателей в ООО «Армина»; дать характеристику ассортимента и оценку некоторых потребительских свойств детских игрушек...
12373. Измерение удельного сопротивления резистивного провода 300 KB
  Лабораторная работа № 4 Измерение удельного сопротивления резистивного провода 1. Цель работы: знакомство с устройством и принципами действия электроизмерительных приборов измерение удельного сопротивления резистивного провода. 2. Электроизмерительные приборы....
12374. Технологічний процес проведення гірничотехнічної рекультивації земель, порушених відкритими гірничими роботами 11.02 MB
  Обґрунтування можливості рекультивації залишених вироблених просторів обводнених кар’єрів, шляхом використання твердих будівельних відходів для відновлення земель порушених відкритою розробкою родовищ будівельних матеріалів.