logo

TechCodeview

Методи обходу дерева – Навчальні посібники зі структури даних і алгоритмів

Техніка обходу дерева включають різні способи відвідування всіх вузлів дерева. На відміну від лінійних структур даних (масив, пов’язаний список, черги, стеки тощо), які мають лише один логічний шлях проходження, дерева можна проходити різними способами. У цій статті ми обговоримо всі методи обходу дерева та їх використання.



Зміст

Значення обходу дерева:

Обхід дерева відноситься до процесу відвідування або доступу до кожного вузла дерева точно один раз у певному порядку. Алгоритми обходу дерева допомагають нам відвідати та обробити всі вузли дерева. Оскільки дерево не є лінійною структурою даних, існує кілька вузлів, які ми можемо відвідати після відвідування певного вузла. Існує кілька методів обходу дерева, які визначають порядок відвідування вузлів дерева.

Методи обходу дерева:



Деревоподібну структуру даних можна обійти такими способами:

  • Пошук за глибиною або DFS
    • Обхід порядку
    • Обхід попереднього замовлення
    • Обхід поштових переказів
  • Обхід порядку рівня або пошук спочатку в ширину або BFS

Обхід порядку :

Обхід у порядку відвідує вузол у порядку: Ліворуч -> Корінь -> Праворуч




Алгоритм обходу порядку:

По порядку (дерево)

  • Перейти до лівого піддерева, тобто викликати Inorder(left->subtree)
  • Відвідайте корінь.
  • Перейти до правого піддерева, тобто викликати Inorder(right->subtree)

Використання Inorder Traversal:

  • У випадку бінарних дерев пошуку (BST) обхід за порядком дає вузли в порядку не спадання.
  • Щоб отримати вузли BST у незростаючому порядку, можна використовувати варіант обходу за порядком, де обхід за порядком є ​​зворотним.
  • Обхід у порядку можна використовувати для оцінки арифметичних виразів, що зберігаються в деревах виразів.

Фрагмент коду для обходу порядку:

C++ 
// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->ліворуч);  // Потім надрукувати дані вузла cout<< node->даних<< ' ';  // Now recur on right child  printInorder(node->праворуч); }>
C 
// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->ліворуч);  // Потім надрукувати дані вузла printf('%d ', node->data);  // Тепер повторюється праворуч printInorder(node->right); }>
Java 
void printInorder(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); }>
Python3 
# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>
C# 
// Given a binary tree, print // its nodes in inorder void printInorder(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); }>
Javascript 
// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Вихід 
Inorder traversal of binary tree is 4 2 5 1 3>

Часова складність: O(N)
Допоміжний простір: Якщо ми не враховуємо розмір стека для викликів функцій, тоді O(1), інакше O(h), де h – це висота дерева.

Обхід попереднього замовлення :

Обхід попереднього порядку відвідує вузол у порядку: Корінь -> Ліворуч -> Праворуч

Алгоритм обходу попереднього замовлення:

Попереднє замовлення (дерево)

  • Відвідайте корінь.
  • Перейти до лівого піддерева, тобто викликати Preorder(left->subtree)
  • Перейти до правого піддерева, тобто викликати Preorder(right->subtree)

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

  • Обхід попереднього замовлення використовується для створення копії дерева.
  • Обхід попереднього порядку також використовується для отримання префіксних виразів у дереві виразів.

Фрагмент коду для попереднього замовлення:

C++ 
// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->даних<< ' ';  // Then recur on left subtree  printPreorder(node->ліворуч);  // Тепер повторюється в правому піддереві printPreorder(node->right); }>
C 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->дані);  // Потім повторюємо ліве піддерево printPreorder(node->left);  // Тепер повторюється в правому піддереві printPreorder(node->right); }>
Java 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Python3 
# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>
C# 
// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Javascript 
// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Вихід 
Preorder traversal of binary tree is 1 2 4 5 3>

Часова складність: O(N)
Допоміжний простір: Якщо ми не враховуємо розмір стека для викликів функцій, тоді O(1), інакше O(h), де h – це висота дерева.

Обхід поштових переказів :

Обхід після замовлення відвідує вузол у порядку: Ліворуч -> Праворуч -> Корінь

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

окремий рядок у java

Алгоритм Поштовий переказ (дерево)

  • Перейти до лівого піддерева, тобто викликати Postorder(left->subtree)
  • Перейти до правого піддерева, тобто викликати Postorder(right->subtree)
  • Відвідайте корінь

Використання Mailorder Traversal:

  • Обхід після замовлення використовується для видалення дерева. Побачити питання про видалення дерева для деталей.
  • Постпорядковий обхід також корисний для отримання постфіксного виразу дерева виразів.
  • Обхід після замовлення може допомогти в алгоритмах збирання сміття, особливо в системах, де використовується ручне керування пам’яттю.

Фрагмент коду для обходу поштою:

C++ 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->ліворуч);  // Потім повторюється в правому піддереві printPostorder(node->right);  // Тепер розберемося з вузлом cout<< node->даних<< ' '; }>
C 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->ліворуч);  // Потім повторюється в правому піддереві printPostorder(node->right);  // Тепер розберемося з вузлом printf('%d ', node->data); }>
Java 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. 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.key + ' '); }>
Python3 
# A function to do postorder tree traversal def printPostorder(root): if root: # 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, end=' '),>
C# 
// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. 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.key + ' '); }>
Javascript 
// Given a binary tree, print its nodes according  // to the 'bottom-up' 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.key + ' '); }>
Вихід 
Postorder traversal of binary tree is 4 5 2 3 1>

Обхід порядку рівня :

Обхід порядку рівня повністю відвідує всі вузли, присутні на одному рівні, перш ніж відвідати наступний рівень.

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

LevelOrder(дерево)

  • Створіть порожню чергу Q
  • Поставте кореневий вузол дерева в Q
  • Цикл, поки Q не порожній
    • Видаліть вузол із Q і відвідайте його
    • Поставте в чергу лівий дочірній елемент вилученого з черги вузла, якщо він існує
    • Поставте в чергу правий дочірній елемент вилученого з черги вузла, якщо він існує

Використання рівня порядку:

  • Обхід рівня порядку в основному використовується як пошук у ширину для пошуку або обробки вузлів рівень за рівнем.
  • Обхід порядку рівня також використовується для Серіалізація та десеріалізація дерева .

Фрагмент коду для проходження порядку рівня:

C++ 
// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueq;  // Ставимо кореневу чергу та ініціалізуємо висоту q.push(root);  while (q.empty() == false) { // Роздрукувати початок черги та видалити його з черги Node* node = q.front();  cout<< node->даних<< ' ';  q.pop();  // Enqueue left child  if (node->зліва != NULL) q.push(node->left);  // Поставити в чергу правий дочірній елемент if (node->right != NULL) q.push(node->right);  } }>
C 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->дані);  // Поставити в чергу лівого дочірнього елемента if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Поставити в чергу правий дочірній елемент if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Зняти вузол із черги та зробити його temp_node temp_node = deQueue(queue, &front);  } }>
Java 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuequeue = новий LinkedList();  queue.add(корінь);  while (!queue.isEmpty()) { // poll() видаляє поточну голову.  Вузол tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Поставте в чергу лівого дочірнього елемента if (tempNode.left != null) { queue.add(tempNode.left);  } // Поставити в чергу правого дочірнього елемента if (tempNode.right != null) { queue.add(tempNode.right);  } } }>
Python3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Надрукувати початок черги та # видалити його з черги print(queue[0].data, end=' ') node = queue.pop(0) # Поставити в чергу лівого дочірнього елемента, якщо node.left не є None: queue.append(node.left) # Поставити правий дочірній елемент у чергу, якщо node.right не є None: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuequeue = нова черга();  queue.Enqueue(корінь);  while (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Поставити лівого дочірнього елемента в чергу if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Поставити в чергу правого дочірнього елемента if (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>
JavaScript 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Інші обходи дерев:

  1. Обхід кордону
  2. Діагональний обхід

1. Обхід кордону :

Обхід кордону дерева включає:

  • ліва межа (вузли ліворуч, за винятком листових вузлів)
  • листки (складаються тільки з листкових вузлів)
  • права межа (вузли справа, за винятком листових вузлів)

Алгоритм обходу межі:

Обхід границі (дерево)

  • Якщо корінь не нульовий:
    • Роздрукувати кореневі дані
    • PrintLeftBoundary(root->left) // Друк лівих граничних вузлів
    • PrintLeafNodes(root->left) // Друк листових вузлів лівого піддерева
    • PrintLeafNodes(root->right) // Друк листових вузлів правого піддерева
    • PrintRightBoundary(root->right) // Друк правих граничних вузлів

Використання обходу кордону:

  • Обхід межі допомагає візуалізувати зовнішню структуру бінарного дерева, надаючи розуміння його форми та меж.
  • Обхід межі надає спосіб отримати доступ до цих вузлів і змінити їх, уможливлюючи такі операції, як скорочення або зміна розташування граничних вузлів.

2. Діагональний обхід

У діагональному обході дерева всі вузли в одній діагоналі друкуватимуться один за одним.

Алгоритм діагонального обходу:

Діагональний обхід (дерево):

  • Якщо корінь не нульовий:
    • Створіть порожню карту
    • DiagonalTraversalUtil(root, 0, M) // Виклик допоміжної функції з початковим рівнем діагоналі 0
    • Для кожної пари ключ-значення (diagonalLevel, вузли) у M:
      • Для кожного вузла у вузлах:
      • Роздрукувати дані вузла

DiagonalTraversalUtil(вузол, diagonalLevel, M):

  • Якщо вузол нульовий:
  • Повернення
  • Якщо diagonalLevel відсутній у M:
    • Створіть новий список у M для diagonalLevel
  • Додайте дані вузла до списку на M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Обхід лівого дочірнього елемента зі збільшеним рівнем діагоналі
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Перехід праворуч дочірнього елемента з однаковим рівнем діагоналі

Використання діагонального обходу:

  • Діагональний обхід допомагає візуалізувати ієрархічну структуру бінарних дерев, зокрема в структурах даних на основі дерева, таких як бінарні дерева пошуку (BST) і дерева купи.
  • Діагональний обхід можна використовувати для обчислення суми шляхів уздовж діагоналей у бінарному дереві.

Часті запитання (FAQ) щодо методів обходу дерева:

1. Що таке методи обходу дерева?

Методи обходу дерева – це методи, які використовуються для відвідування та обробки всіх вузлів у структурі даних дерева. Вони дозволяють отримати доступ до кожного вузла рівно один раз систематично.

2. Які поширені типи обходу дерева?

Загальні типи обходу дерева: обхід за порядком, обхід попереднього порядку, обхід після порядку, обхід рівня рівня (пошук у ширину)

CSS вирівнювання зображень

3. Що таке обхід порядку?

Обхід у порядку — це метод обходу в глибину, де вузли відвідуються в порядку: ліве піддерево, поточний вузол, праве піддерево.

4. Що таке обхід попереднього замовлення?

Обхід попереднього порядку — це метод обходу в глибину, де вузли відвідуються в порядку: поточний вузол, ліве піддерево, праве піддерево.

5. Що таке обхід поштових переказів?

Обхід після порядку — це метод обходу в глибину, де вузли відвідуються в порядку: ліве піддерево, праве піддерево, поточний вузол.

6. Що таке обхід порядку рівня?

Обхід порядку рівнів, також відомий як пошук у ширину (BFS), відвідує вузли рівень за рівнем, починаючи з кореня та переходячи на наступний рівень, перш ніж переходити глибше.

7. Коли я повинен використовувати кожну техніку обходу?

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

Обхід попереднього замовлення корисний для створення копії дерева.

Обхід після порядку зазвичай використовується в деревах виразів для оцінки виразів.

Обхід порядку рівнів корисний для пошуку найкоротшого шляху між вузлами.

8. Як реалізувати алгоритми обходу дерева?

Алгоритми обходу дерева можуть бути реалізовані рекурсивно або ітераційно, залежно від конкретних вимог і мови програмування, що використовується.

9. Чи можна застосувати алгоритми обходу дерева до інших деревоподібних структур?

Так, алгоритми обходу дерева можна адаптувати для обходу інших деревоподібних структур, таких як бінарні купи, n-ічні дерева та графи, представлені у вигляді дерев.

10. Чи є якісь міркування щодо продуктивності при виборі техніки обходу?

Розгляд продуктивності залежить від таких факторів, як розмір і форма дерева, доступна пам'ять і конкретні операції, які виконуються під час обходу. Загалом, вибір техніки обходу може вплинути на ефективність певних операцій, тому важливо вибрати найбільш підходящий метод для конкретного випадку використання.

Деякі інші важливі посібники:

  • Підручник DSA
  • Підручник з проектування системи
  • Дорожня карта розробки програмного забезпечення
  • Дорожня карта, як стати менеджером із продуктів
  • Вивчіть SAP
  • Вивчіть SEO