Traversal cây (Thứ tự, Thứ tự trước & Thứ tự sau) với các ví dụ

Truyền tải cây là gì?

Trong cấu trúc dữ liệu cây, truyền tải có nghĩa là truy cập các nút theo một cách cụ thể nào đó. Có các nút2 kiểu truyền tải. Nói chung, kiểu duyệt này dựa trên cây nhị phân. Cây nhị phân có nghĩa là mỗi nút có thể có tối đa 2 nút.

Cây nhị phân là một cấu trúc dữ liệu nổi tiếng. Ngoài ra còn có cây tìm kiếm nhị phân (BST). Kiểu truyền tải này được sử dụng cho nhiều mục đích khác nhau. Truyền tải thứ tự cấp độ, nó được sử dụng để tính toán độ sâu giữa hai nút. Có một loại cây khác tên là “AVL”, trong đó việc tính toán chiều cao của nút là cần thiết. Chúng ta có thể biểu thị cây nhị phân trong mảng, nhưng để tối ưu hóa bộ nhớ, chúng ta sẽ sử dụng cấu trúc và con trỏ để tham chiếu nút tiếp theo.

Các kiểu duyệt cây

Như chúng ta đã thảo luận cây nhị phân, bây giờ chúng ta thảo luận về các kiểu duyệt riêng lẻ. Tùy thuộc vào loại, có hai loại truyền tải. Trước đây chúng tôi đã đề cập đến sự cần thiết của thứ tự cấp độ hoặc Truyền tải theo chiều rộng đầu tiên. Hiện nay Truyền tải theo chiều sâu đầu tiên giống như lệnh post được sử dụng để xóa một nút (chúng ta sẽ thảo luận sau), lệnh preorder được sử dụng để sao chép một cây nhị phân và lệnh inorder sẽ duyệt cây theo cách không giảm.

Truyền tải theo chiều rộng đầu tiên
Truyền tải theo chiều sâu đầu tiên
Truyền tải đặt hàng trước
Truyền tải sau đơn hàng
Truyền tải theo thứ tự

Truyền tải theo chiều rộng đầu tiên

Nó còn được gọi là duyệt theo thứ tự mức. Chúng ta hãy xem xét cây sau để minh họa cho duyệt theo thứ tự mức.

Vì vậy, chúng ta sẽ bắt đầu từ nút gốc “1”. Nó sẽ được đánh dấu là cấp 1. Sau đó, thuật toán sẽ đi đến tất cả các nút con của nút hiện tại. Bây giờ chúng ta sẽ truy cập nút 2 và 3. Họ sẽ được đánh dấu là cấp 2.

Sau đó, vì chúng tôi có 2 nút ở cấp 2 nên chúng tôi cũng sẽ đến thăm con của họ. Vì vậy, chúng ta sẽ truy cập 5,6,8,7 và đánh dấu chúng là cấp 3. Đây là một điều không được đề cập,

Cấp độ của nút = cấp độ của nút cha + 1

Cấp độ 1: 1

Cấp 2: 2 3

Cấp độ 3: 5 6 8 7

Một thuật toán tương tự được sử dụng cho BFS (Tìm kiếm theo chiều rộng đầu tiên).

Đây là Mã giả để truyền tải thứ tự cấp độ:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Cây Bianry truyền tải thứ tự

Hãy lấy ví dụ tương tự như trước đây. Trong kiểu truyền tải này, trước tiên chúng ta thăm cây con bên trái, sau đó là gốc và sau đó là cây con bên phải. Để dễ nhớ, chúng ta có thể nói theo thứ tự như trái-gốc-phải.

Đối với toàn bộ cây, giả sử gốc là 1. Bây giờ thuật toán sẽ tuân theo:

Thăm cây con bên trái của nút 1.
Nút hiện tại là 2 (vì nó là cây con bên trái của 1)

Thăm cây con bên trái của 2. Nút hiện tại lần này sẽ là 5.
Di chuyển đến 5, nó không có nút con nên nút 5 sẽ được đánh dấu là đã truy cập. Nó sẽ trở về nút cha; đó là 2.
Vì cây con bên trái của 2 đã được thăm nên bây giờ cây con 2 cũng sẽ được thăm.
thuật toán sẽ di chuyển nút hiện tại sang cây con bên phải của nút 2, đó là nút 6. Sau khi truy cập nút 6. Nó sẽ di chuyển đến nút cha 2.
Khi nút 2 được truy cập, bây giờ chúng ta sẽ truy cập nút cha của 2; đó là nút 1.
Sau đó, chúng ta sẽ thăm cây con bên phải.

Vì vậy, quá trình truyền tải cuối cùng sẽ trông như thế này:

Theo thứ tự: 5 → 2 → 6 → 1 → 8 → 3 → 7

Đây là Mã giả để truyền tải theo thứ tự:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Đây là thuật toán đệ quy cho việc duyệt theo thứ tự. Cho Cây tìm kiếm nhị phân (BST), Truyền tải theo thứ tự đưa ra mảng các giá trị đã được sắp xếp.

Truyền tải sau đơn hàng

Trong lần duyệt này, chúng ta sẽ duyệt cây con ngoài cùng bên trái trước, sau đó là cây con ngoài cùng bên phải sau gốc. Tất cả các quá trình duyệt sẽ ở dạng Đặt hàng sau. Hãy chứng minh một ví dụ:

Ở đây cho root = 1,

Đầu tiên chúng ta sẽ đi đến cây con bên trái. Vì vậy gốc sẽ trở thành 2.
Khi đó 2 có cây con bên trái nên chúng ta sẽ chuyển sang nút 5. Bây giờ gốc là 5.
Nó không có cây con bên trái và cũng không có cây con bên phải. Vì vậy, bây giờ chúng ta sẽ đánh dấu nút 5 là đã truy cập và chúng ta sẽ đi đến nút cha của nó.

Bây giờ gốc là 2 và cây con bên trái của nó đã được thăm hoàn toàn. Bây giờ chúng ta sẽ chuyển sang cây con bên phải của nó. Vì vậy, gốc trở thành 6.
Vì nút 6 không có cây con trái và phải, chúng tôi sẽ đánh dấu nút 6 đã truy cập và chuyển đến nút cha 2 của nó.
Bây giờ, cả cây con bên trái và bên phải đều đang được truy cập cho nút 2. Nó cũng sẽ được đánh dấu là đã truy cập.
Chúng ta sẽ chuyển sang nút cha của nút 2, tức là nút 1.
Cây con bên trái được thăm cho gốc 1. Bây giờ tương tự, chúng ta sẽ thăm cây con bên phải.

Vòng tròn được đánh dấu là cây con bên phải. Bây giờ chúng ta sẽ thăm cây con bên phải giống như chúng ta đã thăm cây con bên trái. Sau đó, chúng ta sẽ truy cập vào nút. Vì vậy, lần duyệt cuối cùng sẽ là:

Đặt hàng sau: 5 → 6 → 2 → 8 → 7 → 3 → 1

Đây là Mã giả để truyền tải đơn hàng sau:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Truyền tải đặt hàng trước

Đối với việc duyệt theo thứ tự trước, thuật toán sẽ truy cập nút gốc trước, sau đó sẽ di chuyển tương ứng sang cây con trái và cây con phải. Để dễ hiểu, chúng ta có thể nghĩ về các lượt truy cập duyệt qua đặt hàng trước như gốc → trái-phải.

Vì vậy, hãy chọn nút 1 làm nút gốc.

Theo thuật toán, gốc sẽ được tìm ra trước, sau đó là cây con bên trái và sau đó là cây con bên phải.
Vì vậy, chúng ta sẽ thăm gốc 1. Sau đó chúng ta sẽ chuyển sang cây con bên trái của nó. Gốc trở thành 2.
Chúng ta sẽ ghé thăm nút 2 và chuyển sang cây con bên trái của nó. Vì vậy, gốc trở thành 3.
Chúng ta truy cập nút 3, sau đó chuyển đến nút cha của nó. Bây giờ nút 2 và cây con bên trái của nó đã được truy cập. Đã đến lúc truy cập vào cây con bên phải.
Chúng ta sẽ chuyển sang cây con bên phải, gốc trở thành 4. Chúng ta sẽ truy cập 4. Vì 4 không có nút con nên chúng ta sẽ chuyển đến nút cha của nó.
Bây giờ gốc là 2 và nó được truy cập cùng với cây con trái và phải của nó. Vì vậy, chúng ta sẽ chuyển đến nút cha của nó. Bây giờ root trở thành 1.
Tương tự, chúng ta sẽ thăm cây con bên phải.

Đặt hàng trước: 1 → 2 → 3 → 4 → 5 → 6 → 7

Đây là Mã giả để truyền tải đơn hàng sau:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Triển khai tại Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Đầu ra:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Thực hiện trong C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}