Make your own free website on Tripod.com

//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;

}