นี่คือโปรแกรม C++ สำหรับการนำต้นไม้คาร์ทีเซียน (Cartesian Tree) มาใช้งาน
อัลกอริทึม
Begin คลาส CarTree ประกาศฟังก์ชัน: min() = เพื่อหาดัชนีขององค์ประกอบที่น้อยที่สุดในอาร์เรย์: if (arr[i] < min) min = arr[i] minind = i inorder() = สำหรับการเดินทาง inorder ของต้นไม้: ถ้าต้นไม้ว่าง คืนค่า inorder (node->l) พิมพ์รูทเป็น node->d inorder (node->r) End
ตัวอย่างโค้ด
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; struct nod//node declaration { int d; struct nod* l; struct nod* r; }; class CarTree { public://declare the functions nod *newNode (int); int min(int [], int, int); nod *buildTree (int [], int, int); void inorder (nod* node); void show(nod *, int); CTree() {} }; int CarTree::min(int arr[], int s, int e) { int i, min = arr[s], minind = s; for (i = s + 1; i <= e; i++) { if (arr[i] < min) { min = arr[i]; minind = i; } } return minind; } nod *CarTree::buildTree (int inorder[], int s, int e)//build the cratesian tree { if (s >e) return NULL; int i = min(inorder, s, e); nod *r = newNode(inorder[i]); if (s == e) return r; r->l = buildTree(inorder, s, i - 1);//call the function recursively for left child r->r = buildTree(inorder, i + 1, e);//call the function recursively for right child return r; } void CarTree::inorder (struct nod* node) { if (node == NULL) return; inorder (node->l); cout<<node->d<<" "; inorder (node->r); } void CarTree::show(nod *ptr, int level)//show the tree { int i; if(ptr == NULL) return; if (ptr != NULL) { show(ptr->r, level + 1); cout<<endl; for (i = 0;i < level;i++) cout<<" "; cout<<ptr->d; show(ptr->l, level + 1); } } nod *CarTree::newNode (int d)//creation of new node { nod* t = new nod; t->d = d; t->l = NULL; t->r = NULL; return t; } int main() { CarTree ct; int i, n; cout<<"Enter number of elements to be inserted: "; cin>>n; int a[n]; for (i = 0; i < n; i++) { cout<<"Enter Element "<<i + 1<<" : "; cin>>a[i]; } nod *r = ct.buildTree(a, 0, n - 1); cout<<"Cartesian tree Structure: "<<endl; ct.show(r,1); cout<<endl; cout<<"\n Inorder traversal of the tree \n"<<endl; ct.inorder(r); cout<<endl; return 0; }
ผลลัพธ์
Enter number of elements to be inserted: 10 Enter Element 1 : 10 Enter Element 2 : 30 Enter Element 3 : 20 Enter Element 4 : 40 Enter Element 5 : 50 Enter Element 6 : 70 Enter Element 7 : 60 Enter Element 8 : 80 Enter Element 9 : 100 Enter Element 10 : 112 Cartesian tree Structure: 112 100 80 60 70 50 40 20 30 10 Inorder traversal of the tree 10 30 20 40 50 70 60 80 100 112
