实现笛卡尔树的C ++程序
这是实现笛卡尔树的C++程序。
算法
Begin
class CarTree to declare the functions:
min() = To find index of the minimum element in array:
if (arr[i] < min)
min = arr[i]
minind = i
inorder() = For inorder traversal of the tree:
If tree is empty
Then return
inorder (node->l)
Print the root as 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