实现笛卡尔树的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
热门推荐
10 白羊生日祝福语 简短独特
11 新年给妈妈简短祝福语
12 毕业贺卡老师祝福语简短
13 新年祝福语简短的个性
14 送礼祝福语男性生日简短
15 上司生日祝福语简短 女性
16 今年节日祝福语简短
17 发给导师的祝福语简短
18 生日祝福语简短激励女生