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


 

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

36875. ИСПОЛЬЗОВАНИЕ ОТНОСИТЕЛЬНОЙ И АБСОЛЮТНОЙ АДРЕСАЦИИ В ВЫЧИСЛЕНИЯХ 197.5 KB
  Переименуйте Лист 1 в Задание 1 и на этом листе создайте таблицу по Образцу 1 значения в ячейках к которым применена заливка серым цветом подсчитать с помощью формул: в ячейку D2 введите формулу в которой по умолчанию используются относительные адреса ячеек и скопируйте её в ячейки для других товаров D3 D4 с помощью маркера автозаполнения; в ячейку D5 введите формулу расчета суммы затрат на приобретение товаров; в ячейку E2 введите формулу: = Стоимость 100 Всего в которой используются относительные адреса ячеек и...
36876. РАБОТА СО СПИСКАМИ: ФИЛЬТРАЦИЯ, СОРТИРОВКА, ИТОГИ, СВОДНЫЕ ТАБЛИЦЫ 64.5 KB
  РАБОТА СО СПИСКАМИ: ФИЛЬТРАЦИЯ СОРТИРОВКАИТОГИ СВОДНЫЕ ТАБЛИЦЫ. Перейти на лист Книжный магазин и скопировать таблицу на листы Итоги1 Итоги2 Итоги3 и Итоги4. На листе Итоги1 сформировать итоги по товарам: в итоги включить сумму значений по столбцам Колво и Доход руб. На листе Итоги2 сформировать итоги по продавцам: в итоги включить сумму значений по столбцам Колво и Доход руб.
36877. РАБОТА С ФОРМУЛАМИ И ФУНКЦИЯМИ В MS EXCEL 527 KB
  Создайте таблицу Результаты тестирования рассчитайте средний показатель тестирования для каждого сотрудника. Создайте таблицу содержащую следующие поля: № п п Фамилия Тест 1 Тест 2 Тест 3 Тест 4 Средний показатель Заполните таблицу данными. Таблица результаты тестирования Рассчитайте Средний показатель тестирования каждого сотрудника. Для этого: Выделите пустую ячейку в поле Средний показатель напротив фамилии первого сотрудника.
36878. Определение ёмкости конденсаторов измерительным мостиком Соти 85 KB
  Тема: Определение ёмкости конденсаторов измерительным мостиком Соти. Цель работы: измерение теплоёмкостей двух конденсаторов проверка закона последовательного и параллельного соединения конденсаторов. Пусть Δφ1 Δφ2 мгновенные значения напряжений на обкладках конденсаторов а ΔφN ΔφNB мгновенные значения напряжений на сопротивлениях R1 R2.
36880. Определение заряда иона водорода 63.5 KB
  Тема: Определение заряда иона водорода. Цель работы: изучить прохождение тока в электролитах определить заряд иона водорода оценить погрешность данного метода определения заряда иона водорода и ознакомиться с явлением наводораживания металлов. КРАТКАЯ ТЕОРИЯ Для определения заряда иона водорода можно использовать прохождение тока в электролитах явление электролиза.
36882. Word: Ввод и редактирование текста. Операции с фрагментами текста 99 KB
  ввод пробела: при нажатии клавиши Пробел вводится занимающий определенное место в строке символ пробела; наличие или отсутствие пробела в конце строки может быть определено при нажатии на кнопку Непечатаемые знаки на Стандартной панели инструментов в правой стороне; Введите в расположенной ниже строке по одному пробелу между цифрами 1 и 2 и еще три пробела в конце строки. Ввод пробелов: 1111122222311112222311122231122313 Отобразите на экране символы пробела абзаца разрыва строки нажатием на кнопку Непечатаемые знаки на Стандартной панели...