การข้ามต้นไม้เป็นรูปแบบหนึ่งของการข้ามผ่านกราฟ มันเกี่ยวข้องกับการตรวจสอบหรือพิมพ์แต่ละโหนดในทรีเพียงครั้งเดียว การข้ามผ่านของการสั่งซื้อล่วงหน้าของทรีการค้นหาแบบไบนารีเกี่ยวข้องกับการเยี่ยมชมแต่ละโหนดในทรีตามลำดับ (ราก ซ้าย ขวา)
ตัวอย่างการสั่งผ่านแบบพรีออร์เดอร์ของไบนารีทรีมีดังนี้
ต้นไม้ไบนารีจะได้รับดังนี้
การสั่งซื้อล่วงหน้าคือ:6 4 1 5 8
โปรแกรมสำหรับสั่งจองล่วงหน้าแบบเรียกซ้ำมีดังต่อไปนี้
ตัวอย่าง
#include<iostream> using namespace std; struct node { int data; struct node *left; struct node *right; }; struct node *createNode(int val) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->data = val; temp->left = temp->right = NULL; return temp; } void preorder(struct node *root) { if (root != NULL) { cout<<root->data<<" "; preorder(root->left); preorder(root->right); } } struct node* insertNode(struct node* node, int val) { if (node == NULL) return createNode(val); if (val < node->data) node->left = insertNode(node->left, val); else if (val > node->data) node->right = insertNode(node->right, val); return node; } int main() { struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3); cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root); return 0; }
ผลลัพธ์
Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 5 9
ในโปรแกรมข้างต้น โครงสร้างโหนดจะสร้างโหนดของต้นไม้ โครงสร้างนี้เป็นโครงสร้างอ้างอิงตนเอง เนื่องจากมีตัวชี้ประเภทโหนดโครงสร้าง โครงสร้างนี้แสดงไว้ดังนี้
struct node { int data; struct node *left; struct node *right; };
ฟังก์ชัน createNode() สร้างโหนดชั่วคราวและจัดสรรหน่วยความจำโดยใช้ malloc ค่าข้อมูลจะถูกเก็บไว้ในข้อมูลของอุณหภูมิ NULL ถูกเก็บไว้ในพอยน์เตอร์ของอุณหภูมิด้านซ้ายและขวา สิ่งนี้แสดงให้เห็นโดยข้อมูลโค้ดต่อไปนี้
struct node *createNode(int val) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->data = val; temp->left = temp->right = NULL; return temp; }
ฟังก์ชั่น preorder() รับรูทของไบนารีทรีเป็นอาร์กิวเมนต์และพิมพ์องค์ประกอบของทรีในการสั่งซื้อล่วงหน้า เป็นฟังก์ชันแบบเรียกซ้ำ มันแสดงให้เห็นโดยใช้รหัสต่อไปนี้
void preorder(struct node *root) { if (root != NULL) { cout<<root-->data<<" "; preorder(root-->left); preorder(root-->right); } }
ฟังก์ชัน insertNode() แทรกค่าที่ต้องการลงในไบนารีทรีในตำแหน่งที่ถูกต้อง หากโหนดเป็น NULL ระบบจะเรียก createNode มิฉะนั้น จะพบตำแหน่งที่ถูกต้องสำหรับโหนดในแผนผัง ซึ่งสังเกตได้จากข้อมูลโค้ดต่อไปนี้
struct node* insertNode(struct node* node, int val) { if (node == NULL) return createNode(val); if (val < node->data) node->left = insertNode(node->left, val); else if (val > node->data) node-->right = insertNode(node-->right, val); return node; }
ในฟังก์ชัน main() โหนดรูทจะถูกกำหนดเป็น NULL ก่อน จากนั้นโหนดทั้งหมดที่มีค่าที่จำเป็นจะถูกแทรกลงในแผนผังการค้นหาแบบไบนารี ดังแสดงด้านล่าง
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
สุดท้าย ฟังก์ชัน preorder() จะถูกเรียกใช้โดยใช้โหนดรูทของทรี และค่าทรีทั้งหมดจะแสดงในการสั่งซื้อล่วงหน้า ด้านล่างนี้
cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root);