binary tree sorting.
Posted: Wed Mar 04, 2009 11:02 am
i dont know if anyone would want/need this. its by no means the best solution. but it works and is more academical than anything else.
please feel free to ask any questions may the arise.
ps: just a little node. NO this does not do any fancy checking for alphabetic order. it does not check for caps. so just use all lower or all uppercase. if you are really interested you can twiddle with it. but like i said, its more academical.
edit: i also just want to add that there is no advanced techniques like tree balancing to make the tree more efficient. but there are things like that, so feel free to study up on them.
main.cpp
node.h
node.cpp
tree.h
tree.cpp
please feel free to ask any questions may the arise.
ps: just a little node. NO this does not do any fancy checking for alphabetic order. it does not check for caps. so just use all lower or all uppercase. if you are really interested you can twiddle with it. but like i said, its more academical.
edit: i also just want to add that there is no advanced techniques like tree balancing to make the tree more efficient. but there are things like that, so feel free to study up on them.
main.cpp
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include "node.h"
#include "tree.h"
int main()
{
printf("Start of program.\n");
tree *sort = new tree();
sort->addNode("zach");
sort->addNode("stephanie");
sort->addNode("andre");
sort->addNode("bob");
sort->addNode("dannie");
sort->addNode("kurk");
sort->printList(sort->head);
return 0;
}
Code: Select all
#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char *name;
node *left;
node *right;
};
node *newNode(char *name);
#endif // NODE_H_INCLUDED
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node.h"
node *newNode(char *name)
{
node *temp = (node*)malloc(sizeof(node));
temp->name = (char*)malloc(sizeof(char)*strlen(name));
for(int a = 0;a < strlen(name);a++)
{
temp->name[a] = name[a];
}
temp->name[strlen(name)] = '\0';
temp->left = NULL;
temp->right = NULL;
return temp;
}
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node.h"
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
class tree
{
public:
tree();
void addNode(char *name);
bool sort(char *a, char *b); // returns true if a comes before b
void printList(const node * const temp);
//private:
node *head;
};
#endif // TREE_H_INCLUDED
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node.h"
#include "tree.h"
tree::tree()
{
this->head = NULL;
}
void tree::addNode(char *name)
{
if(!this->head)
{
this->head = newNode(name);
return;
}
node *temp = (node*)malloc(sizeof(node));
temp = this->head;
while(temp)
{
if(this->sort(name, temp->name))
{
if(temp->left)
{
temp = temp->left;
}else{
temp->left = newNode(name);
return;
}
}else{
if(temp->right)
{
temp = temp->right;
}else{
temp->right = newNode(name);
return;
}
}
}
}
bool tree::sort(char *a, char *b)
{
int p = 0;
while(p < strlen(a) || p < strlen(b))
{
if(a[p] > b[p])
{
return false;
}
if(a[p] < b[p])
{
return true;
}
p++;
}
return false;
}
void tree::printList(const node * const temp)
{
if(!temp) return;
this->printList(temp->left);
printf("name : %s\n", temp->name);
this->printList(temp->right);
}