学步园

树的实现文件

/*<br /> * BinarySearchTree.h<br /> *<br /> * Created on: 2011-5-27<br /> * Author: sjiang2142<br /> */</p> <p>template<typename Comparable><br /> class BinarySearchTree<br /> {<br /> public:<br /> //构造函数<br /> BinarySearchTree()<br /> {<br /> root=NULL;<br /> }<br /> //复制构造函数<br /> BinarySearchTree(const BinarySearchTree& rhs)<br /> {<br /> operator=(rhs);<br /> }<br /> //析构函数<br /> ~BinarySearchTree()<br /> {<br /> makeEmpty();<br /> }<br /> //该方法用于寻找最小元素<br /> const Comparable& findMin()const<br /> {<br /> return findMin(root)->element;<br /> }<br /> //该方法用于寻找最大元素<br /> const Comparable& findMax()const<br /> {<br /> return findMax(root)->element;<br /> }<br /> //该方法判断树中是否包含某一元素<br /> bool contains(const Comparable& x)const<br /> {<br /> return contains(x,root);<br /> }<br /> //判断是否是空树<br /> bool isEmpty()const<br /> {<br /> if(root==NULL)<br /> {<br /> return true;<br /> }<br /> else<br /> {<br /> return false;<br /> }<br /> }<br /> //打印一棵树<br /> void printTree()const<br /> {<br /> printTree(root);<br /> }<br /> //清空一棵树<br /> void makeEmpty()<br /> {<br /> makeEmpty(root);<br /> }<br /> //插入一个元素<br /> void insert(const Comparable& x)<br /> {<br /> insert(x,root);<br /> }<br /> //移除一个元素<br /> void remove(const Comparable& x)<br /> {<br /> remove(x,root);<br /> }<br /> //重载赋值运算符<br /> const BinarySearchTree& operator=(const BinarySearchTree& rhs)<br /> {<br /> if(this!=&rhs)<br /> {<br /> makeEmpty();<br /> root = clone(rhs.root);<br /> }<br /> return *this;<br /> }</p> <p>private:<br /> //结点结构<br /> struct BinaryNode<br /> {<br /> Comparable element;<br /> BinaryNode* left;<br /> BinaryNode* right;<br /> BinaryNode(const Comparable& theElement,BinaryNode *lt,BinaryNode* rt):element(theElement),left(lt),right(rt){}<br /> };<br /> BinaryNode* root;//根结点<br /> //插入一个元素<br /> void insert(const Comparable& x,BinaryNode*& t)const<br /> {<br /> if(t==NULL)<br /> {<br /> t = new BinaryNode(x,NULL,NULL);<br /> }<br /> else if(x<t->element)<br /> {<br /> insert(x,t->left);<br /> }<br /> else if(x>t->element)<br /> {<br /> insert(x,t->right);<br /> }<br /> }<br /> //删除某一元素<br /> void remove(const Comparable& x,BinaryNode*& t)const<br /> {<br /> if(t==NULL)<br /> {<br /> return;<br /> }<br /> if(x<t->element)//首先找到要删除的节点<br /> {<br /> remove(x,t->left);<br /> }<br /> else if(x>t->element)<br /> {<br /> remove(x,t->right);<br /> }<br /> else if(t->left!=NULL&&t->right!=NULL)//找到了要删除的节点，并且该节点有两个孩子<br /> {<br /> t->element=findMin(t->right)->element;//使用右子树中最小的节点元素替代要删除的节点元素<br /> remove(t->element,t->right);<br /> }<br /> else//找到了要删除的节点，并且该节点只有一个孩子<br /> {<br /> BinaryNode* oldNode=t;<br /> t=(t->left!=NULL)?t->left:t->right;<br /> delete oldNode;<br /> }<br /> }<br /> //返回最小元素<br /> BinaryNode* findMin(BinaryNode* t)const<br /> {<br /> if(t==NULL)<br /> {<br /> return NULL;<br /> }<br /> if(t->left==NULL)<br /> {<br /> return t;<br /> }<br /> return findMin(t->left);<br /> }<br /> //返回最大元素<br /> BinaryNode* findMax(BinaryNode* t)const<br /> {<br /> if(t!=NULL)<br /> {<br /> while(t->right!=NULL)<br /> {<br /> t=t->right;<br /> }<br /> }<br /> return t;<br /> }<br /> //判断是否包含某一元素<br /> bool contains(const Comparable& x,BinaryNode* t)const<br /> {<br /> if(t==NULL)<br /> {<br /> return false;<br /> }<br /> else if(x<t->element)<br /> {<br /> return contains(x,t->left);//递归调用<br /> }<br /> else if(x>t->element)<br /> {<br /> return contains(x,t->right);<br /> }<br /> else<br /> {<br /> return true;<br /> }<br /> }<br /> //清空树<br /> void makeEmpty(BinaryNode*& t)<br /> {<br /> if(t!=NULL)<br /> {<br /> makeEmpty(t->left);<br /> makeEmpty(t->right);<br /> delete t;<br /> }<br /> t=NULL;<br /> }<br /> //打印一棵树<br /> void printTree(BinaryNode* t)const<br /> {<br /> if(t==NULL)<br /> {<br /> return;<br /> }<br /> if(t->left!=NULL)<br /> {<br /> printTree(t->left);<br /> }<br /> std::cout<<t->element<<std::endl;<br /> printTree(t->right);</p> <p> }<br /> //克隆一棵树<br /> BinaryNode* clone(BinaryNode* t)const<br /> {<br /> if(t==NULL)<br /> {<br /> return NULL;<br /> }<br /> return new BinaryNode(t->element,clone(t->left),clone(t->right));<br /> }<br /> };<br />

测试代码

//============================================================================<br /> // Name : DT.cpp<br /> // Author : SJ<br /> // Version :<br /> // Copyright : Your copyright notice<br /> //============================================================================</p> <p>#include <iostream><br /> #include "BinarySearchTree.h"<br /> using namespace std;</p> <p>int main() {</p> <p> BinarySearchTree<int> binarySearchTree;//创建一个二差查找树</p> <p> //向树中插入值<br /> binarySearchTree.insert(5);<br /> binarySearchTree.insert(2);<br /> binarySearchTree.insert(38);<br /> binarySearchTree.insert(24);<br /> binarySearchTree.insert(4);<br /> binarySearchTree.insert(56);</p> <p> //从树中移除一个元素<br /> binarySearchTree.remove(4);</p> <p> int max = binarySearchTree.findMax();//返回树中的最大值<br /> int min = binarySearchTree.findMin();//返回树中的最小值</p> <p> cout<<"max="<<max<<endl;//输出最大值<br /> cout<<"min="<<min<<endl;//输出最小值</p> <p> bool isContains = binarySearchTree.contains(4);//判断树中是否包含一个元素</p> <p> cout<<"isContains 4:"<<isContains<<endl;</p> <p> bool isEmpty = binarySearchTree.isEmpty();//判断树是否为空</p> <p> cout<<"isEmpty:"<<isEmpty<<endl;</p> <p> binarySearchTree.printTree();//采用中序遍历打印树</p> <p> //复制构造函数<br /> BinarySearchTree<int> binarySearchTreeX(binarySearchTree);<br /> cout<<"new tree......"<<endl;<br /> binarySearchTreeX.printTree();</p> <p> return 0;<br /> }<br />

程序运行结果

max=56
min=2
isContains 4:0
isEmpty:0
2
5
24
38
56
new tree......
2
5
24
38
56