การสำรวจเส้นทางต้นไม้ (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