Some knowledge of C++ (and maybe data structures) is needed for reading this section.
This is a C++ class teplate which I created for my data structures class. It is used for sorting any abstract data type.
A binary tree is a structure which is either empty or contains a node, who's elements are a datum, a pointer to a left sub-tree, and a pointer to a right sub-tree. Each of the left and right sub-trees are themselves binary trees.
In this binary tree, anything in the left sub-tree of a node X is said to be "less than" the value of the datum in node X. Likewise, anything in the right sub-tree of the node X is said to be "greater than or equal to" the value of the datum in node X.
In this way, the data contained within the binary tree is sorted, and can be read in an ordered pattern.
Binary trees are very fast structures, assuming that the data being stored into it is in a rather randomized state. It only performs well when the data is not already partially or fully ordered.
The other downfall to binary trees are that they require extra memory... approximately 8 bytes per node beyond what is needed to store the datum in that node (in a 32-bit system who's pointers are 32 bits wide).
But a binary tree can sort a randomized set of data much quicker than more traditional sorting methods such as bubble sort and insertion sort.
Here is the C++ class for the binary tree:
binarytree.t
// (c) Jayson King
// binary tree template
#include <iostream.h>
template <class T>
class BinaryTree {
public:
BinaryTree();
~BinaryTree();
bool Full();
bool Empty();
void Add(T datum, bool(*leftof)(T x, T y));
void LNR(void(*pf)(T x));
void RNL(void(*pf)(T x));
bool Delete(T datum, bool(*leftof)(T x, T y));
private:
typedef struct treenode {
T datum;
struct treenode *left, *right;
} * TREE;
TREE root;
void Addhelp(TREE *Tree, T datum, bool(*leftof)(T x, T y));
void LNRhelp(TREE *Tree, void(*pf)(T x));
void RNLhelp(TREE *Tree, void(*pf)(T x));
bool Deletehelp(TREE *Tree, T datum, bool(*leftof)(T x, T y));
};
template <class T>
BinaryTree<T>::BinaryTree() { // initializes the tree
root=NULL;
}
template <class T>
bool BinaryTree<T>::Empty() { // checks for "emptiness" of tree
return (root==NULL);
}
template <class T>
void BinaryTree<T>::LNR(void(*pf)(T x)) { // prints elements in left-node-right order
BinaryTree<T>::LNRhelp(&root, pf);
}
template <class T>
void BinaryTree<T>::LNRhelp(TREE *Tree, void(*pf)(T x)) { // helper for LNR function
if(*Tree) {
BinaryTree<T>::LNRhelp(&((*Tree)->left), pf);
pf((*Tree)->datum);
BinaryTree<T>::LNRhelp(&((*Tree)->right), pf);
}
}
template <class T>
void BinaryTree<T>::RNL(void(*pf)(T x)) { // prints elements in right-node-left order
BinaryTree<T>::LNRhelp(&root, pf);
}
template <class T>
void BinaryTree<T>::RNLhelp(TREE *Tree, void(*pf)(T x)) { // helper for RNL function
if(*Tree) {
BinaryTree<T>::RNLhelp(&((*Tree)->right), pf);
pf((*Tree)->datum);
BinaryTree<T>::RNLhelp(&((*Tree)->left), pf);
}
}
template <class T>
void BinaryTree<T>::Add(T datum, bool(*leftof)(T x, T y)) { // Add a node to the tree
BinaryTree<T>::Addhelp(&root, datum, leftof);
}
template <class T>
void BinaryTree<T>::Addhelp(TREE *Tree, T datum, bool(*leftof)(T x, T y)) { // helper for add function
if(*Tree==NULL) {
TREE temp;
temp = new struct treenode;
if(!temp) {
cout << "Cannot add " << datum << " because there is no free memory!" << endl;
return;
}
temp->datum=datum;
temp->left=NULL;
temp->right=NULL;
*Tree=temp;
return;
} else if(leftof(datum, (*Tree)->datum))
BinaryTree<T>::Addhelp (&((*Tree)->left), datum, leftof);
else BinaryTree<T>::Addhelp (&((*Tree)->right), datum, leftof);
}
template <class T>
bool BinaryTree<T>::Delete(T datum, bool(*leftof)(T x, T y)) { // Delete an element
return(Deletehelp(&root, datum, leftof));
}
template <class T>
bool BinaryTree<T>::Deletehelp(TREE *Tree, T datum, bool(*leftof)(T x, T y)) { // Helper delete function
if(*Tree) {
if(datum == (*Tree)->datum) {
TREE temp;
if((*Tree)->left == NULL && (*Tree)->right == NULL) {
temp = *Tree;
*Tree = NULL;
delete temp;
}
else if((*Tree)->left != NULL && (*Tree)->right == NULL) {
temp = *Tree;
*Tree = (*Tree)->left;
delete temp;
}
else if((*Tree)->left == NULL && (*Tree)->right != NULL) {
temp = *Tree;
*Tree = (*Tree)->right;
delete temp;
}
else {
temp = (*Tree)->right;
while(temp->left != NULL)
temp = temp->left;
temp->left = (*Tree)->left;
temp = *Tree;
*Tree = (*Tree)->right;
delete temp;
}
return true; // show it was successful
}
else {
if(leftof(datum, (*Tree)->datum))
return Deletehelp(&(*Tree)->left, datum, leftof); // search on the left
else
return Deletehelp(&(*Tree)->right, datum, leftof); // search on the right
}
}
return false; // show the node did not exist
}
template <class T>
bool BinaryTree<T>::Full() { // check for "fullness"
TREE temp;
temp = new struct treenode;
if(temp) {
delete temp;
return true;
}
else
return false;
}
template <class T>
BinaryTree<T>::~BinaryTree() { }
The binary tree class relies on the caller to tell it how to determine which of two nodes is "greater" than the other one, since it is only acting on abstract data types. So most of the functions have as a parameter a pointer to a function which decides which node is greater.
Here is a main program which utilizes the binary tree class and uses it to sort a sample of random numbers, then print them out in sorted order.
main.cc
// (c) Jayson King
// binary tree sort
// main program
#include <time.h>
#include <iostream.h>
#include "binarytree.t"
#define COUNT 10000 // set how many numbers to use
void printer(int x);
bool lessthan(int x, int y);
int randu();
main() {
BinaryTree <int> b; // initialize the tree
int i,x[COUNT];
clock_t start,finish;
double duration;
void (*pf) (int x); // pointer to the print function
bool (*lt) (int x, int y); // pointer to the comparison function
pf = &printer;
lt = &lessthan;
for(i=0;i
start=clock(); // start the clock
for(i=0;i
}
finish=clock(); // stop the clock
duration=(double)(finish-start)/CLOCKS_PER_SEC;
cout << "Took " << duration << " seconds to sort " << COUNT << " numbers." << endl;
}
void printer(int x) {
cout << x << endl;
}
bool lessthan(int x, int y) {
return (x < y);
}
int randu() { // random number generator
static int seed=6718;
seed = (25173 * seed + 13849) % 65536;
return seed;
}
This code may be used as long as I am given credit and my copyright remains in place.