Code illustrating a simple binary tree class with an assoicated tree iterator. ==== a test program ==== #include #include #include #include "biny.h" 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 << ">"; 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; 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; } ==== header file for binary tree class, 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 ==== implementation file, biny.cp ==== #include #include "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(); }