Порядок узлов дерева прямой обход дерева

Прямой, обратный и симметричный обходы дерева

Если сыновья узла упорядочиваются слева направо, такое дерево называется упорядоченным. В противном случае дерево называетсянеупорядоченым.

Для упорядоченных деревьев существует три способа рекурсивного описания. Для данных способов существуют правила:

1. Если дерево T является нулевым, то в список обхода заносится нулевая запись.

2. Если дерево состоит ровно из 1 узла, то в список обхода заносится этот узел.

Способы рекурсивного описания:

• Прямой обход— сначала посещается корень, затем узлы поддерева
• Симметричный обход— сначала посещаются все узлы поддерева t₁, затем корень n, затем последовательно в симметричном порядке все узлы поддеревьев t₁,…,t_k
• Обход в обратном порядке— сначала посещаются в обратном порядке все узлы поддерева t₁, затем t₂и т.д., последним посещается корень n.

Схемы алгоритмов обходов:

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

Деревья выражений

Если в каждом узле дерева хранятся некоторые данные, то это значение называется меткой узла. Существуют деревья, метки узлов которых являются числами (операндами), а метки внутренних узлов являются символами математических операций (операторами). Такие деревья называются деревьями выражений. При обходе деревьев выражений составляется список узлов, который можно интерпретировать как запись арифметического выражения. В порядке прямого обхода получается список меток узлов x + a b — c d. Такая форма записи называется префиксной формой выражения. В порядке обратного обхода получается постфиксная форма выражения: a b + c d — x, а в порядке симметричного обхода — инфиксная: (a+b)x(c..d). Вопрос №23. Деревья как АТД, набор операций. Реализация АТД — дерево (с помощью массивов, с использованием списка сыновей). Список операций АТД TREE:

• MAKENULL(T) — создать пустое дерево;
• ROOT(T) — получить метку корня дерева;
• PARENT(n, T) — узнать родителя;
• LEFTMOST_CHILD(n, T) -самый левый сын;
• RIGHT_SIBLING(n, T) — правый брат;
• LABEL(n, T) получить метку узла;
• CREATE(n, T1, T2, . ) — создать дерево из узла-корня и набора поддеревьев.

Рекурсивная функция, которая позволяет обходить дерево в порядке прямого обхода и составлять его список: Функция, которая производит обход дерева не в прямом порядке, использует стек. Для этого можно использовать предыдущую реализацию стека. Основные идея в том, что когда функция дойдет до узла n, стек будет хранить путь от корня до этого узла. Причем корень будет на дне стека, а узел n — на вершине. Сама функция может работать в двух режимах: 1. обход по направлению к потомкам самого левого еще не проверенного пути дерева до тех пор, пока не встретится лист, при этом узлы заносятся в стек. 2. возврат по пройденному пути с поочередным извлечением узлов до тех пор, пока не встретится узел, имеющий еще неописанного правого брата.

Реализация деревьев

Одна из реализаций дерева может быть выполнена на основе массива, где каждый элемент массива – это имя родительского узла. Такая форма дерева очень удобна для реализации PARENT(n, T). Она основана на том свойстве деревьев, что каждый узел, отличающийся от корня, имеет только одного родителя. Однако, она неудобна для написания операторов, дающих информацию о сыновьях. Чтобы реализовать операции этого дерева, нужно условиться о том, что сыновья одного узла нумеруются в возрастающем порядке слева направо. Для представления дерева с помощью списка сыновей можно ввести массив указателей на первый элемент списка сыновей. Каждый указатель является массивом, состоящим из элементов-узлов. Элементы списка сыновей являются сыновьями данного конкретного узла. Список сыновей Такая реализация не очень удобна, если надо реализовать операцию . Возможно следующее изменение представления дерева. В данной реализации заменим массив заголовков на массив области узлов. Элементы этого массива расположены произвольно, каждый элемент — это структура с двумя полями. Первые два поля — это указатели на левых сыновей. Вторые два поля — это указатели на правых братьев. Используя такое представление, можно найти самого левого сына как cellspace [ i ]. node = n. Предположим, что имя узла это n, тогда указатель, стоящий в nodespace[i ]. header, указывает на заголовок самого левого узла в массиве cellspace. Существует модификация предложенного способы представления дерева не с помощью двух массивов, а с помощью одного. Такой способ представления удобен для реализации всех операций АТД дерева, за исключением PARENT. Вопрос №24. Определение двоичных деревьев. Реализация двоичных деревьев в виде массива структур с полями: левый сын, правый сын. Двоичное дерево(бинарное) — это или пустое дерево или дерево у которого любой узел или лист имеет либо левого сына либо или правого сына. Рационально для представления двоичных деревьев использовать массив cellspace, каждый элемент массива — структура. Вопрос №25. Применение двоичных деревьев для конструирования кодов Хаффмана (этапы создания дерева Хаффмана, идея реализации алгоритма).

Источник

Порядок узлов

Если в определении дерева имеет значение порядок поддеревьевT₁, T₂, . T_m, то дерево является упорядоченным.

Сыновья узла обычно упорядочиваются слева направо. Поэтому деревья, приведенные на рисунке, являются различными.

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

Обходы дерева

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

• Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
• Если дерево T состоит из одного узла, то в список обхода записывается этот узел;
• Пусть дерево T имеет корень n и поддеревья T₁, T₂, . T_m, как показано на рисунке

Тогда для различных способов обхода имеем следующее:

1. Прямой обход. Сначала посещается корень n, затем в прямом порядке узлы поддерева T₁, далее все узлы поддерева T₂ и т.д. Последними посещаются в прямом порядке узлы поддерева T_m.
2. Обратный обход. Сначала посещаются в обратном порядке все узлы поддерева T₁, затем в обратном порядке узлы поддеревьев T₂ … T_m, последним посещается корень n.
3. Симметричный обход. Сначала в симметричном порядке посещаются все узлы поддерева T₁, затем корень n, после чего в симметричном порядке все узлы поддеревьев T₂ … T_m.

Рассмотрим пример всех способов обхода дерева, изображенного на рисунке: Порядок узлов данного дерева в случаепрямого обхода будет следующим: 1 2 3 5 8 9 6 10 4 7. Обратный обход этого же дерева даст нам следующий порядок узлов: 2 8 9 5 10 6 3 7 4 1. При симметричном обходе мы получим следующую последовательность узлов: 2 1 8 5 9 3 10 6 7 4.

Помеченные деревья и деревья выражений

Часто бывает полезным сопоставить каждому узлу дерева метку или значение. Дерево, у которого узлам сопоставлены метки, называется помеченным деревом. Метка узла – это значение, которое «хранится» в узле. Полезна следующая аналогия: дерево – список, узел – позиция, метка – элемент. Рассмотрим пример дерева с метками, представляющее арифметическое выражение (a+b)*(a+c), где n₁, n₂, …, n₇ – имена узлов, а метки проставлены рядом с соответствующими узлами. Правила соответствия меток деревьев элементам выражений следующие:

• Метка каждого листа соответствует операнду и содержит его значение;
• Метка каждого внутреннего (родительского) узла соответствует оператору.

Часто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом обходе получим известнуюпрефиксную форму записи выражения, где оператор предшествует обоим операндам. В нашем примере мы получим префиксное выражение вида: *+ab+ac. Обратный обход меток дерева дает постфиксное представление выражения (польскую запись). Обратный обход нашего дерева даст нам следующую запись выражения: ab+ac+*. Следует учесть, что префиксная и постфиксная запись выражения не требует скобок. При симметричном обходе мы получим обычную инфиксную запись выражения: a+b * a+c. Правда для инфиксной записи выражений характерно заключение в скобки: (a+b)*(a+c).

Источник

Обход дерева – центрированный (inorder), прямой (preorder) и обратный (postorder) (три основных способа обхода)

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

Начиная снизу, слева направо

Хотя этот процесс в некотором роде прост, он не учитывает иерархию дерева, а только глубину узлов. Вместо этого мы используем методы обхода, которые учитывают базовую структуру дерева, то есть

Помните, что нашей задачей является посещение каждого узла, поэтому нам нужно посетить все узлы в поддереве, посетить корневой узел и также посетить все узлы в правом поддереве.

В зависимости от порядка, в котором мы это делаем, может быть три типа обхода .

Центрированный тип обхода (Inorder traversal)

1. Сначала посетите все узлы в левом поддереве
2. Затем корневой узел
3. Посетите все узлы в правом поддереве

inorder(root->left) display(root->data) inorder(root->right)
 
Прямой тип обхода (Preorder traversal)
 
 
Посетите корневой узел
 
Посетите все узлы в левом поддереве
 
Посетите все узлы в правом поддереве
 
 
display(root->data) preorder(root->left) preorder(root->right)
 
Обратный тип обхода (Postorder traversal)
 
 
посетить все узлы в левом поддереве
 
посетить корневой узел
 
посетить все узлы в правом поддереве
 
 
postorder(root->left) postorder(root->right) display(root->data)
 
Давайте визуализируем центрированный тип обхода (inorder traversal). Начнем с корневого узла.
 
 
Сначала мы проходим левое поддерево. Мы также должны помнить, что нужно посетить корневой узел и правое поддерево, когда дерево будет готово.
 
Давайте поместим все это в стек, чтобы мы помнили.
 
 
Теперь перейдем к поддереву, указанному на вершине стека.
 
Опять же, мы следуем тому же правилу центрированного типа (inorder)
 
Left subtree -> root -> right subtree
 
Пройдя левое поддерево, мы остаемся с
 
Поскольку у узла "5" нет поддеревьев, мы печатаем его напрямую. После этого мы печатаем его родительский узел «12», а затем правый дочерний «6».
 
Поместить все в стек было полезно, потому как теперь, когда левое поддерево корневого узла было пройдено, мы можем распечатать его и перейти к правому поддереву.
 
После прохождения всех элементов, центрированный тип обхода (inorder traversal) выглядит так:
 
Нам не нужно создавать стек самостоятельно, потому что рекурсия поддерживает для нас правильный порядок.
 
Полный код для центрированного (inorder), прямого (preorder) и обратного (postorder) типа обхода на языке программирования C размещен ниже:
 
#include #include struct node < int data; struct node* left; struct node* right; >; void inorder(struct node* root)< if(root == NULL) return; inorder(root->left); printf("%d ->", root->data); inorder(root->right); > void preorder(struct node* root)< if(root == NULL) return; printf("%d ->", root->data); preorder(root->left); preorder(root->right); > void postorder(struct node* root) < if(root == NULL) return; postorder(root->left); postorder(root->right); printf("%d ->", root->data); > struct node* createNode(value)< struct node* newNode = malloc(sizeof(struct node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; > struct node* insertLeft(struct node *root, int value) < root->left = createNode(value); return root->left; > struct node* insertRight(struct node *root, int value)< root->right = createNode(value); return root->right; > int main()< struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal \n"); inorder(root); printf("\nPreorder traversal \n"); preorder(root); printf("\nPostorder traversal \n"); postorder(root); >
 
Вывод кода будет выглядеть так:
 
Inorder traversal 5 ->12 ->6 ->1 ->9 -> Preorder traversal 1 ->12 ->5 ->6 ->9 -> Postorder traversal 5 ->6 ->12 ->9 ->1 ->
 
 
Рекомендуем хостинг TIMEWEB
 
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
 
Рекомендуемые статьи по этой тематике
 
По статье задано0 вопрос(ов) 
 
Вам это нравится? Поделитесь в социальных сетях!
 
Источник