นี่คือโปรแกรม C++ สำหรับการนำต้นไม้ค้นหาทวิภาคมาใช้งานโดยใช้รายการเชื่อมต่อ (Linked Lists)
ฟังก์ชันและ pseudocode
อัลกอริทึม
Begin รับโหนดของต้นไม้เป็นอินพุท สร้างโครงสร้าง nod เพื่อรับข้อมูล d, พอยน์เตอร์ซ้าย l และพอยน์เตอร์ขวา r เป็นอินพุท สร้างฟังก์ชัน create() เพื่อแทรกโหนดเข้าไปในต้นไม้: เริ่มต้น c = 0 เป็นจำนวนโหนด ทำลูป while จนกว่า c < 6: ป้อนรูท ป้อนค่าของโหนด ถ้ามากกว่ารูทให้แทรกทางขวา มิฉะนั้นทางซ้าย สร้างฟังก์ชัน inorder() เพื่อเดินทางโหนดแบบ inorder: Left – Root – Right สร้างฟังก์ชัน preorder() เพื่อเดินทางโหนดแบบ preorder: Root – Left – Right สร้างฟังก์ชัน postorder() เพื่อเดินทางโหนดแบบ postorder: Left – Right – Root จาก main() เรียกฟังก์ชันและพิมพ์ผลลัพธ์ End
ตัวอย่างโค้ด
#include <iostream> using namespace std; struct nod { nod *l, *r; int d; }*r = NULL, *p = NULL, *np = NULL, *q; void create() { int v,c = 0; while (c < 6) { if (r == NULL) { r = new nod; cout<<"enter value of root node\n"; cin>>r->d; r->r = NULL; r->l = NULL; } else { p = r; cout<<"enter value of node\n"; cin>>v; while(true) { if (v< p->d) { if (p->l == NULL) { p->l = new nod; p = p->l; p->d = v; p->l = NULL; p->r = NULL; cout<<"value entered in left\n"; break; } else if (p->l != NULL) { p = p->l; } } else if (v >p->d) { if (p->r == NULL) { p->r = new nod; p = p->r; p->d = v; p->l = NULL; p->r = NULL; cout<<"value entered in right\n"; break; } else if (p->r != NULL) { p = p->r; } } } } c++; } } void inorder(nod *p) { if (p != NULL) { inorder(p->l); cout<<p->d<<endl; inorder(p->r); } } void preorder(nod *p) { if (p != NULL) { cout<<p->d<<endl; preorder(p->l); preorder(p->r); } } void postorder(nod *p) { if (p != NULL) { postorder(p->l); postorder(p->r); cout<<p->d<<endl; } } int main() { create(); cout<<" traversal in inorder\n"; inorder(r); cout<<" traversal in preorder\n"; preorder(r); cout<<" traversal in postorder\n"; postorder(r); }
ผลลัพธ์
enter value of root node 7 enter value of node 6 value entered in left enter value of node 4 value entered in left enter value of node 3 value entered in left enter value of node 2 value entered in left enter value of node 1 value entered in left traversal in inorder 1 2 3 4 6 7 traversal in preorder 7 6 4 3 2 1 traversal in postorder 1 2 3 4 6 7
