В отличие от линейных структур данных (массив, связанный список, очереди, стеки и т. Д.), Которые имеют только один логический способ обхода, деревья можно обходить по-разному. Ниже приведены обычно используемые способы обхода деревьев.
Обходы в глубину: (а) Порядок (слева, корень, справа): 4 2 5 1 3 (б) Предварительный заказ (корень, слева, справа): 1 2 4 5 3 (c) Поступорядочение (слева, справа, корень): 4 5 2 3 1 Обход первого порядка ширины или уровня: 1 2 3 4 5 Пожалуйста, смотрите этот пост для первого обхода в ширину. Inorder Traversal ( практика ):
Алгоритм Inorder (дерево)
1. Пройдите по левому поддереву, т. Е. Вызовите Inorder (left-subtree)
2. Зайдите в рут.
3. Пройдите по правому поддереву, т. Е. Вызовите Inorder (правое поддерево)
Использование Inorder В случае двоичных деревьев поиска (BST) обход в порядке неубывания дает узлы в неубывающем порядке. Чтобы получить узлы BST в невозрастающем порядке, можно использовать вариант Inorder traversal, где Inorder traversal отменен. Пример: обход указанного выше рисунка равен 4 2 5 1 3. Обход предзаказа ( практика ):
Предварительный заказ алгоритма (дерево)
1. Зайдите в рут.
2. Пройдите по левому поддереву, т. Е. Вызовите Preorder (left-subtree).
3. Пройдите по правому поддереву, т. Е. Вызовите Preorder (правое поддерево).
Использование предзаказа Предварительный обход используется для создания копии дерева. Предварительный обход также используется для получения префиксного выражения дерева выражения. Пожалуйста, посетите http://en.wikipedia.org/wiki/Polish_notation, чтобы узнать, почему префиксные выражения полезны. Пример: обход предварительного заказа для указанной выше цифры составляет 1 2 4 5 3. Пост порядковый обход ( практика ):
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Использование Postorder Поступорядоченный обход используется для удаления дерева. См. Подробности в вопросе об удалении дерева. Поступорядоченный обход также полезен для получения постфиксного выражения дерева выражений. См. Http://en.wikipedia.org/wiki/Reverse_Polish_notation для использования постфиксного выражения. Пример: обратный ход для приведенного выше рисунка равен 4 5 2 3 1.
C ++
// C++ program for different tree traversals
#include <iostream>
usingnamespacestd;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
structNode {
data;int
structNode *left, *right;
Node(data)int
{
this->data = data;
left = right = NULL;
}
};
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
voidprintPostorder(structNode* node)
{
if(node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
cout << node->data <<" ";
}
/* Given a binary tree, print its nodes in inorder*/
voidprintInorder(structNode* node)
{
if(node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout << node->data <<" ";
/* now recur on right child */
printInorder(node->right);
}
/* Given a binary tree, print its nodes in preorder*/
voidprintPreorder(structNode* node)
{
if(node == NULL)
return;
/* first print data of node */
cout << node->data <<" ";
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/* Driver program to test above functions*/
intmain()
{
structNode* root =newNode(1);
root->left =newNode(2);
root->right =newNode(3);
root->left->left =newNode(4);
root->left->right =newNode(5);
cout <<"
Preorder traversal of binary tree is
";
printPreorder(root);
cout <<"
Inorder traversal of binary tree is
";
printInorder(root);
cout <<"
Postorder traversal of binary tree is
";
printPostorder(root);
return0;
}
C
// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
structnode {
data;int
structnode* left;
structnode* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
structnode* newNode(data)int
{
structnode* node
= (structnode*)malloc(sizeof(structnode));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
voidprintPostorder(structnode* node)
{
if(node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
printf("%d ", node->data);
}
/* Given a binary tree, print its nodes in inorder*/
voidprintInorder(structnode* node)
{
if(node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Given a binary tree, print its nodes in preorder*/
voidprintPreorder(structnode* node)
{
if(node == NULL)
return;
/* first print data of node */
printf("%d ", node->data);
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/* Driver program to test above functions*/
intmain()
{
structnode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("
Preorder traversal of binary tree is
");
printPreorder(root);
printf("
Inorder traversal of binary tree is
");
printInorder(root);
printf("
Postorder traversal of binary tree is
");
printPostorder(root);
getchar();
return0;
}
Python
# Python program to for tree traversals
# A class that represents an individual node in a
# Binary Tree
classNode:
def__init__(self, key):
self.left=None
self.right=None
self.val=key
# A function to do inorder tree traversal
defprintInorder(root):
ifroot:
# First recur on left child
printInorder(root.left)
# then print the data of node
print(root.val),
# now recur on right child
printInorder(root.right)
# A function to do postorder tree traversal
defprintPostorder(root):
ifroot:
# First recur on left child
printPostorder(root.left)
# the recur on right child
printPostorder(root.right)
# now print the data of node
print(root.val),
# A function to do preorder tree traversal
defprintPreorder(root):
ifroot:
# First print the data of node
print(root.val),
# Then recur on left child
printPreorder(root.left)
# Finally recur on right child
printPreorder(root.right)
# Driver code
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)
print"Preorder traversal of binary tree is"
printPreorder(root)
print"
Inorder traversal of binary tree is"
printInorder(root)
print"
Postorder traversal of binary tree is"
printPostorder(root)
Джава
// Java program for different tree traversals
/* Class containing left and right child of current
node and key value*/
classNode {
intkey;
Node left, right;
publicNode(intitem)
{
key = item;
left = right =null;
}
}
classBinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root =null; }
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
voidprintPostorder(Node node)
{
if(node ==null)
return;
// first recur on left subtree
printPostorder(node.left);
// then recur on right subtree
printPostorder(node.right);
// now deal with the node
System.out.print(node.key +" ");
}
/* Given a binary tree, print its nodes in inorder*/
voidprintInorder(Node node)
{
if(node ==null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.key +" ");
/* now recur on right child */
printInorder(node.right);
}
/* Given a binary tree, print its nodes in preorder*/
voidprintPreorder(Node node)
{
if(node ==null)
return;
/* first print data of node */
System.out.print(node.key +" ");
/* then recur on left sutree */
printPreorder(node.left);
/* now recur on right subtree */
printPreorder(node.right);
}
// Wrappers over above recursive functions
voidprintPostorder() { printPostorder(root); }
voidprintInorder() { printInorder(root); }
voidprintPreorder() { printPreorder(root); }
// Driver method
publicstaticvoidmain(String[] args)
{
BinaryTree tree =newBinaryTree();
tree.root =newNode(1);
tree.root.left =newNode(2);
tree.root.right =newNode(3);
tree.root.left.left =newNode(4);
tree.root.left.right =newNode(5);
System.out.println(
"Preorder traversal of binary tree is ");
tree.printPreorder();
System.out.println(
"
Inorder traversal of binary tree is ");
tree.printInorder();
System.out.println(
"
Postorder traversal of binary tree is ");
tree.printPostorder();
}
}
C #
// C# program for different
// tree traversals
usingSystem;
/* Class containing left and
right child of current
node and key value*/
classNode {
publickey;int
publicNode left, right;
publicNode(intitem)
{
key = item;
left = right =null;
}
}
classBinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root =null; }
/* Given a binary tree, print
its nodes according to the
"bottom-up" postorder traversal. */
voidprintPostorder(Node node)
{
if(node ==null)
return;
// first recur on left subtree
printPostorder(node.left);
// then recur on right subtree
printPostorder(node.right);
// now deal with the node
Console.Write(node.key +" ");
}
/* Given a binary tree, print
its nodes in inorder*/
voidprintInorder(Node node)
{
if(node ==null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
Console.Write(node.key +" ");
/* now recur on right child */
printInorder(node.right);
}
/* Given a binary tree, print
its nodes in preorder*/
voidprintPreorder(Node node)
{
if(node ==null)
return;
/* first print data of node */
Console.Write(node.key +" ");
/* then recur on left sutree */
printPreorder(node.left);
/* now recur on right subtree */
printPreorder(node.right);
}
// Wrappers over above recursive functions
voidprintPostorder() { printPostorder(root); }
voidprintInorder() { printInorder(root); }
voidprintPreorder() { printPreorder(root); }
// Driver Code
staticpublicvoidMain(String[] args)
{
BinaryTree tree =newBinaryTree();
tree.root =newNode(1);
tree.root.left =newNode(2);
tree.root.right =newNode(3);
tree.root.left.left =newNode(4);
tree.root.left.right =newNode(5);
Console.WriteLine("Preorder traversal "
+"of binary tree is ");
tree.printPreorder();
Console.WriteLine("
Inorder traversal "
+"of binary tree is ");
tree.printInorder();
Console.WriteLine("
Postorder traversal "
+"of binary tree is ");
tree.printPostorder();
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// javascript program for different tree traversals
/* Class containing left and right child of current