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


 

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

37298. Теория обучения и воспитания 481 KB
  Методические рекомендации и план освоения учебной дисциплины 13 Описание учебнометодического комплекса дисциплины Теория обучения и воспитания 15 Виды учебной работы 16 Тематический план курса 16 8. Задачи: Вооружить студентов системой научных знаний о сущности и особенностях процессов обучения воспитания и развития; Раскрыть потенциалы образовательной среды и ее возможные модификации для обеспечения качества образования; Активизировать развитие у студентов профессиональнопедагогического мышления умения видеть и анализировать...
37299. Перехідна характеристика об’єкта керування 101.5 KB
  Користуючись теоремою розкладення та стандартною функцією перетворення Лапласа розрахувати та побудувати перехідні характеристики об'єкта керування. Перехідну характеристику ht будуємо за допомогою стандартної операції зворотного перетворення Лапласа програмного середовища Mthcd. Спочатку знаходимо перетворення за Лапласом вихідної величини hp Задаємо початкові умови: Знайдемо перехідну функцію за допомогою теореми розкладення. Спочатку знаходимо перетворення за Лапласом...
37300. Общие требования к курсовой работе (для юридических дисциплин) 190 KB
  Структура и содержание курсовой работы Тема курсовой работы избирается студентом исходя из его интересов и согласовывается с научным руководителем. После утверждения темы студентом разрабатывается план работы который также должен быть согласован с научным руководителем. В дальнейшем при написании работы студенту рекомендуется обсуждать с руководителем наиболее принципиальные и спорные вопросы темы. Структура и содержание курсовой работы должны в полной мере раскрывать избранную тему.
37301. Физиология центральных и периферических эндокринных органов 57.54 KB
  Все процессы жизнедеятельности организма строго согласованы между собой по скорости, времени и месту протекания. В организме человека эту согласованность на периферии осуществляют внутриклеточные и межклеточные механизмы регуляции, важнейшую роль в которых играют гормоны.
37302. Инженерный анализ моделей технических систем с помощью MathCAD 72.5 KB
  Освоить программу MathCAD и получить практические навыки ее использования при инженерном анализе моделей технических систем.
37303. Провести анализ напряженно-деформированного состояния конструкции балочного типа с заданным поперечным сечением, при статическом нагружении 512 KB
  Ввод координат 2 Задание материала Для задания характеристик материала выберем пункт меню Model= Mteril Модель= Материал. Рисунок 2 Задание материала и его свойств Для сохранения введенного материала в библиотеке нажмем кнопку Sve ответив при этом утвердительно на запрос о подтверждении занесения Ст. Рисунок 3 Выбор типа конечных элементов Нажмем кнопку Shpe Форма для задания формы и размеров поперечного сечения балки. Рисунок 4 Задание формы поперечного сечения балки Выберем из списка Shpe сечение Chnnel C Section...
37305. Проектирование усилительного устройства, цифрового устройства 968.5 KB
  Усилитель напряжения УН усиливает входной сигнал до необходимого уровня. Действующее значение напряжения: .4 Выбор и расчёт усилителя напряжения Каскад УН строим на базе инвертирующего усилителя.2 Инвертирующий усилитель напряжения на ОУ 1.
37306. Рачсчет мелкосерийного производства 977.88 KB
  Для современного этапа развития экономики страны особое значение приобретает полное использование преимуществ рыночной системы хозяйствования, положительного опыта предыдущего периода её функционирования, возможностей выявления резервов роста производства, которыми располагает народное хозяйство РБ.