Прямой обход дерева суть

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

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

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

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. Применение двоичных деревьев для конструирования кодов Хаффмана (этапы создания дерева Хаффмана, идея реализации алгоритма).

Источник

Обход дерева – центрированный (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 вопрос(ов) 
 
Вам это нравится? Поделитесь в социальных сетях!
 
Источник
 
3.7. Обходы бинарных деревьев и леса
 
Многие алгоритмы работы с бинарными деревьями основаны на последовательной обработке узлов дерева. Если для линейного списка последовательность обработки элементов очевидна (в однонаправленных списках только в прямом, в двунаправленных — в прямом и обратном направлении), то в бинарном дереве имеется гораздо больше возможностей из-зи наличия ветвления. В связи с этим вводится понятие обхода дерева. При обходе дерева каждый узел посещается только один раз, при этом узлы выстраиваются в определённую линейную последовательность узлов, т.е. можно говорить о предыдущем и следующем узле.
 
Понятие обхода вводится для любых деревьев, однако удобнее начать с обхода бинарных деревьев ввиду простоты и универсальности.
 
Наиболее известны и практически важны 3 способа прохождения, которые отличаются порядком и направлением обхода бинарного дерева. К сожалению, в литературе встречается довольно много различных названий для данных обходов, что порождает некоторую путаницу. В таблице 3.4 приведены основные названия (верхняя строка) и алгоритмы рекурсивного прохождения узлов дерева для каждого способа (нижняя строка).
 
Рекурсивное прохождение бинарного дерева.
 
Postorder(постфиксный)
 
3. Пройти правое поддерево
 
3. Пройти правое поддерево
 
2. Пройти правое поддерево
 
Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину. Прямой порядок используется в представлении дерева в форме вложенных скобок (левое скобочное представление), в виде уступчатого списка или десятичной классификации Дьюи. В геналогических терминах прямой порядок прохождения дерева отражает династический порядок престолонаследования, когда титул передается старшему потомку.
 
При центрированном (симметричном) проядке дерево проходится слева направо. Такой порядок используется, например, при обходе бинарного дерева поиска, порождая упорядоченную последовательность значений. Подробнее об этом будет рассказано в главах, посвященных сортировке и поиску.
 
Если применяется концевой порядок прохождения, то получается обход дерева снизу-вверх, когда в момент посещения любого узла все его потомки уже пройдены, а корень дерева проходится последним. Из-за этой особенности обхода, концевой порядок называют восходящим, или обратным относительно прямого.
 
Иногда используется еще один способ обхода бинарного дерева  обход в горизонтальном порядке (в ширину). При таком способе узлы бинарного дерева проходятся слева направо, уровень за уровнем от корня вниз (поколение за поколением от старших к младшим).
 
Очередность обработки узлов
 
Источник