//biny.h
#ifndef __MYBINY__
#define __MYBINY__
#define DEBUG
#define kITMAXDEPTH 100
class TreeNode;
class BinaryTree
{
public:
BinaryTree();
int NumItems() const;
int Add(void* nItem, long key);
void *Find(long key);
void *Remove(long key);
#ifdef DEBUG
void PrintOn(ostream& out) const;
#endif
friend class TreeIterator;
private:
TreeNode *Root(void);
int AuxAdd(TreeNode*& c, void* nItem, long key);
void *AuxFind(TreeNode* c, long key);
void *AuxRemove(TreeNode*& c, long key);
void *Delete(TreeNode*&c);
TreeNode *Successor(TreeNode*& c);
#ifdef DEBUG
void AuxPrint(TreeNode* c, ostream& out, int depth) const;
#endif
TreeNode *fRoot;
int fNum;
};
class TreeIterator {
public:
TreeIterator(BinaryTree *tree);
void First(void);
void Next(void);
int IsDone(void);
void *CurrentItem(void);
private:
int fDepth;
TreeNode *fStack[kITMAXDEPTH];
BinaryTree *fTree;
};
inline int BinaryTree::NumItems(void) const { return fNum; }
inline TreeNode *BinaryTree::Root(void) { return fRoot; }
#endif
// biny.cpp
#include <iostream.h>
#include "a:biny.h"
class TreeNode {
public:
TreeNode(long k, void *d);
TreeNode*& LeftLink(void);
TreeNode*& RightLink(void);
long Key(void) const;
void *Data(void) const;
void Replace(long key, void *d);
private:
long fKey;
void *fData;
TreeNode *fLeft;
TreeNode *fRight;
};
TreeNode::TreeNode(long k,void *d)
{
fKey = k;
fData = d;
fLeft = NULL;
fRight = NULL;
}
inline long TreeNode::Key(void) const { return fKey; }
inline void *TreeNode::Data(void) const { return fData; }
inline TreeNode*& TreeNode::LeftLink(void) { return fLeft; }
inline TreeNode*& TreeNode::RightLink(void) { return fRight; }
inline void TreeNode::Replace(long key, void *d) { fKey = key; fData = d; }
BinaryTree::BinaryTree()
{
fRoot = NULL;
fNum = 0;
}
int BinaryTree::Add(void *nItem, long key)
{
return AuxAdd(fRoot, nItem, key);
}
int BinaryTree::AuxAdd(TreeNode*& c, void* nItem, long key)
{
if(c==NULL) {
c = new TreeNode(key, nItem);
fNum++;
return 1;
}
int compare = key - c->Key();
if(compare == 0) {
cout << "Sorry, duplicate keys not allowed" << endl;
return 0;
}
if(compare < 0)
return AuxAdd(c->LeftLink(), nItem, key);
else
return AuxAdd(c->RightLink(),nItem, key);
}
void *BinaryTree::Find(long key)
{
return AuxFind(fRoot, key);
}
void *BinaryTree::AuxFind(TreeNode* c, long key)
{
if(c == NULL)
return NULL;
int compare = key - c->Key();
if(compare == 0)
return c->Data();
if(compare < 0)
return AuxFind(c->LeftLink(), key);
else
return AuxFind(c->RightLink(), key);
}
void *BinaryTree::Remove(long key)
{
return AuxRemove(fRoot, key);
}
void *BinaryTree::AuxRemove(TreeNode*& c, long key)
{
if(c == NULL)
return NULL;
int compare = key - c->Key();
if(compare == 0)
return Delete(c);
if(compare < 0)
return AuxRemove(c->LeftLink(), key);
else
return AuxRemove(c->RightLink(), key);
}
void *BinaryTree::Delete(TreeNode*& c)
{
void *deaddata = c->Data(); fNum--;
if((c->LeftLink() == NULL) && (c->RightLink() == NULL))
{ delete c; c = NULL; }
else
if(c->LeftLink() == NULL) {
TreeNode* temp = c;
c = c->RightLink();
delete temp;
}
else
if(c->RightLink() == NULL) {
TreeNode* temp = c;
c = c->LeftLink();
delete temp;
}
else {
TreeNode* temp = Successor(c->RightLink());
c->Replace(temp->Key(), temp->Data());
delete temp;
}
return deaddata;
}
TreeNode *BinaryTree::Successor(TreeNode*& c)
{
if(c->LeftLink() != NULL)
return Successor(c->LeftLink());
else {
TreeNode *temp = c;
c = c->RightLink();
return temp;
}
}
#ifdef DEBUG
void BinaryTree::PrintOn(ostream& out) const
{
AuxPrint(fRoot, out, 0);
}
void BinaryTree::AuxPrint(TreeNode* c, ostream& out, int depth) const
{
if(c == NULL)
return;
AuxPrint(c->RightLink(), out, depth + 2);
for(int i=0;i< depth; i++)
cout << " ";
cout << c->Key();
cout << endl;
AuxPrint(c->LeftLink(), out, depth + 2);
}
#endif
TreeIterator::TreeIterator(BinaryTree *tree)
{
fTree = tree;
fDepth = -1;
}
void TreeIterator::First(void)
{
fDepth = -1;
TreeNode *ptr = fTree->Root();
while(ptr != NULL) {
fDepth++;
fStack[fDepth] = ptr;
ptr = ptr->LeftLink();
}
}
void TreeIterator::Next(void)
{
if(fDepth < 0) return;
TreeNode *ptr = fStack[fDepth];
fDepth--;
ptr = ptr->RightLink();
while(ptr != NULL) {
fDepth++;
fStack[fDepth] = ptr;
ptr = ptr->LeftLink();
}
}
int TreeIterator::IsDone(void)
{
return (fDepth < 0);
}
void *TreeIterator::CurrentItem(void)
{
if(fDepth < 0) return NULL;
else
return fStack[fDepth]->Data();
}
// main program
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#include "a:biny.cpp"
class DataItem {
public:
DataItem(long k, char txt[]);
void PrintOn(ostream& out) const;
long K() const;
private:
long fK;
char fName[20];
};
DataItem::DataItem(long k, char txt[] )
{
fK = k;
int len = strlen(txt);
len = (len > 19) ? 19 : len;
strncpy(fName, txt, len);
fName[len] = '\0';
}
void DataItem::PrintOn(ostream& out) const
{
out << fName << " : " << fK << ";" << endl;
}
inline long DataItem::K() const { return fK; }
BinaryTree gTree;
void DoDelete()
{
cout << "Enter key : ";
int k;
cin >> k;
DataItem *item = (DataItem*) gTree.Remove(k);
if(item == NULL) cout << "Wasn't there" << endl;
else {
cout << "Removed item: " ;
item->PrintOn(cout);
cout << "Destroyed" << endl;
delete item;
}
}
void DoInsert()
{
char buff[100];
int k;
cout << "Enter key and name" << endl;
cin >> k >> buff;
DataItem *d = new DataItem(k, buff);
if(gTree.Add(d , k)) cout << "OK" << endl;
else cout << "Problems" << endl;
}
void DoSearch()
{
cout << "Enter search key : ";
int k;
cin >> k;
DataItem *item = (DataItem*) gTree.Find(k);
if(item == NULL)
cout << "Not found " << endl;
else {
cout << "Found record : ";
item->PrintOn(cout);
}
}
int main()
{
for(int done = 0; ! done; ) {
cout<< "Q to quit, s to Search, i to Insert, d to Delete, p Print, w Walk" << endl;
cout << ">";
char ch;
cin >> ch;
switch(ch) {
case 'q':
done = 1;
break;
case 's':
DoSearch();
break;
case 'i':
DoInsert();
break;
case 'd':
DoDelete();
break;
case 'p':
gTree.PrintOn(cout);
break;
case 'w':
{
TreeIterator ti(&gTree);
ti.First();
cout << "Current tree " << endl;
cout << "Name Key" << endl;
while(!ti.IsDone()) {
DataItem *d = (DataItem*) ti.CurrentItem();
d->PrintOn(cout);
ti.Next();
}
}
break;
case '?':
cout << "Q to quit, s to Search, i to Insert, d to Delete, p Print, w Walk" << endl;
break;
default:
;
}
}
return EXIT_SUCCESS;
}