索引二叉搜索树

1、/ linked binary tree implementation of a binary search tree/ implements all dictionary and bsTree methods#ifndef indexedBinarySearchTree_#define indexedBinarySearchTree_#include "indexedBSTree.h"#include "linkedBinaryTree.h"using namespace std;template<class K, class E>clas

2、s indexedBinarySearchTree : public indexedBSTree<K,E>, public linkedBinaryTree<pair<const K, E> > public: / methods of dictionary bool empty() const return this->treeSize = 0; int size() const return this->treeSize; pair<const K, E>* get(int ) const; void insert(const p

3、air<const K, E>& thePair); void erase(const K& theKey); void delete2(int); / additional method of bsTree void ascend() this->inOrderOutput(); / void makeBst(const int a); void eraseMax();/删除关键字最大的元素;template<class K, class E>pair<const K, E>* indexedBinarySearchTree<K

4、,E>:get(int Index)const binaryTreeNode<pair<const K, E> > *p =this->root; while (p != NULL) if (Index < p->leftSize) p = p->leftChild; else if (Index > p->leftSize) Index = Index-(p->leftSize+1); p = p->rightChild; else / found matching pair return &p->e

5、lement; / no matching pair return NULL;template<class K, class E>void indexedBinarySearchTree<K,E>:insert(const pair<const K, E>& thePair)/ Insert thePair into the tree. Overwrite existing / pair, if any, with same key. / find place to insert binaryTreeNode<pair<const K,

6、E> > *p = this->root, *pp = NULL; while (p != NULL) / examine p->element pp = p; / pp作为p的双亲结点 if (thePair.first < p->element.first) p->leftSize+;/索引加1 p = p->leftChild; else if (thePair.first > p->element.first) p = p->rightChild; else/如果相同 /替换原来的value p->element.

7、second = thePair.second;/不对 return; / get a node for thePair and attach to pp binaryTreeNode<pair<const K, E> > *newNode = new binaryTreeNode<pair<const K, E> > (thePair); if (this->root != NULL) / the tree is not empty if (thePair.first < pp->element.first) pp->l

8、eftChild = newNode; /pp->leftSize = 1;/索引为1 else pp->rightChild = newNode; else this->root = newNode; /this->root->leftSize = 0;/索引为0 / insertion into empty tree this->treeSize+;template<class K, class E>void indexedBinarySearchTree<K,E>:erase(const K& theKey)/根据关键字

9、删除/ Delete the pair, if any, whose key equals theKey. / search for node with key theKey binaryTreeNode<pair<const K, E> > *p = this->root, *pp = NULL; while (p != NULL && p->element.first != theKey) / move to a child of p pp = p; if (theKey < p->element.first) p = p-&

10、gt;leftChild; else p = p->rightChild; if (p = NULL) return; / no pair with key theKey / restructure tree / handle case when p has two children if (p->leftChild != NULL && p->rightChild != NULL) / two children / convert to zero or one child case / find largest element in left subtree

11、 of p binaryTreeNode<pair<const K, E> > *s = p->leftChild, *ps = p; / parent of s while (s->rightChild != NULL) / move to larger element ps = s; s = s->rightChild; / move largest from s to p, can't do a simple move / p->element = s->element as key is const binaryTreeNo

12、de<pair<const K, E> > *q = new binaryTreeNode<pair<const K, E> > (s->element, p->leftChild, p->rightChild); if (pp = NULL) this->root = q; else if (p = pp->leftChild) pp->leftChild = q; else pp->rightChild = q; if (ps = p) pp = q; else pp = ps; delete p;

13、p = s; / p has at most one child / save child pointer in c binaryTreeNode<pair<const K, E> > *c; if (p->leftChild != NULL) c = p->leftChild; else c = p->rightChild; / delete p if (p = this->root) this->root = c; else / is p left or right child of pp? if (p = pp->leftChi

14、ld) pp->leftChild = c; else pp->rightChild = c; this->treeSize-; delete p;template<class K, class E>void indexedBinarySearchTree<K,E>:delete2(int Index)/ Delete the pair, if any, whose key equals theKey. / search for node with key theKey binaryTreeNode<pair<const K, E>

15、> *p = this->root, *pp = NULL;/* if (p = NULL) return; / no pair with key theKey*/ if(Index>this->treeSize-1)/如果索引值大于节点数减1，则不存在该索引值 return ; while (p&& p->leftSize != Index)/寻找索引值为Index的结点 / move to a child of p /*pp = p; if (theKey < p->element.first) p = p->leftChil

16、d; else p = p->rightChild;*/ if (Index < p->leftSize) pp = p;/p的父节点 p->leftSize-;/每向左移动一次索引值减1 p = p->leftChild; else if (Index > p->leftSize) pp = p;/p的父节点 Index = Index-(p->leftSize+1); p = p->rightChild; /*else / found matching pair return &p->element;*/ if (p-&g

17、t;leftChild != NULL && p->rightChild != NULL)/存在左孩子和右孩子的情况 / two children / convert to zero or one child case / find largest element in left subtree of p binaryTreeNode<pair<const K, E> > *s = p->leftChild, *ps = p; / parent of s while (s->rightChild != NULL)/寻找左子树中最大的结点

18、 / move to larger element ps = s; /ps->leftSize-;/索引减1 s = s->rightChild;/s为要替换的值 / 将最大元素s移动到p但不是简单的移动 binaryTreeNode<pair<const K, E> > *q = new binaryTreeNode<pair<const K, E> > (s->element, p->leftChild, p->rightChild); if (pp = NULL)/如果要删除的结点是根节点，则直接替换根节点 t

19、his->root = q; else if (p = pp->leftChild) pp->leftChild = q; else pp->rightChild = q; if (ps = p) pp = q; else pp = ps; delete p; p = s; / p has at most one child / save child pointer in c binaryTreeNode<pair<const K, E> > *c; if (p->leftChild != NULL) c = p->leftChild

20、; else c = p->rightChild; / delete p if (p = this->root) this->root = c; else / is p left or right child of pp? if (p = pp->leftChild) pp->leftChild = c; else pp->rightChild = c; this->treeSize-; delete p;/ overload << for pairtemplate <class K, class E>ostream&

21、operator<<(ostream& out, const pair<K, E>& x) out << x.first << ' ' << x.second; return out;template <class K,class E>void indexedBinarySearchTree<K,E>:eraseMax()binaryTreeNode<pair<const K, E> > *p =this->root, *pp = NULL;whil

22、e(p != NULL)pp = p;p = p->rightChild;if(p->leftChild != NULL)pp->leftChild = p->leftChild;this->treeSize-;delete p;#endif/测试代码/ test binary search tree class#include <iostream>#include "indexedBinarySearchTree.h"using namespace std;int main(void) indexedBinarySearchTre

23、e<int,char> y; y.insert(pair<int, char>(1, 'a'); y.insert(pair<int, char>(6, 'c'); y.insert(pair<int, char>(4, 'b'); y.insert(pair<int, char>(8, 'd'); cout << "Tree size is " << y.size() << endl; cout <<

24、"Elements in ascending order are" << endl; y.ascend(); pair<const int, char> *s = y.get(3);/查找索引为3的结点 cout << "Search for 3 index " << endl; cout << s->first << ' ' << s->second << endl; / y.erase(4); y.delete2(2);/删除索

25、引为2的结点 cout << "2 index deleted " << endl; cout << "Tree size is " << y.size() << endl; cout << "Elements in ascending order are" << endl; y.ascend(); s = y.get(2);/查找索引为2的结点 cout << "Search for 2 index " << endl; /cout << s->first << ' ' << s->second << endl; y.delete2(2);/删除索引为2的结点 cout << "2 deleted " << endl; cout << "Tree size is " << y.size() << endl; cout &