实现笛卡尔树的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 好听的元旦简短祝福语