Binary Tree Traversals ในโครงสร้างข้อมูล

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

สมมติว่าเรามีต้นไม้ต้นหนึ่งแบบนี้ -

ลำดับการข้ามผ่านของ Inorder จะเป็นเช่น − 5 8 10 15 16 20 23

ลำดับการสั่งจองล่วงหน้าจะเป็นเช่น − 10 5 8 16 15 20 23

ลำดับการข้ามผ่านของ Postorder จะเป็นเช่น − 8 5 15 23 20 16 10

ลำดับการข้ามผ่านระดับจะเป็น − 10, 5, 16, 8, 15, 20, 23

อัลกอริทึม

inorderTraverse(root):เริ่มต้นถ้ารูทไม่ว่าง จากนั้น inorderTraversal(ซ้ายของรูท) พิมพ์ค่าของรูท inorderTraversal(ทางขวาของรูท) end ifEndpreorderTraverse(root):Begin ถ้ารูทไม่ว่าง จากนั้นพิมพ์ค่า ของรูท preorderTraversal(ซ้ายของรูท) preorderTraversal(ทางขวาของรูท) สิ้นสุด ifEndpostorderTraverse(root):เริ่มต้นหากรูทไม่ว่าง จากนั้น postorderTraversal(ซ้ายของรูท) postorderTraversal(ทางขวาของรูท) พิมพ์ค่าของรูท end ifEndlevelOrderTraverse(root) :เริ่มต้นกำหนดคิว que เพื่อเก็บโหนดที่แทรกรูทลงใน que ในขณะที่ que ไม่ว่างเปล่า do item :=item present at front position of queue พิมพ์ค่าของ item if left of item is not null จากนั้นแทรกด้านซ้ายของ item ลงใน que end ถ้าถ้าทางขวาของไอเท็มไม่เป็น null แล้ว แทรกด้านขวาของรายการใน que end หากลบองค์ประกอบด้านหน้าออกจาก que doneEnd

ตัวอย่าง

#include#includeusing เนมสเปซ std;โหนดคลาส{ สาธารณะ:int h_left, h_right, bf, ค่า; โหนด * ซ้าย * ขวา;}; คลาสทรี { ส่วนตัว:โหนด *get_node (คีย์ int); สาธารณะ:โหนด * รูท; ต้นไม้ () { ราก =NULL; //ตั้งค่ารูทเป็น NULL ที่จุดเริ่มต้น } void inorder_traversal(โหนด *r); ถือเป็นโมฆะ preorder_traversal(โหนด *r); เป็นโมฆะ postorder_traversal(โหนด *r); เป็นโมฆะ levelorder_traversal(โหนด *r); โหนด *insert_node (โหนด * รูท, คีย์ int);}; โหนด * tree::get_node (คีย์ int) { โหนด * new_node; new_node =โหนดใหม่; //สร้างโหนดใหม่แบบไดนามิก new_node->h_left =0; new_node->h_right =0; new_node->bf =0; new_node->value =คีย์; //เก็บค่าจากคีย์ที่กำหนด new_node->left =NULL; new_node->right =NULL; return new_node;}void tree::inorder_traversal(node ​​*r){ if(r !=NULL){ //เมื่อมีรูท เข้าไปที่ left - root - right inorder_traversal(r->left); ศาล <ค่า <<" "; inorder_traversal(r->ขวา); }} void tree::preorder_traversal(node ​​*r){ if(r !=NULL){ //เมื่อมีรูทอยู่ ให้ไปที่ left - root - right cout <value <<" "; preorder_traversal(r->ซ้าย); preorder_traversal(r->ขวา); }} void tree::postorder_traversal(node ​​*r){ if(r !=NULL){ //เมื่อมีรูท ให้ไปที่ left - root - right postorder_traversal(r->left); postorder_traversal(r->ขวา); ศาล <ค่า <<" "; }} void tree::levelorder_traversal(node ​​*root){ คิว  que; โหนด *รายการ; que.push(ราก); // ใส่รูทในตอนแรกในขณะที่ (!que.empty()){ item =que.front(); // รับองค์ประกอบจากส่วนหน้า cout <value <<" "; if(item->left !=NULL) //เมื่อลูกเหลืออยู่ ให้ใส่คิว que.push(item->left); if(item->right !=NULL) //เมื่อมีลูกที่ถูกต้อง ให้ใส่คิว que.push(item->right); que.pop(); //ลบรายการออกจากคิว }}โหนด *tree::insert_node(โหนด *root, คีย์ int){ if(root ==NULL){ return (get_node(key)); //เมื่อต้นไม้ว่าง ให้สร้างโหนดเป็นรูท } if(key value){ //เมื่อคีย์น้อยกว่าค่ารูท ให้ไปที่ root->left =insert_node(root->left, key ); } else if(key> root->value){ //เมื่อคีย์มากกว่าค่ารูท ไปที่ root->right =insert_node(root->right, key); } ส่งคืนรูท; //เมื่อมีคีย์อยู่แล้ว ห้ามใส่คีย์นั้นอีก}main(){ โหนด *root; ต้นไม้ my_tree; //ใส่กุญแจเข้าไปในต้นไม้ my_tree.root =my_tree.insert_node (my_tree.root, 10); my_tree.root =my_tree.insert_node (my_tree.root, 5); my_tree.root =my_tree.insert_node (my_tree.root, 16); my_tree.root =my_tree.insert_node (my_tree.root, 20); my_tree.root =my_tree.insert_node (my_tree.root, 15); my_tree.root =my_tree.insert_node (my_tree.root, 8); my_tree.root =my_tree.insert_node (my_tree.root, 23); cout <<"In-Order Traversal:"; my_tree.inorder_traversal(my_tree.root); cout <<"\nPre-Order Traversal:"; my_tree.preorder_traversal(my_tree.root); cout <<"\nPost-Order Traversal:"; my_tree.postorder_traversal(my_tree.root); cout <<"\nLevel-Order Traversal:"; my_tree.levelorder_traversal(my_tree.root);}

ผลลัพธ์

In-Order Traversal:5 8 10 15 16 20 23Pre-Order Traversal:10 5 8 16 15 20 23Post-Order Traversal:8 5 15 23 20 16 10Level-Order Traversal:10 5 16 8 15 20 23