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


 

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

30089. Методические особенности вариативных курсов «Окружающий мир» 62 KB
  Методические особенности вариативных курсов Окружающий мир Учебная программа – документ определяющий цели задачи и основное содержание обучения по конкретному предмету уровень его предъявления учащимся и требования к результатам усвоения. В связи с углублением процесса дифференциации начального образования разработаны различные варианты учебных программ по предметам Окружающий мир и Естествознание Природоведение. Плешаков Система учебных курсов Зеленый дом обеспечивает ознакомление младших школьников с окружающим миром их...
30090. Формирование и развитие начальных естественнонаучных представлений и понятий на уроках «Окружающий мир» 37.5 KB
  Понятия отражают существенные свойства связи и отношения предметов и явлений. Как понятия так и представления которыми овладеют дети при изучении естествознания делятся на общие и единичные. Общие понятия охватывают однородные предметы и явления. Единичные понятия это понятия о конкретных объектах и явлениях например река Волга Кавказские горы озеро Байкал дождь гроза и т.
30091. Олигофрения 18.9 KB
  а также с резуснесовместимостью крови матери и плода травмой и асфиксией плода в родах перенесёнными менингитомэнцефалитом и т. Имбецильность средняя степень олигофрении слабоумия интеллектуального недоразвития обусловленная задержкой развития мозга плода или ребёнка в первые годы жизни. В ней выделяется 4 степени тяжести олигофрении: Легкая IQ 5070 Умеренная IQ 3550 Тяжелая IQ 2035 Глубокая IQ менее 20 Причинами олигофрении могут служить: наследственные факторы в том числе патология генеративных клеток...
30092. Заде́ржка психи́ческого разви́тия 19.51 KB
  ЗПР нарушение нормального темпа психического развития когда отдельные психические функции память вниманиемышление эмоциональноволевая сфера отстают в своём развитии от принятых психологических норм для данного возраста. ЗПР как психологопедагогический диагноз ставится только в дошкольном и младшем школьном возрасте если к окончанию этого периода остаются признаки недоразвития психических функций то речь идёт уже оконституциональном инфантилизме или об умственной отсталости. Синдром психического инфантилизма Церебрастенический...
30093. Микроцефалия 15.16 KB
  Микроцефалия характерна для таких синдромов как: трисомия по 18 хромосоме синдром Эдвардса трисомия по 13 хромосоме синдром Патау синдром кошачьего крика сидром Миллера синдром ПрадераВилли и др. плодный алкогольный синдром Аутосомнорецессивный тип наследования.
30094. Шизофрени́я 17.6 KB
  У лиц страдающих шизофренией обнаруживается повышенная дофаминергическая активность в мезолимбическом пути и сниженная в мезокортикальном. У больных шизофренией с большой вероятностью диагностируются коморбидные расстройства в их числе депрессии и тревожные расстройства; риск алкоголизма и наркомании составляет около 40 . Повышенный риск самоубийства и проблемы со здоровьем обуславливают снижение продолжительность жизни которая у больных на 1012 лет короче по сравнению с людьми не страдающими шизофренией. Есть также данные о возможной...
30095. Наследственные нарушения органов зрения 20.15 KB
  Аниридия иногда сочетается с передней и задней полярной катарактой подвывихом хрусталика и редко – колобомой хрусталика. Эктопия хрусталика – смещение линзы хрусталика. Наиболее типичным примером является эктопия хрусталика наблюдающаяся при семейнонаследственном поражении всей костномышечной системы которое выражается в удлинении дистальных фаланг пальцев рук и ног удлинении конечностей слабости суставов. В глазах при этом обнаруживается симметричное смещение хрусталика.
30096. Наследственные заболевания органов слуха 12 KB
  Наследственные заболевания органов слуха: Наследственные нарушения слуха возникают под действием генетических факторов в том числе в результате врожденных дефектов. Некоторые исследователи в особую группу факторов снижения слуха выделяют факторы патологического воздействия на орган слуха плода не связанные с генетическим фоном. Несиндромальная форма тугоухости – форма тугоухости при которой снижение слуха не сопровождается другими признаками или заболеваниями других органов и систем которые передавались бы по наследству вместе с...
30097. Сложные сенсорные дефекты при наследственных синдромах 12.17 KB
  Дети с задержкой психического развития которая сочетается с дефектами зрения или слуха; Глухие дети с нарушениями соматического характера врожденные пороки сердца заболевания почек печени желудочнокишечного тракта. Кроме того в дефектологической практике встречаются дети с множественными дефектами. Дети с умственной осталостью слепоглухие; 2. Дети с нарушениями опорнодвигательного аппарата в сочетании с дефектами органов слуха зрения речи или интеллектуальной недостаточностью.