Деревья прямой обход java

Обход дерева предварительного заказа — итеративный и рекурсивный

Имея двоичное дерево, напишите итеративное и рекурсивное решение для обхода дерева с использованием обхода в прямом порядке в C++, Java и Python.

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

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

Для обхода (непустого) бинарного дерева в предварительном порядке мы должны сделать эти три вещи для каждого узла. n начиная с корня дерева:

(N) Процесс n сам.
(L) Рекурсивно обходим его левое поддерево. Когда этот шаг будет завершен, мы вернемся к n опять таки.
(R) Рекурсивно обходим его правое поддерево. Когда этот шаг будет завершен, мы вернемся к n опять таки.

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

Рекурсивная реализация

Как мы видим, только после обработки любого узла обрабатывается левое поддерево, а за ним правое поддерево. Эти операции могут быть определены рекурсивно для каждого узла. Рекурсивная реализация называется Поиск в глубину (DFS), так как дерево поиска максимально углубляется для каждого дочернего элемента, прежде чем перейти к следующему родственному элементу.

Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

Источник

Обход дерева – центрированный (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 вопрос(ов) 
 
Вам это нравится? Поделитесь в социальных сетях!
 
Источник
 
Двоичное дерево
 
 
Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.
 
 
Типы двоичных деревьев
 
Полное двоичное дерево
 
Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.
 
Совершенное двоичное дерево
 
Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.
 
Законченное двоичное дерево
 
Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.
 
 
Все уровни должны быть заполнены.
 
Все листовые вершины склоняются влево.
 
У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.
 
 
Вырожденное двоичное дерево
 
Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.
 
Скошенное вырожденное дерево
 
Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.
 
Сбалансированное двоичное дерево
 
Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.
 
 
Представление двоичного дерева
 
Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.
 
 
Примеры реализации
 
Python
 
# Двоичное дерево в Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Прямой обход дерева def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Центрированный обход дерева def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Обратный обход дерева def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Прямой обход дерева: ", end="") root.traversePreOrder() print("\nЦентрированный обход дерева: ", end="") root.traverseInOrder() print("\nОбратный обход дерева: ", end="") root.traversePostOrder()
 
Java
 
// Двоичное дерево на Java // Создание узла class Node < int key; Node left, right; public Node(int item) < key = item; left = right = null; >> class BinaryTree < Node root; BinaryTree(int key) < root = new Node(key); >BinaryTree() < root = null; >// Центрированный обход дерева public void traverseInOrder(Node node) < if (node != null) < traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); >> // Обратный обход дерева public void traversePostOrder(Node node) < if (node != null) < traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); >> // Прямой обход дерева public void traversePreOrder(Node node) < if (node != null) < System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); >> public static void main(String[] args) < BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Прямой обход дерева: "); tree.traversePreOrder(tree.root); System.out.print("\nЦентрированный обход дерева: "); tree.traverseInOrder(tree.root); System.out.print("\nОбратный обход дерева: "); tree.traversePostOrder(tree.root); >>
 
Си
 
// Обход дерева на Си #include #include struct node < int item; struct node* left; struct node* right; >; // Центрированный обход дерева void inorderTraversal(struct node* root) < if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); > // Прямой обход дерева void preorderTraversal(struct node* root) < if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); > // Обратный обход дерева void postorderTraversal(struct node* root) < if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); > // Создание нового узла struct node* createNode(value) < struct node* newNode = malloc(sizeof(struct node)); newNode->item = 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, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Центрированный обход дерева\n"); inorderTraversal(root); printf("\nПрямой обход дерева\n"); preorderTraversal(root); printf("\nОбратный обход дерева\n"); postorderTraversal(root); >
 
С++
 
// Двоичное дерево на С++ #include #include using namespace std; struct node < int data; struct node *left; struct node *right; >; // Создание нового узла struct node *newNode(int data) < struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); > // Прямой обход дерева void traversePreOrder(struct node *temp) < if (temp != NULL) < cout data; traversePreOrder(temp->left); traversePreOrder(temp->right); > > // Центрированный обход дерева void traverseInOrder(struct node *temp) < if (temp != NULL) < traverseInOrder(temp->left); cout data; traverseInOrder(temp->right); > > // Обратный обход дерева void traversePostOrder(struct node *temp) < if (temp != NULL) < traversePostOrder(temp->left); traversePostOrder(temp->right); cout data; > > int main() < struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout
 
Где используется
 
 
Для быстрого доступа к данным.
 
В алгоритмах маршрутизации.
 
Для реализации куч.
 
В синтаксических деревьях.
 
 
Источник