// bts.cpp // binary tree search #define infoNIL 0 #define itemMIN 0 #include typedef int itemType; typedef int infoType; class Dict { private: struct node { itemType key; infoType info; node *l, *r; node(itemType k, infoType i, node *ll, node *rr) {key = k; info = i; l = ll; r = rr; }; }; node *head, *z; // head's r points to the actual root of the tree void trav(node *t); public: Dict(int max) { z = new node(0, infoNIL, 0, 0); head = new node(itemMIN, 0, 0, z); } ~Dict() {} infoType search(itemType v); void insert(itemType v, infoType info); void remove(itemType v); void traverse(); void visit(node *t); }; void Dict::visit(node *t) { cout << t->key << ". info: " << t->info << endl; } void Dict::traverse() { trav(head->r); // head's right link points to the actual root of the tree } void Dict::trav(node* t) { if (t != z) { trav(t->l); visit(t); // inorder traversal trav(t->r); } } infoType Dict::search(itemType v) { node *x = head->r; z->key = v; while (v != x->key) x = (v < x->key) ? x->l : x->r; return x->info; } void Dict::remove(itemType v) { node *c, *p, *x, *t; // p is the parent of x. c is the successor node // of the node to be deleted. After the deletion, // x is the child of p. t is to be deleted z->key = v; p = head; x = head->r; while (v != x->key) { p = x; x = (v < x->key) ? x->l : x->r; } t = x; if (t->r == z) x = x->l;// if t has no right child, then the child of p // after the deletion will be the left child of t else if (t->r->l == z) { x = x->r; x->l = t->l; } // if t has a right child // with no left child then that rigth child will be // the child of p after the deletion, with its left // link copied from t else { // otherwise, x is set to the node with the smallest // key in the subtree to the right of t; that node's // right link is copied to the left link of its // parent, and both of its links are set from t c = x->r; while (c->l->l != z) c = c->l; x = c->l; c->l = x->r; x->l = t->l; x->r = t->r; } delete t; if (v < p->key) p->l = x; else p->r = x; } void Dict::insert(itemType v, infoType info) { node *p, *x; // p keeps track of the parent of x as it proceeds // down the tree. When the bottom om the tree (x == z) // is reached, p points to the node whose link must be // changed to point to the new node inserted. p = head; x = head->r; while (x != z) { p = x; x = (v < x->key) ? x->l : x->r; } x = new node(v, info, z, z); if (v < p->key) p->l=x; else p->r=x; } void main() { Dict d(10); infoType i, j; d.insert(3, 2); d.insert(9, 33); d.insert(6, 23); d.insert(2, 198); d.insert(12, 2); d.insert(3, 12); d.remove(9); i = d.search(9); j = d.search(2); cout << i << " " << j << endl << endl; d.traverse(); }