การสำรวจเส้นทางต้นไม้ (Inorder, Preorder & Postorder) พร้อมตัวอย่าง

Tree Traversal คืออะไร?

ในโครงสร้างข้อมูลแบบต้นไม้ การสำรวจเส้นทางหมายถึงการเยี่ยมชมโหนดในลักษณะเฉพาะบางอย่าง การข้ามผ่านมี 2 ประเภท โดยทั่วไป การสำรวจประเภทนี้จะขึ้นอยู่กับแผนผังไบนารี ต้นไม้ไบนารีหมายความว่าแต่ละโหนดสามารถมีได้สูงสุด 2 โหนด

ต้นไม้ไบนารีเป็นโครงสร้างข้อมูลที่รู้จักกันดี นอกจากนี้ยังมีแผนผังการค้นหาแบบไบนารี (BST) การสำรวจประเภทนี้ใช้เพื่อวัตถุประสงค์ต่างๆ การข้ามลำดับระดับ ใช้สำหรับการคำนวณความลึกระหว่างสองโหนด มีต้นไม้อีกประเภทหนึ่งที่เรียกว่า “AVL” ซึ่งจำเป็นต้องคำนวณความสูงของโหนด เราสามารถแสดงไบนารีทรีในอาเรย์ได้ แต่สำหรับการเพิ่มประสิทธิภาพหน่วยความจำ เราจะใช้โครงสร้างและตัวชี้สำหรับอ้างอิงโหนดถัดไป

ประเภทของการข้ามต้นไม้

ตามที่เราได้กล่าวมา ต้นไม้ไบนารีตอนนี้เราจะพูดถึงการแวะผ่านแต่ละประเภท การข้ามผ่านมีสองประเภทขึ้นอยู่กับประเภท ก่อนหน้านี้เราได้กล่าวถึงความจำเป็นในการเรียงลำดับระดับหรือการสำรวจเส้นทางแบบกว้างก่อน ตอนนี้ การสำรวจเชิงลึกครั้งแรก เช่น ลำดับหลังถูกใช้สำหรับการลบโหนด (เราจะพูดถึงเรื่องนี้ในภายหลัง) ลำดับล่วงหน้าใช้สำหรับการคัดลอกไบนารีทรี และ "inorder" จะเคลื่อนผ่านทรีในลักษณะที่ไม่ลดลง

การสำรวจเส้นทางแบบกว้างครั้งแรก
การสำรวจเชิงลึกครั้งแรก
สั่งซื้อการข้ามผ่านล่วงหน้า
การข้ามผ่านหลังการสั่งซื้อ
การสัญจรไปมาตามลำดับ

การสำรวจเส้นทางแบบกว้างครั้งแรก

เรียกอีกอย่างว่าการท่องตามลำดับระดับ ลองพิจารณาต้นไม้ต่อไปนี้เพื่อสาธิตการท่องตามลำดับระดับ

ดังนั้นเราจะเริ่มจากโหนดรูท “1” มันจะถูกทำเครื่องหมายเป็นระดับ 1 จากนั้นอัลกอริธึมจะไปที่ลูกทั้งหมดของโหนดปัจจุบัน เราจะไปที่โหนด 2 และ 3 ทันที พวกเขาจะถูกทำเครื่องหมายเป็นระดับ 2

หลังจากนั้นเนื่องจากเรามี 2 โหนดในระดับ 2 เราก็จะไปเยี่ยมลูก ๆ ของพวกเขาด้วย เราจะไปที่ 5,6,8,7 และทำเครื่องหมายว่าเป็นระดับ 3 ต่อไปนี้ไม่ต้องพูดถึง

ระดับของโหนด = ระดับของโหนดหลัก + 1

ระดับ 1: 1

ระดับ 2: 2 3

ระดับ 3: 5 6 8 7

ใช้อัลกอริทึมที่คล้ายกันสำหรับ BFS (ค้นหาแบบกว้างก่อน).

นี่คือ Pseudocode สำหรับการข้ามลำดับระดับ:

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)

ต้นไม้ Bianry Traversal ตามลำดับ

มาดูตัวอย่างเหมือนเมื่อก่อนกัน ในการสำรวจประเภทนี้ อันดับแรกเราจะไปที่แผนผังย่อยด้านซ้าย จากนั้นไปที่รูท และหลังจากนั้นไปที่แผนผังย่อยด้านขวา เพื่อความสะดวกในการจำ เราสามารถพูดตามลำดับจากซ้าย-รูท-ขวาได้

สำหรับทรีทั้งหมด สมมติว่ารูทคือ 1 ตอนนี้อัลกอริทึมจะเป็นไปตามนี้:

ไปที่แผนผังย่อยด้านซ้ายของโหนด 1
โหนดปัจจุบันคือ 2 (เนื่องจากเป็นแผนผังย่อยด้านซ้ายของ 1)

ไปที่แผนผังย่อยด้านซ้ายของ 2 โหนดปัจจุบันจะเป็น 5 ในครั้งนี้
ย้ายไปที่ 5 โดยไม่มีลูก ดังนั้นโหนด 5 จะถูกทำเครื่องหมายว่าเยี่ยมชมแล้ว มันจะกลับไปที่โหนดหลัก ซึ่งก็คือ 2
เมื่อมีการเยี่ยมชมแผนผังย่อยด้านซ้ายของ 2 ตอนนี้จะมีการเยี่ยมชม 2 รายการเช่นกัน
เค้ก ขั้นตอนวิธี จะย้ายโหนดปัจจุบันไปยังแผนผังย่อยด้านขวาของโหนด 2 ซึ่งก็คือโหนด 6 หลังจากเยี่ยมชมโหนด 6 แล้ว มันจะย้ายไปยังโหนดแม่ 2
เมื่อมีการเยี่ยมชมโหนด 2 ตอนนี้เราจะไปเยี่ยมชมพาเรนต์ของ 2; ซึ่งเป็นโหนด 1
หลังจากนั้นเราจะไปที่แผนผังย่อยที่ถูกต้อง

ดังนั้นการแวะผ่านครั้งสุดท้ายจะมีลักษณะดังนี้:

ตามลำดับ: 5 → 2 → 6 → 1 → 8 → 3 → 7

นี่คือ Pseudocode สำหรับการข้ามผ่านตามลำดับ:

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

นี่คืออัลกอริธึมแบบเรียกซ้ำสำหรับการข้ามผ่านตามลำดับ สำหรับ แผนผังการค้นหาแบบไบนารี (BST)การข้ามผ่านตามลำดับจะให้อาร์เรย์ของค่าที่เรียงลำดับแล้ว

การข้ามผ่านคำสั่งซื้อภายหลัง

ในการสำรวจครั้งนี้ เราจะสำรวจทรีย่อยซ้ายสุดก่อน จากนั้นจึงสำรวจทรีย่อยขวาสุดหลังราก การสำรวจทั้งหมดจะอยู่ในสถานะ Post-Order เรามาสาธิตตัวอย่างกัน:

ที่นี่สำหรับรูท = 1

เราจะไปที่ทรีย่อยด้านซ้ายก่อน ดังนั้นรากจะกลายเป็น 2
จากนั้น 2 ออกจากแผนผังย่อย ดังนั้นเราจะไปที่โหนด 5 ตอนนี้รากคือ 5
ไม่มีแผนผังย่อยด้านซ้าย และไม่มีแผนผังย่อยด้านขวาด้วย ดังนั้น ตอนนี้เราจะทำเครื่องหมายโหนด 5 ว่าเยี่ยมชมแล้ว และเราจะไปที่โหนดแม่ของมัน

ตอนนี้รูทคือ 2 และทรีย่อยด้านซ้ายถูกเยี่ยมชมโดยสมบูรณ์ ตอนนี้เราจะย้ายไปที่แผนผังย่อยด้านขวา ดังนั้นรากจึงกลายเป็น 6
เนื่องจากโหนด 6 ไม่มีแผนผังย่อยด้านซ้ายและขวา เราจะทำเครื่องหมายโหนด 6 ที่เยี่ยมชมและย้ายไปยังโหนดแม่ 2
ตอนนี้ทั้งทรีย่อยด้านซ้ายและขวากำลังถูกเยี่ยมชมสำหรับโหนด 2 และจะถูกทำเครื่องหมายว่าเยี่ยมชมแล้วเช่นกัน
เราจะย้ายไปยังพาเรนต์ของโหนด 2 ซึ่งก็คือโหนด 1
ทรีย่อยด้านซ้ายถูกเยี่ยมชมสำหรับรูท 1 ตอนนี้เราจะไปที่ทรีย่อยด้านขวาในทำนองเดียวกัน

วงกลมที่ทำเครื่องหมายไว้คือแผนผังย่อยด้านขวา ตอนนี้เราจะไปที่แผนผังย่อยด้านขวาเมื่อเราไปที่แผนผังย่อยด้านซ้าย หลังจากนั้นเราจะไปเยี่ยมชมโหนด ดังนั้นการแวะผ่านครั้งสุดท้ายจะเป็นดังนี้:

ลำดับหลัง: 5 → 6 → 2 → 8 → 7 → 3 → 1

นี่คือ Pseudocode สำหรับการแวะผ่านหลังการสั่งซื้อ:

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

สั่งซื้อล่วงหน้า

สำหรับการแวะผ่านการสั่งซื้อล่วงหน้า อัลกอริธึมจะไปที่โหนดรูทก่อน หลังจากนั้นจะย้ายไปที่ทรีย่อยด้านซ้ายและขวาตามลำดับ เพื่อความสะดวกในการทำความเข้าใจ เราสามารถนึกถึงการสั่งซื้อการแวะเยี่ยมชมล่วงหน้าได้ เช่น รูต → ซ้าย-ขวา

ดังนั้น เรามาเลือกโหนด 1 เป็นรูทกันดีกว่า

ตามอัลกอริธึม รูทจะถูกค้นพบก่อน จากนั้นไปทางซ้าย และทรีย่อยทางขวา
เราจะไปที่รูท 1 จากนั้นเราจะย้ายไปที่แผนผังย่อยด้านซ้าย รากกลายเป็น 2
เราจะไปที่โหนด 2 และย้ายไปที่แผนผังย่อยด้านซ้าย ดังนั้นรากจึงกลายเป็น 3
เราไปที่โหนด 3 จากนั้นเราจะย้ายไปยังโหนดแม่ ตอนนี้มีการเยี่ยมชมโหนด 2 และทรีย่อยด้านซ้ายแล้ว ถึงเวลาเยี่ยมชมทรีย่อยที่ถูกต้อง
เราจะย้ายไปยังแผนผังย่อยด้านขวา รากจะกลายเป็น 4 เราจะไปที่ 4 เนื่องจาก 4 ไม่มีโหนดย่อย เราจะย้ายไปยังโหนดแม่
ตอนนี้รูทคือ 2 และมีการเยี่ยมชมพร้อมกับทรีย่อยด้านซ้ายและขวา ดังนั้นเราจะย้ายไปยังโหนดแม่ ตอนนี้รูตกลายเป็น 1
ในทำนองเดียวกัน เราจะไปที่แผนผังย่อยที่ถูกต้อง

สั่งซื้อล่วงหน้า: 1 → 2 → 3 → 4 → 5 → 6 → 7

นี่คือ Pseudocode สำหรับการแวะผ่านหลังการสั่งซื้อ:

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

การนำไปปฏิบัติใน 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)

Output:

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

การนำไปใช้ใน 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);
}

เอาท์พุต:

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

การนำไปใช้งาน C++ (การใช้ std:queue เพื่อเรียงลำดับระดับ)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// 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);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new 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("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

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