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


 

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

74551. Пакетный файл 20.46 KB
  После запуска пакетного файла программаинтерпретатор как правило COMMND. Командный интерпретатор в MSDOS а следом и в семействе Windows 9x имеет название COMMND.BT который автоматически исполняется COMMND.exe который частично совместим с COMMND.
74553. Теорія двоїстості 764 KB
  Економічну інтерпретацію кожної з пари таких задач розглянемо на прикладі виробничої задачі п.6 є двоїстою або спряженою до задачі 5. Як у прямій так і у двоїстій задачі використовують один набір початкових даних. Крім того вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки а рядки матриці А матриці коефіцієнтів при змінних з обмежень прямої задачі стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі.
74554. Аналіз лінійних моделей оптимізаційних задач 408.5 KB
  Оцінка рентабельності продукції яка виробляється і нової продукції. Використання двоїстих оцінок уможливлює визначення рентабельності кожного виду продукції яка виробляється підприємством. Водночас можна оцінити інтервали можливої зміни цін одиниці кожного виду продукції що дуже важливо за ринкових умов. Це дає змогу перевірити
74555. Аналіз коефіцієнтів лінійних моделей 196 KB
  1 Аналіз коефіцієнтів цільової функції Під впливом різних обставин ціна виробленої на підприємстві одиниці продукції може змінюватися збільшуватися чи зменшуватися. Нехай змінюється ціна на одиницю продукції виду С тобто початкове значення 3 ум. подамо як де – величина зміни ціни одиниці продукції виду С. Отже ціна одиниці продукції виду С може збільшуватися чи зменшуватися на 1ум.
74556. КОНЦЕПТУАЛЬНІ АСПЕКТИ МАТЕМАТИЧНОГО МОДЕЛЮВАННЯ ЕКОНОМІКИ 262.5 KB
  Сутність методології математичного моделювання полягає в заміні досліджуваного об’єкта його образом математичною моделлю і подальшим вивченням дослідженням моделі на підставі аналітичних методів та обчислювальнологічних алгоритмів які реалізуються за допомогою комп’ютерних програм. Другий етап вибір чи розроблення алгоритму для реалізації моделі на комп’ютері. Зумовленість моделі об’єктом. Як модель для об’єкта так і об’єкт для даної моделі семантично та інтерпретаційно багатозначні: об’єкт описується не однією а...
74557. ОПТИМІЗАЦІЙНІ ЕКОНОМІКО-МАТЕМАТИЧНІ МОДЕЛІ 661.5 KB
  Постановка задачі економіко-математичного моделювання. Приклади задач економіко-математичного моделювання. Задача визначення оптимального плану виробництва. Задача про «дієту». Транспортна задача.
74558. Задача лінійного програмування та методи її розв’язування 2.06 MB
  Основні властивості розв’язків задачі лінійного програмування. Графічний метод розв’язування задач лінійного програмування. Називається допустимим розв’язком планом задачі лінійного програмування.
74559. СИМПЛЕКСНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ 278 KB
  Розв’язування задачі лінійного програмування симплексним методом. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків.