实现笛卡尔树的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 爱生日祝福语简短独特