带索引的二叉搜索树

1、带索引的二叉搜索树/file:indexedBSTree.h#pragma once#include "BSTree.h"template<typename E,typename K>class IndexedBSTree : public BSTree<E,K>public:void Create();bool Search(const K& k,E& e)const;bool IndexSearch(int k,E& e)const;IndexedBSTree<E,K>& Insert(const E&

2、amp; e);IndexedBSTree<E,K>& Delete(const K& k,E& e);IndexedBSTree<E,K>& IndexDelete(int k,E& e);void Ascend();void IndexOutput();private:static void OutputLeftSize(BinaryTreeNode<E> *t);template<typename E,typename K>void IndexedBSTree<E,K>:Create()/

3、产生一个空的带索引的二叉搜索树root = 0;template<typename E,typename K>bool IndexedBSTree<E,K>:Search(const K& k,E& e) const/将关键值为k的元素返回到e中；如果操作失败返回false，否则返回truereturn BSTree<E,K>:Search(k,e);template<typename E,typename K>bool IndexedBSTree<E,K>:IndexSearch(int k,E& e) co

4、nst/将第k个元素返回到e中if(!root)return false;BinaryTreeNode<E> *p = root;while(p)if(k < p->LeftSize)p = p->LeftChild;else if(k > p->LeftSize)k -= p->LeftSize;p = p->RightChild;elsee = p->data;return true;return false;template<typename E,typename K>IndexedBSTree<E,K>

5、& IndexedBSTree<E,K>:Insert(const E& e)BSTree<E, K>:Insert(e);BinaryTreeNode<E> *t = root;while(t)if(e < t->data)t->LeftSize+;t = t->LeftChild;else if(e > t->data)t = t->RightChild;elset->LeftSize = 1;return *this;template<typename E,typename K>

6、;IndexedBSTree<E,K>& IndexedBSTree<E,K>:Delete(const K& k,E& e)/删除关键值为k的元素并且将其返回到e中/将p指向关键值为k的节点BinaryTreeNode<E> *p = root,/搜索指针*pp = 0;/p的父节点指针while(p && p->data != k)/移动到p的孩子pp = p;if(k < p->data)p = p->LeftChild;elsep = p->RightChild;if(!p)thr

7、ow BadInput();/没有关键值为k的元素e = p->data;/保存欲删除的元素BinaryTreeNode<E> *t = root;/搜索指针while(t && t->data != k)/移动到p的孩子if(k < t->data)t->LeftSize-;t = t->LeftChild;elset = t->RightChild;/对树进行重构/处理p有两个孩子的情形if(p->LeftChild && p->RightChild)/两个孩子/转换成有0或1个孩子的情形/在

8、p的左子树中寻找最大元素BinaryTreeNode<E> *s = p->LeftChild,*ps = p;/s的父节点while(s->RightChild)/移动到较大的元素ps = s;s = s->RightChild;p->LeftSize = p->LeftSize - 1;/修改所删除元素的索引值/将最大元素从s移动到pp->data = s->data;p = s;pp = ps;/p最多有一个孩子/在c中保存孩子指针BinaryTreeNode<E> *c;if(p->LeftChild)c = p-

9、>LeftChild;else c= p->RightChild;/删除pif(p = root)root = c;else/p是pp的左孩子还是pp的右孩子？if(p = pp->LeftChild)pp->LeftChild = c;elsepp->RightChild = c;delete p;return *this;template<typename E,typename K>IndexedBSTree<E,K>& IndexedBSTree<E,K>:IndexDelete(int k,E& e)/删

10、除第k个元素并将其返回到e中BinaryTreeNode<E> *p = root,*pp = 0;/指向第k个元素的父节点/寻找删除点while(p && k != p->LeftSize)pp = p;if(k < p->LeftSize)p = p->LeftChild;else if(k > p->LeftSize)k -= p->LeftSize;p = p->RightChild;if(!p)throw BadInput();/没有关键值为k的元素e = p->data;/保存欲删除的元素/调整Lef

11、tSize值BinaryTreeNode<E> *t = root;/搜索指针while(p && k != t->LeftSize)/移动到t的孩子if(k < t->LeftSize)t = t->LeftChild;else if(k > p->LeftSize)k -= t->LeftSize;t = t->RightChild;/对树进行重构/处理p有两个孩子的情形if(p->LeftChild && p->RightChild)/两个孩子/转换成有0或1个孩子的情形/在p的左子树

12、中寻找最大元素BinaryTreeNode<E> *s = p->LeftChild,*ps = p;/s的父节点while(s->RightChild)/移动到较大的元素ps = s;s = s->RightChild;p->LeftSize = p->LeftSize - 1;/修改所删除元素的索引值/将最大元素从s移动到pp->data = s->data;p = s;pp = ps;/p最多有一个孩子/在c中保存孩子指针BinaryTreeNode<E> *c;if(p->LeftChild)c = p->L

13、eftChild;else c= p->RightChild;/删除pif(p = root)root = c;else/p是pp的左孩子还是pp的右孩子？if(p = pp->LeftChild)pp->LeftChild = c;elsepp->RightChild = c;delete p;return *this;template<typename E,typename K>void IndexedBSTree<E,K>:Ascend()/按照关键值的升序排列输出所有元素InOutput();template<typename E,

14、typename K>void IndexedBSTree<E,K>:IndexOutput()/中序遍历，输出节点元素的索引值InOrder(OutputLeftSize,root);cout<<endl;template<typename E,typename K>void IndexedBSTree<E,K>:OutputLeftSize(BinaryTreeNode<E> *t)/输出节点元素的索引值cout<<t->LeftSize<<' '/file:BSTree.h#p

15、ragma once#include "binaryTree.h"template <typename E,typename K>class BSTree : public BinaryTree<E>public:bool Search(const K& k,E& e)const;BSTree<E,K>& Insert(const E& e);BSTree<E,K>& Delete(const K& k,E& e);void Ascend() InOutput();voi

16、d traversalBSTree(int a);void traversalBSTree0(BinaryTreeNode<E> *t,int &pos,int a);BSTree<E,K>& DeleteMax(E& x);template <typename E,typename K>bool BSTree<E,K>:Search(const K& k,E& e) const/搜索与k匹配的元素/指针p从树根开始进行查找if(!root)return false;BinaryTreeNode<E&

17、gt; *p = root;while(p)/检查p->dataif(k < p->data)p = p->LeftChild;else if(k > p->data)p = p->RightChild;else e = p->data;return true;return false;template <typename E,typename K>BSTree<E,K>& BSTree<E,K>:Insert(const E& e)/如果不出现重复，则插入eBinaryTreeNode<

18、E> *p = root,/搜索指针*pp = 0;/寻找插入点while(p)/检查p->datapp = p;/将p移向孩子节点if(e < p->data)p = p->LeftChild;else if(e > p->data)p = p->RightChild;elsethrow BadInput();/出现重复/为e建立一个节点，并将该节点连接至ppBinaryTreeNode<E> *r = new BinaryTreeNode<E> (e);if(root)/树非空if(e < pp->data

19、)pp->LeftChild = r;elsepp->RightChild = r;else/插入到空树root = r;return *this;template <typename E,typename K>BSTree<E,K>& BSTree<E,K>:Delete(const K& k,E& e)/删除关键值为k的元素，并将其放入e/将p指向关键值为k的节点BinaryTreeNode<E> *p = root,/搜索指针*pp = 0;/p的父节点指针while(p && p->

20、;data != k)/移动到p的孩子pp = p;if(k < p->data)p = p->LeftChild;elsep = p->RightChild;if(!p)throw BadInput();/没有关键值为k的元素e = p->data;/保存欲删除的元素/对树进行重构/处理p有两个孩子的情形if(p->LeftChild && p->RightChild)/两个孩子/转换成有0或1个孩子的情形/在p的左子树中寻找最大元素BinaryTreeNode<E> *s = p->LeftChild,*ps =

21、p;/s的父节点while(s->RightChild)/移动到较大的元素ps = s;s = s->RightChild;/将最大元素从s移动到pp->data = s->data;p = s;pp = ps;/p最多有一个孩子/在c中保存孩子指针BinaryTreeNode<E> *c;if(p->LeftChild)c = p->LeftChild;else c= p->RightChild;/删除pif(p = root)root = c;else/p是pp的左孩子还是pp的右孩子？if(p = pp->LeftChild)p

22、p->LeftChild = c;elsepp->RightChild = c;delete p;return *this;template <typename E,typename K>void BSTree<E,K>:traversalBSTree(int a) int pos = 0;traversalBSTree0(root,pos,a);template <typename E,typename K>void BSTree<E,K>:traversalBSTree0(BinaryTreeNode<E> *t,in

23、t &pos,int a) if (!t) return; traversalBSTree0(t->LeftChild, pos, a); apos+ = t->data; traversalBSTree0(t->RightChild, pos, a);template<class E, class K>BSTree<E,K>& BSTree<E,K>:DeleteMax(E& x) if (!root) throw OutOfBounds(); BinaryTreeNode<E> *p = root,

24、*pp = 0; while (p->RightChild) pp = p; p = p->RightChild; x = p->data; if (p = root) root = p->LeftChild; else pp->RightChild = p->LeftChild; delete p; return *this;/file:binaryTree.h#ifndef _BINARYTREE_H_#define _BINARYTREE_H_#include "BinaryTreeNode.h"#include "lin

25、kedQueue.h"#include "exception.h"int _count = 0;template <typename T>class BinaryTreetemplate <typename E,typename K>friend class IndexedBSTree;template <typename E,typename K>friend class BSTree;public:BinaryTree() root = 0;BinaryTree() bool IsEmpty() const return (

26、root) ? false : true);bool Root(T& x) const;void SetRoot(BinaryTreeNode<T>* t) root = t;BinaryTreeNode<T>* GetRoot() return root;void MakeTree(const T& element,BinaryTree<T>& left,BinaryTree<T>& right);void BreakTree(T& element,BinaryTree<T>& lef

27、t,BinaryTree<T>& right);void PreOrder(void (*Visit)(BinaryTreeNode<T> *u)PreOrder(Visit,root);void InOrder(void (*Visit)(BinaryTreeNode<T> *u)InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode<T> *u)PostOrder(Visit,root);void LevelOrder(void (*Visit)(BinaryTr

28、eeNode<T> *u);void PreOutput()PreOrder(Output,root);cout<<endl;void InOutput()InOrder(Output,root);cout<<endl;void PostOutput()PostOrder(Output,root);cout<<endl;void LevelOutput()LevelOrder(Output);cout<<endl;void Delete()PostOrder(Free,root);root = 0;int Height() const

29、return Height(root);int Size();BinaryTreeNode<T>* search(T element) return search(element, root);BinaryTreeNode<T>* copy(BinaryTreeNode<T> * t);int NumLeaves()return CountLeaf(root);void Swap()Swap0(root);bool Compare(BinaryTree<T>& X)return Compare1(root,X.root);bool IsH

30、BLT()return IsHBLT(root);private:BinaryTreeNode<T> *root;/根节点指针void PreOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t);void InOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t);void PostOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryT

31、reeNode<T> *t);static void Output(BinaryTreeNode<T> *t);static void Free(BinaryTreeNode<T> *t) delete t;int Height(BinaryTreeNode<T> *t) const;static void Add1(BinaryTreeNode<T> *t) _count+;/int Count(BinaryTreeNode<T> *t) const;BinaryTreeNode<T>* search(T&a

32、mp; element,BinaryTreeNode<T> *t);int CountLeaf(BinaryTreeNode<T> *t);void Swap0(BinaryTreeNode<T> *t);bool Compare1(BinaryTreeNode<T> *p,BinaryTreeNode<T> *t);bool IsHBLT(BinaryTreeNode<T> * t);template <typename T>bool BinaryTree<T>:Root(T& x) co

33、nst/取根节点的data域，放入x /如果没有根节点，则返回falseif(root)x = root->data;return true;elsereturn false; /没有根节点template <typename T>void BinaryTree<T>:MakeTree(const T& element,BinaryTree<T>& left,BinaryTree<T>& right)/将left，right和element合并成一棵新树 /left，right和this必须是不同的树/创建新树roo

34、t = new BinaryTreeNode<T> (element,left.root,right.root);/阻止访问left和rightleft.root = right.root = 0;template <typename T>void BinaryTree<T>:BreakTree(T& element,BinaryTree<T>& left,BinaryTree<T>& right)/left，right和this必须是不同的树/检查树是否为空if(!root) throw BadInput()

35、; /空树/分解树element = root->data;left.root = root->LeftChild;right.root = root->RightChild;delete root;root = 0;template <typename T>void BinaryTree<T>:LevelOrder(void (*Visit)(BinaryTreeNode<T> *u)/逐层遍历LinkedQueue<BinaryTreeNode<T>*> Q;BinaryTreeNode<T> *t;

36、t = root;while(t)Visit(t);if(t->LeftChild)Q.Add(t->LeftChild);if(t->RightChild)Q.Add(t->RightChild);tryQ.Delete(t);catch (OutOfBounds)return ;template <typename T>int BinaryTree<T>:Size()_count = 0;PreOrder(Add1,root);return _count;/*int size() return Count(root);*/template &

37、lt;typename T>BinaryTreeNode<T>* BinaryTree<T>:copy(BinaryTreeNode<T> * t) if (!t) return 0;/ empty tree BinaryTreeNode<T> * left = copy(t->LeftChild); BinaryTreeNode<T> * right = copy(t->RightChild); root = new BinaryTreeNode<T> ; root->data = t->d

38、ata; root->LeftChild = left; root->RightChild = right; return root;/*template <typename T>bool BinaryTree<T>:Compare(BinaryTree<T>& X)/比较该二叉树与二叉树XBinaryTreeNode<T> *t = X.GetRoot();return Compare1(root,t);*/*私有函数成员*template <typename T>void BinaryTree<T>

39、:PreOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t)/前序遍历if(t)Visit(t);PreOrder(Visit,t->LeftChild);PreOrder(Visit,t->RightChild);template <typename T>void BinaryTree<T>:InOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t)/中序遍历if(

40、t)InOrder(Visit,t->LeftChild);Visit(t);InOrder(Visit,t->RightChild);template <typename T>void BinaryTree<T>:PostOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t)/后序遍历if(t)PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);template

41、<typename T>void BinaryTree<T>:Output(BinaryTreeNode<T> *t)cout<<t->data<<' 'template <typename T>int BinaryTree<T>:Height(BinaryTreeNode<T> *t) const/返回树*t的高度if(!t)return 0; /空树int hl = Height(t->LeftChild);/左子树的高度int hr = Height(t->R

42、ightChild);/右子树的高度if(hl > hr)return +hl;elsereturn +hr;/*template<typename T>int BinaryTree<T>:Count(BinaryTreeNode<T> *t) const if (!t) return 0; int left,right; left = Count(t->LeftChild); right = Count(t->RightChild); return 1 + left + right;*/template<typename T>

43、BinaryTreeNode<T>* BinaryTree<T>:search(T& element,BinaryTreeNode<T> *t) if (!t) return 0; if(t->data = element) return t; BinaryTreeNode<T> * p; p = search(element, t->LeftChild); if(p) return p; return search(element, t->RightChild);template <typename T>i

44、nt BinaryTree<T>:CountLeaf(BinaryTreeNode<T> *t)if(!t)return 0;if(!t->LeftChild && !t->RightChild)return 1;int c1,c2;c1 = CountLeaf(t->LeftChild);c2 = CountLeaf(t->RightChild);return c1 + c2;template <typename T>void BinaryTree<T>:Swap0(BinaryTreeNode<T

45、> *t)/交换二叉树所有节点的左右子节点if(t)if(t->LeftChild | t->RightChild)BinaryTreeNode<T> *temp = t->LeftChild;t->LeftChild = t->RightChild;t->RightChild = temp;Swap0(t->LeftChild);Swap0(t->RightChild);template <typename T>bool BinaryTree<T>:Compare1(BinaryTreeNode<

46、T> *p,BinaryTreeNode<T> *t)if(!p && !t)return true;if(!p && t) | (p && !t)return false;if(p && t)if(p->data = t->data)bool left = Compare1(p->LeftChild,t->LeftChild);bool right = Compare1(p->RightChild,t->RightChild);if(left && right

47、)return true;elsereturn false;elsereturn false;template <typename T>bool BinaryTree<T>:IsHBLT(BinaryTreeNode<T> * t)if(!t)return true;if(!t->LeftChild && t->RightChild)return false;if(t->LeftChild && !t->RightChild)return true;bool bLeft = IsHBLT(t->L

48、eftChild);bool bRight = IsHBLT(t->RightChild);if(bLeft && bRight)return true;elsereturn false;/*#endif/file:binaryTreeNode.h#ifndef _BINARYTREENODE_H_#define _BINARYTREENODE_H_#include <iostream>using namespace std;template <typename T>class BinaryTree;template <typename T&

49、gt;class BinaryTreeNodetemplate <typename E,typename K>friend class IndexedBSTree;template <typename E,typename K>friend class BSTree;friend class BinaryTree<T>friend ostream& operator<<(ostream& out,BinaryTreeNode<T> *p);public:BinaryTreeNode()LeftChild = Right

50、Child = 0;BinaryTreeNode(const T& e)data = e;LeftChild = RightChild = 0;BinaryTreeNode(const T& e,BinaryTreeNode<T> *l,BinaryTreeNode<T> *r)data = e;LeftChild = l;RightChild = r;T GetData()return data;void SetLeftChild(BinaryTreeNode<T> *left) LeftChild = left;void SetRight

51、Child(BinaryTreeNode<T> *right) RightChild = right;private:T data;BinaryTreeNode<T> *LeftChild,/左子树*RightChild;/右子树int LeftSize;/索引值 = 该节点左子树的元素个数加1;template <typename T>ostream& operator<<(ostream& out,BinaryTreeNode<T> *p)out<<p->GetData()<<endl

52、;return out;#endif/file:linkedQueue.h#ifndef _LINKEDQUEUE_H_#define _LINKEDQUEUE_H_#include "node.h"#include "exception.h"template <typename T>class LinkedQueue/FIFO对象public:LinkedQueue() front = rear = 0;/构造函数LinkedQueue();/析构函数bool IsEmpty() constreturn (front) ? false :

53、true);bool IsFull() const;T First() const;/返回第一个元素T Last() const;/返回最后一个元素Node<T>* GetFront()return front;LinkedQueue<T>& Add(const T& x);LinkedQueue<T>& Delete(T& x);private:Node<T> *front;/指向第一个节点Node<T> *rear;/指向最后一个节点;template <typename T>Linke

54、dQueue<T>:LinkedQueue()/队列析构函数，删除所有节点Node<T> *next;while(front)next = front->link;delete front;front = next;template <typename T>bool LinkedQueue<T>:IsFull() const/判断队列是否已满Node<T> *p;tryp = new Node<T>delete p;return false;catch(NoMem)return true;template <t

55、ypename T>T LinkedQueue<T>:First() const/返回队列的第一个元素 /如果队列为空，则引发异常OutOfBoundsif(IsEmpty()throw OutOfBounds();return front->data;template <typename T>T LinkedQueue<T>:Last() const/返回队列的最后一个元素 /如果队列为空，则引发异常OutOfBoundsif(IsEmpty()throw OutOfBounds();return rear->data;template <typename T>LinkedQueue<T>& LinkedQueue<T>:Add(const T& x)/把x添加到队列的尾部 /不捕获可能由new引发的NoMem异常/为新元素创建链表节点Node<T> *p = new Node<T>p->data = x;p->link = 0;/在队列尾部添加新节点if(front)rear->link = p;/队列不为空rear = p;elsefront = p;/队列为空rear = p;return *this;templa