My binary tree needs to do the following:
1. Store any amount of positive integers.
2. Delete any given entry in the binary search tree
3. Print out the entries in the tree in ascending and descending order.
4. Allow the tree to be searched such that if a number is input the two nearest numbers to it are found in the tree and output to the screen, if the input number exists in the tree only that is output.
Now i have done task 1, 2, and part of 3. I can't fugure out how to make it print out the numbers in reverse order or how to do task 4. Any help on the subject is much appreciated. Here is my code.
Code:
#include <iostream.h>
#include <cstring.h>
#include <conio.h>
#include <ctype.h>
#include <fstream.h>
// declare a tree node structure
struct treenode {
string data;
treenode* left;
treenode* right;
};
// create a new tree with an empty root node
// pass back the root address
treenode* initialise() {
treenode *root = new treenode;
root->data=" ";
root->right=NULL;
root->left=NULL;
return root;
}
// used for the 'delete' routine
ofstream file1;
ifstream file2;
// insert a new item, starting at the root
void insert(treenode* root,string newitem) {
treenode *temp, *current;
bool found;
clrscr();
current=root;
found=false;
while (!found) {
if (newitem < current->data)// belongs to left of current
{
if (!(current->left))
found=true; //if left pointer is NULL add new item here
else {
current=current->left;
}
}
else // otherwise belongs on right hand side
if(!(current->right))
found=true; // if right pointer NULL add here
else {
current=current->right; // look at right hand branch
}
}
// now add a new node
temp= new treenode; // create node
temp->data = newitem; // put data into it
temp->right=NULL;
temp->left=NULL;
if (newitem < current->data) // now add it on correct side of current
current->left=temp;
else
current->right=temp;
}
// this is a recursive function
// traverse in order
void inorder(treenode* tree) {
treenode *leftsubtree, *rightsubtree;
leftsubtree=tree->left;
rightsubtree=tree->right;
if (leftsubtree) // i.e if not NULL (empty subtree)
inorder(leftsubtree); // recursive call
cout<<tree->data<<endl;
if (rightsubtree) // i.e. if not NULL (empty subtree)
inorder(rightsubtree); // recursive call
}
// also a recursive function
void search(treenode* current, string item){
if (!current)
cout<<"not in the tree"<<endl;
else {
if (item==current->data)
cout<<item<<" is in the tree "<<endl;
else
{
if (item<current->data)
search(current->left, item);
else
search(current->right, item);
}
}
}
// delete a node containing a given item
// traverse tree pre-order and write data to file, except for item to delete
void preorder(treenode* tree, string item){
treenode *leftsubtree, *rightsubtree;
leftsubtree=tree->left;
rightsubtree=tree->right;
if (tree->data!=item)
file1<<tree->data<<" ";
if (leftsubtree) // i.e if not NULL (empty subtree)
preorder(leftsubtree, item); // recursive call
if (rightsubtree) // i.e. if not NULL (empty subtree)
preorder(rightsubtree, item); // recursive call
}
// read file and insert data to build a new tree
void writenewtree(treenode* root){
string data;
while (file2>>data)
insert(root, data);
}
void main() {
treenode* root;
treenode* newroot;
string prompt = "Traverse in order 1. Search 2. Delete node 3. Quit 0.";
char choice;
root= initialise();
string item;
// build the tree -------------------------------------
cout<<"Data -Z to end: ";
getline(cin, item);
while (item!="Z") {
if (root->data==" ") // if the root is empty
{
root->data =item; // put the new item in the root
}
else
insert(root,item); // otherwise call insert function passing 'root'
cout<<"Data Z to end: ";
getline(cin, item);
}
// ----------------------------------------------------
clrscr();
cout<<endl<<prompt;
cin>>choice;
clrscr();
while (toupper(choice)!='0'){
switch (choice){
case '1': cout<<"Traversing tree in order..."<<endl;
inorder(root);
break;
case '2': cout<<"Search for an item? Z if none: ";
getline(cin, item);
while (item!="Z"){
clrscr();
search(root,item);
inorder(root);
cout<<"Search for an item? Z if none: ";
getline(cin, item);
}
break;
case '3': cout<<"Delete an item? Z if none: ";
getline(cin, item);
while (item!="Z"){
clrscr();
file1.open("tempfile");
preorder(root, item);
file1.close();
file2.open("tempfile");
newroot = initialise();
writenewtree(newroot);
file2.close();
cout<<"Existing tree..."<<endl;
inorder(root);
cout<<endl<<"New tree..."<<endl;
inorder(newroot);
root=newroot;
cout<<endl<<"Delete an item? Z if none: ";
getline(cin, item);
}
break;
}
cout<<endl<<prompt;
cin>>choice;
clrscr();
}
PostQuitMessage(0);
}