Data Structure: Implementing Tree Sort in C++
In tree sort, the given data is first converted into a binary tree. The inorder traversal of the binary tree results in the sorted form which is known as tree sort.
Algorithm
1. Declare and initialize necessary variables.
2. Input the array of element to be sorted from the user.
3. Make a binary tree of the elements.
4. Traverse the binary tree using inorder traversal.
5. Display the result which are in sorted form
Source Codes
#include
using namespace std;
struct tree{
int info;
tree *Left, *Right;
};
tree *root;
class TreeSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit();
void insert1(int);
tree *insert2(tree *, tree *);
void display(tree *);
};
void TreeSort::getarray(){
coutHow many elements? ";
cin>>no_of_elements;
coutInsert array of element to sort: ";
for(int i=0;i
cin>>elements[i];
}
}
void TreeSort::sortit(){
for(int i = 0; i
insert1(elements[i]);
}
}
tree* TreeSort::insert2(tree *temp,tree *newnode){
if(temp==NULL){
temp=newnode;
}
else if(temp->info info){
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else{
insert2(temp->Left,newnode);
if(temp->Left==NULL)
temp->Left=newnode;
}
return temp;
}
void TreeSort::insert1(int n){
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}
/* Inorder traversal */
void TreeSort::display(tree *t = root){
if(root==NULL){
coutNothing to display";
}else
if(t!=NULL){
display(t->Left);
coutinfo ";
display(t->Right);
}
}
int main(){
TreeSort TS;
TS.getarray();
TS.sortit();
TS.display();
return 0;
}
Output
How many elements? 5
Insert array of element to sort: 85 53 26 98 77
26 53 77 85 98