Binary tree sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Pseudocode
This section needs your Code!
[edit] C Code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int RANGE = 200; //range for random numbers in the array
typedef enum {
FOUND,
NOT_FOUND
} SearchResult;
void initLookupTable(SearchResult lookup[], int array[], int sizeOfData, int RANGE)
{
int v;
for (int m = 0; m < RANGE; m++)
{
lookup[m] = NOT_FOUND;
}
for (int mm = 0; mm < sizeOfData; mm++)
{
v = array[mm];
lookup[v] = FOUND;
}
}
SearchResult searchLookupTable(SearchResult lookup[], int key)
{
return lookup[key];
}
void fill_array(int array[], int sizeOfData)
{
for (int i = 0; i < sizeOfData; i++)
{
array[i] = rand() % RANGE;
}
}
void print_array(int array[], int sizeOfData)
{
for (int j = 0; j < sizeOfData; j++)
{
printf("Item %d is %d\t", j, array[j]);
}
}
int main()
{
srand ( time (0) );
for (int ij=0; ij <100; ij++)
{
const int arraySize = 100;
int a [arraySize];
SearchResult lookup[RANGE];
SearchResult result;
int searchKey = rand() % RANGE;
fill_array(a, arraySize);
print_array(a, arraySize);
initLookupTable(lookup, a, arraySize, RANGE);
result = searchLookupTable(lookup, searchKey);
if (result == FOUND)
printf("\nKEY %d FOUND \n", searchKey);
else
printf("\nKEY %d NOT FOUND \n", searchKey);
}
return 0;
}
[edit] C++ Code
#include <iostream>
using namespace std;
class element //element
{
public:
int value;
element *next;
element()
{
value=NULL;
next=NULL;
}
};
class bucket //bucket containing a perticular range of values
{
public:
element *firstElement;
bucket()
{
firstElement = NULL;
}
};
void main()
{
int lowend=0; // minimum element
int highend=100; //max element
int interval=10; //number of intervals
const int noBuckets=(highend-lowend)/interval; //number of buckets required
bucket *buckets=new bucket[noBuckets];
bucket *temp;
for(int a=0;a<noBuckets;a++) //creation of required buckets
{
temp=new bucket;
buckets[a]=*temp;
}
cout<<"--------The Elements to be Sorted using Bucket sort are ------------------\n";
int array[]={12,2,22,33,44,55,66,77,85,87,81,83,89,82,88,86,84,88,99};
for(int j=0;j<19;j++) //sending elments into appropriate buckets
{
cout<<array[j]<<endl;
element *temp,*pre;
temp=buckets[array[j]/interval].firstElement;
if(temp==NULL)//if it is the first element of the bucket
{
temp=new element;
buckets[array[j]/interval].firstElement=temp;
temp->value=array[j];
}
else
{
pre=NULL;
while(temp!=NULL) {
if(temp->value>array[j])
break;
pre=temp;
temp=temp->next;
}
if(temp->value>array[j]) {
if(pre==NULL) {
element *firstNode;
firstNode=new element();
firstNode->value=array[j];
firstNode->next=temp;
buckets[array[j]/interval].firstElement=firstNode;
}
else //insertion at middle
{
element *firstNode;
firstNode=new element();
firstNode->value=array[j];
firstNode->next=temp;
pre->next=firstNode;
}
}
else// if the new value is to be created at last of bucket
{
temp=new element;
pre->next=temp;
temp->value=array[j];
}
}
}
cout<<"------------------------The Sorted Elements Are---------------\n";
for(int jk=0;jk<10;jk++)
{
element *temp;
temp= buckets[jk].firstElement;
while(temp!=NULL)
{
cout<<"*"<<temp->value<<endl;
temp=temp->next;
}
}
cout<<"--------------------------------END--------------------------------\n";
}
[edit] template
template <typename Type> class CBinTree; // for CNode and BinTree()
template<typename Type> inline
void BinTree(Type *pF, Type *pL)
{
CBinTree<Type> tree(pF);
for (Type *pI=pF-1; ++pI!=pL;) { tree.Insert(*pI); }
tree.InOrder();
}
//====================================================================
template <typename Type>
class CNode {
private: // Nobody can access
CNode(Type data) : m_data(data), m_pLeft(0), m_pRight(0) {}
~CNode() {}
friend class CBinTree<Type>; // Only CBinTree can access
private:
Type m_data;
CNode *m_pLeft;
CNode *m_pRight;
};
template <typename Type>
class CBinTree {
public:
typedef CNode<Type> *TPNode;
CBinTree(Type *pDest) : m_pRoot(0), m_pDest(pDest) {}
TPNode GetRoot() { return m_pRoot; }
void Visit(TPNode pNode) { *m_pDest++ = pNode->m_data; }
void Insert(Type data);
void InOrder(); // traverse : loop (user's stack)
void InOrder(TPNode pNode); // traverse : recursive
private:
TPNode m_pRoot;
Type *m_pDest;
};
template <typename Type> inline
void CBinTree<Type>::Insert(Type data)
{
TPNode pNewNode = new CNode<Type>(data);
TPNode pSearch = m_pRoot;
TPNode pParent = NULL;
while (pSearch != NULL) {
pParent = pSearch;
if (data < pSearch->m_data) { pSearch = pSearch->m_pLeft; }
else if (pSearch->m_data < data) { pSearch = pSearch->m_pRight; }
else { break; }
};
if (pParent == NULL) { m_pRoot = pNewNode; }
else if (data < pParent->m_data) { pParent->m_pLeft = pNewNode; }
else if (pParent->m_data < data) { pParent->m_pRight = pNewNode; }
else {
pNewNode->m_pLeft = pParent->m_pLeft;
pNewNode->m_pRight = NULL;
pParent->m_pLeft = pNewNode;
}
}
template <typename Type> inline
void CBinTree<Type>::InOrder() // traverse : loop (user's stack)
{
TPNode pNode = m_pRoot;
stack<TPNode> nodeStack;
do {
while (pNode != NULL) {
nodeStack.push(pNode);
pNode = pNode->m_pLeft;
}
if (!nodeStack.empty()) {
pNode = nodeStack.top();
nodeStack.pop();
Visit(pNode);
pNode = pNode->m_pRight;
} else {
break;
}
} while (1);
}
template <typename Type> inline
void CBinTree<Type>::InOrder(TPNode pNode) // traverse : recursive
{
if (pNode) {
InOrder(pNode->m_pLeft);
Visit(pNode);
InOrder(pNode->m_pRight);
}
}
[edit] PHP Code
This section needs your Code!
[edit] C# Code
This section needs your Code!
This section needs your Code!
[edit] VB Code
This section needs your Code!
[edit] Perl Code
This section needs your Code!
[edit] Prolog Code
This section needs your Code!
[edit] Python Code
<tlg>++
ypwrite+hello+
TLg?
(tlg++)
{
tlg+=write+rr+
}
[edit] Ruby Code
This section needs your Code!
