ОБХІД БІНАРНОГО ДЕРЕВА ПІСЛЯ ЗАМОВЛЕННЯ - TECHCODEVIEW.COM

Обхід поштового замовлення визначається як вид обхід дерева який дотримується політики лівого-правого кореня таким чином, що для кожного вузла:

Першим проходить ліве піддерево

Потім виконується обхід правого піддерева

Нарешті, здійснюється обхід кореневого вузла піддерева

Обхід поштового замовлення

Алгоритм постпорядкового обходу бінарного дерева:

Алгоритм обходу після замовлення показаний таким чином:

Поштовий переказ (корінець):

Виконуйте кроки 2-4, доки root не стане != NULL

Postorder (корінь -> ліворуч)

Postorder (корінь -> праворуч)

Записати корінь -> дані

Кінцева петля

Як працює Postorder Traversal бінарного дерева?

Розглянемо таке дерево:

Приклад бінарного дерева

Якщо ми виконуємо обхід після порядку в цьому бінарному дереві, то обхід буде таким:

Крок 1: Обхід проходитиме від 1 до його лівого піддерева, тобто 2, потім від 2 до його лівого кореня піддерева, тобто 4. Тепер 4 не має піддерева, тому його відвідуватимуть.

Вузол 4 відвідується

крок 2: Оскільки ліве піддерево 2 відвідано повністю, тепер воно перетинатиме праве піддерево 2, тобто воно переміститься до 5. Оскільки піддерева 5 немає, його буде відвідано.

Вузол 5 відвідується

крок 3: Тепер відвідуються як ліве, так і праве піддерева вузла 2. Тож тепер відвідайте сам вузол 2.

Відвідується вузол 2

крок 4: Під час обходу лівого піддерева вузла 1 він тепер переміститься до кореня правого піддерева, тобто 3. Вузол 3 не має жодного лівого піддерева, тому він обійде праве піддерево, тобто 6. Вузол 6 не має піддерева і тому його відвідують.

Вузол 6 відвідується

крок 5: Усі піддерева вузла 3 обходяться. Отже, зараз відвідано вузол 3.

Відвідується вузол 3

Крок 6: Оскільки пройдено всі піддерева вузла 1, тепер настав час для відвідування вузла 1, після чого обхід завершується, оскільки пройдено все дерево.

Відвідується все дерево

Отже, порядок обходу вузлів такий 4 -> 5 -> 2 -> 6 -> 3 -> 1 .

Програма для впровадження Postorder Traversal бінарного дерева

Нижче наведено реалізацію коду обходу після замовлення:

C++

// C++ program for postorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> > int> data;> > struct> Node *left, *right;> > Node(> int> v)> > {> > data = v;> > left = right = NULL;> > }> };> // Function to print postorder traversal> void> printPostorder(> struct> Node* node)> {> > if> (node == NULL)> > return> ;> > // First recur on left subtree> > printPostorder(node->ліворуч);> > // Then recur on right subtree> > printPostorder(node->правильно);> > // Now deal with the node> >

cout ' '; } // Driver code int main() {  struct Node* root = new Node(1);  root->зліва = новий вузол (2);  root->right = новий вузол (3);  root->left->left = новий вузол(4);  root->left->right = новий вузол(5);  root->right->right = новий вузол (6);  // Виклик функції cout < < 'Postorder traversal of binary tree is: 
';  printPostorder(root);  return 0; }>

Java

// Java program for postorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> > int> data;> > Node left, right;> > Node(> int> v)> > {> > data = v;> > left = right => null> ;> > }> }> class> GFG {> > > // Function to print postorder traversal> > static> void> printPostorder(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.data +> ' '> );> > }> > // Driver code> > public> static> void> main(String[] args)> > {> > Node root => new> Node(> 1> );> > root.left => new> Node(> 2> );> > root.right => new> Node(> 3> );> > root.left.left => new> Node(> 4> );> > root.left.right => new> Node(> 5> );> > root.right.right => new> Node(> 6> );> > // Function call> > System.out.println(> 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by prasad264>

Python3

# Python program for postorder traversals> # Structure of a Binary Tree Node> class> Node:> > def> __init__(> self> , v):> > self> .data> => v> > self> .left> => None> > self> .right> => None> # Function to print postorder traversal> def> printPostorder(node):> > if> node> => => None> :> > return> > # First recur on left subtree> > printPostorder(node.left)> > # Then recur on right subtree> > printPostorder(node.right)> > # Now deal with the node> > print> (node.data, end> => ' '> )> # Driver code> if> __name__> => => '__main__'> :> > root> => Node(> 1> )> > root.left> => Node(> 2> )> > root.right> => Node(> 3> )> > root.left.left> => Node(> 4> )> > root.left.right> => Node(> 5> )> > root.right.right> => Node(> 6> )> > # Function call> > print> (> 'Postorder traversal of binary tree is:'> )> > printPostorder(root)>

C#

// C# program for postorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> > public> int> data;> > public> Node left, right;> > public> Node(> int> v)> > {> > data = v;> > left = right => null> ;> > }> }> public> class> GFG {> > // Function to print postorder traversal> > static> void> printPostorder(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.data +> ' '> );> > }> > static> public> void> Main()> > {> > // Code> > Node root => new> Node(1);> > root.left => new> Node(2);> > root.right => new> Node(3);> > root.left.left => new> Node(4);> > root.left.right => new> Node(5);> > root.right.right => new> Node(6);> > // Function call> > Console.WriteLine(> > 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by karthik.>

Javascript

// Structure of a Binary Tree Node> class Node {> > constructor(v) {> > this> .data = v;> > this> .left => null> ;> > this> .right => null> ;> > }> }> // Function to print postorder traversal> function> printPostorder(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.log(node.data +> ' '> );> }> // Driver code> function> main() {> > let root => new> Node(1);> > root.left => new> Node(2);> > root.right => new> Node(3);> > root.left.left => new> Node(4);> > root.left.right => new> Node(5);> > root.right.right => new> Node(6);> > // Function call> > console.log(>

'Postorder traversal of binary tree is: 
'>

);> > printPostorder(root);> }> main();>

Вихід

Postorder traversal of binary tree is: 4 5 2 6 3 1

Пояснення:

Як працює обхід замовлень поштою

Аналіз складності:

Часова складність: O(N), де N - загальна кількість вузлів. Тому що він проходить усі вузли принаймні один раз.
Допоміжний простір: O(1), якщо простір стеку рекурсії не розглядається. В іншому випадку O(h), де h — висота дерева

У гіршому випадку ч може бути таким же, як Н (коли дерево перекошене)
У кращому випадку ч може бути таким же, як спокійний (коли дерево є повним деревом)