นี่คือโปรแกรม C++ สำหรับการนำการเดินทางแบบ Double Order (Double Order Traversal) ของต้นไม้ทวิภาคมาใช้งาน
ในการเดินทางแบบ Double Order รูทของต้นไม้ย่อยจะถูกเดินทางสองครั้ง
อัลกอริทึม
Begin คลาส BST มีฟังก์ชันต่อไปนี้: insert() = เพื่อแทรกไอเทมในต้นไม้: ป้อนรูท ป้อนค่าของโหนด ถ้ามากกว่ารูทให้แทรกทางขวา มิฉะนั้นทางซ้าย doubleOrder() = เพื่อทำ inorder: ถ้า root = null พิมพ์ tree is empty ถ้าไม่ ให้ทำ: เยี่ยมชมรูทของ (sub)tree เยี่ยมชมต้นไม้ย่อยทางซ้าย เยี่ยมชมรูทของ (sub)tree อีกครั้ง เยี่ยมชมต้นไม้ย่อยทางขวา End
ตัวอย่างโค้ด
# include <iostream> # include <cstdlib> using namespace std; struct nod//node declaration { int info; struct nod *l; struct nod *r; }*r; class BST { public://declaration of functions void insert(nod *, nod *); void doubleOrder(nod *); void show(nod *, int); BST() { r = NULL; } }; void BST::insert(nod *tree, nod *newnode) { if (r == NULL) { r = new nod; r->info = newnode->info; r->l = NULL; r->r = NULL; cout<<"Root Node is Added"<<endl; return; } if (tree->info == newnode->info) { cout<<"Element already in the tree"<<endl; return; } if (tree->info >newnode->info) { if (tree->l != NULL) { insert(tree->l, newnode); } else { tree->l= newnode; (tree->l)->l = NULL; (tree->l)->r= NULL; cout<<"Node Added To Left"<<endl; return; } } else { if (tree->r != NULL) { insert(tree->r, newnode); } else { tree->r = newnode; (tree->r)->l= NULL; (tree->r)->r = NULL; cout<<"Node Added To Right"<<endl; return; } } } void BST::doubleOrder(nod *ptr) { if (r == NULL) { cout << "Tree is empty" << endl; return; } if (ptr != NULL) { cout << ptr->info << " "; doubleOrder(ptr->l); cout << ptr->info << " "; doubleOrder(ptr->r); } } void BST::show(nod *ptr, int level)// print the tree { int i; if (ptr != NULL) { show(ptr->r, level + 1); cout << endl; if (ptr == r) cout << "Root->: "; else { for (i = 0; i < level; i++) cout << " "; } cout << ptr->info; show(ptr->l, level + 1); } } int main() { int c, n; BST bst; nod *t; while (1)//perform switch operation { cout << "1.Insert Element " << endl; cout << "2.Double-Order Traversal" << endl; cout << "3.Show" << endl; cout << "4.Quit" << endl; cout << "Enter your choice : "; cin >>c; switch (c)//perform switch operation { case 1: t = new nod; cout << "Enter the number to be inserted : "; cin >>t->info; bst.insert(r, t); break; case 2: cout << "Double-Order Traversal of BST:" << endl; bst.doubleOrder(r); cout << endl; break; case 3: cout << "Print BST:" << endl; bst.show(r, 1); cout << endl; break; case 4: exit(1); default: cout << "Wrong choice" << endl; } } }
ผลลัพธ์
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 7 Root Node is Added 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 6 Node Added To Left 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 4 Node Added To Left 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 2 Node Added To Left 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 10 Node Added To Right 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 3 Print BST: 10 Root->: 7 6 4 2 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 2 Double-Order Traversal of BST: 7 6 4 2 2 4 6 7 10 10 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 4
