Деревья. Теперь обратимся к изучению деревьев, наиболее важных нелинейных структур, встречающихся в вычислительных алгоритмах

Теперь обратимся к изучению деревьев, наиболее важных нелинейных структур, встречающихся в вычислительных алгоритмах. Грубо говоря, структура дерева означает " разветвление", такое от­ношение между " узлами", как и в обычных деревьях.

Определим формально дерево как конечное множество Т, со­стоящее из одного или более узлов, таких, что

a) Имеется один специально обозначенный узел, называемый корнем данного дерева.

b) Остальные узлы (исключая корень) содержатся в т > 0 по­парно не пересекающихся множествах Т_i,..., Т_m, каждое из которых в свою очередь является деревом. Деревья Т_i,..., Т_m называются поддеревьями данного корня.

Это определение является рекурсивным, т. е. мы определили дерево в терминах самих же деревьев. Разумеется, никакого пороч­ного круга здесь не возникает, поскольку деревья с п > 1 узлами определяются с использованием понятия дерева с количеством уз­лов, меньшим чем п', следовательно, наше определение дает понятия деревьев с двумя узлами, тремя узлами, в конечном итоге с любым числом узлов. Можно попытаться дать и нерекурсивное определение дерева, но рекурсивное опреде­ление кажется более подходящим, так как рекурсивность являет­ся естественной характеристикой структур типа дерева. Рекурсив­ный характер деревьев налицо также и в природе, поскольку почки молодого дерева вырастают в ветви, имеющие собственные почки, которые дают новые ветви и т. д. Основываясь на рекурсивном определении, подобном тому, которое мы привели выше, легко дать строгие доказательства многих важных фактов относительно де­ревьев, используя индукцию по числу узлов в дереве.

Из нашего определения следует, что каждый узел дерева явля­ется корнем некоторого поддерева, которое содержится в этом де­реве. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом; иногда его называют листом. Неконцевые узлы часто называют узлами разветвления. Уровень узла по отношению к дереву Т определяет ся следующим образом: говорят, что корень имеет уровень 1, а дру­гие узлы имеют уровень на единицу выше их уровня относительно содержащего их поддерева Т, этого корня.

На рис. 15 показано дерево с семью узлами. Проиллюстрируем на нем введенные нами понятия. Корнем дерева является А; дерево имеет два поддерева: {В} и [С, D, Е, F, G]. Корнем дерева {С, D, Е, F, G} является С. Узел С имеет уровень 2 относительно всего дерева; он имеет три поддерева: [D], [Е] и {F, G), и, следовательно, его степень равна 3. Узлы В, D, Е и G являются конце­выми узлами; F— единственный узел степени 1, а G—единствен­ный узел уровня 4.

Обход деревьев

Сначала вглубь и сначала вширь

[1] Фомин С.В. Системы счисления, издание пятое, М., Наука, главная редакция физико-математической литературы, 1987, серия Популярные лекции по математике, вып. 40

[2] двоично-десятичная форма представления чисел Ее появление объясняется следующим. При обработке больших массивов десятичных чисел (например, больших экономических документов) приходится тратить существенное время на перевод этих чисел из десятичной системы счисления в двоичную для последующей обработки и обратно -для вывода результатов. Каждый такой перевод требует выполнения двух - четырех десятков машинных команд. С включением в состав отдельных ЭВМ специальных функциональных блоков или спецпроцессоров десятичной арифметики появляется возможность обрабатывать десятичные числа напрямую, без их преобразования, что сокращает время вычислений. При этом каждая цифра десятичного числа представляется двоичной тетрадой. Например, A₁₀ =3759, A_2-10= 0011 0111 0101 1001. Положение десятичной точки (запятой), отделяющей целую часть от дробной, обычно заранее фиксируется. Значение знака числа отмечается кодом, отличным от кодов цифр. Например, ⌠ +■ имеет значение тетрады ⌠ 1100■, а ⌠ -■ - ⌠ 1101■.