二叉搜索树实现(继承于二叉树)
1
#include "BinTree.h"
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
template<class K,class E>
4
class BinSearchTree:public BinTree<E>
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
6
public:
7
bool Search(const K &k,E &e);//以关键字K进行搜索,结果返回到e中
8
BinSearchTree<K,E>& Insert(const E &e);//将元素e插入到树中
9
BinSearchTree<K,E>& Delete(const K &k,E &e);//通过指定关键字k进行节点的删除
10![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
11
};
12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
13
//----------------------------------------------------------
14
template<class K,class E>
15
bool BinSearchTree<K,E>::Search(const K &k,E &e)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
17![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
18
BinTreeNode<E> *p=root;
19
while(p)
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
21
if(k<p->data)
22
p=p->LeftChild;
23
else if(k>p->data)
24
p=p->RightChild;
25
else//找到元素
26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
27
e=p->data;
28
return true;
29
}
30
}
31
return false;
32
}
33
//----------------------------------------------------------
34
template<class K,class E>
35
BinSearchTree<K,E>& BinSearchTree<K,E>::Insert(const E &e)
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
37![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
38
BinTreeNode<E> *p=root,*pp=NULL;
39
while(p)
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
41
pp=p;
42
if(e<=p->data)
43
p=p->LeftChild;
44
else
45
p=p->RightChild;
46
}
47![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
48
BinTreeNode<E> *NewNode=new BinTreeNode<E>(e);
49
if(root)
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
51
if(e<=pp->data)
52
pp->LeftChild=NewNode;
53
else
54
pp->RightChild=NewNode;
55
}
56
else
57
root=NewNode;
58
return *this;
59
}
60![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
61
//----------------------------------------------------------
62
template<class K,class E>
63
BinSearchTree<K,E>& BinSearchTree<K,E>::Delete(const K &k,E &e)
64![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
65
BinTreeNode<E> *p=root,*pp=NULL;
66![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
67
while(p&&p->data!=k)
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{pp=p;
69
if(k<p->data) p=p->LeftChild;
70
else p=p->RightChild;
71
}
72![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
73![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!p)
{throw exception("没有找到指定元素");}
74
e=p->data;
75
if(p->LeftChild&&p->RightChild)//p的左右孩子均不为空
76![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
77
BinTreeNode<E> *s=p->LeftChild,*ps=p;
78
while(s->RightChild)
79![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
80
ps=s;
81
s=s->RightChild;
82
}
83![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
84
p->data=s->data;
85
p=s;
86
pp=ps;
87
}//if
88
BinTreeNode<E> *c;
89
if(p->LeftChild) c=p->LeftChild;
90
else c=p->RightChild;
91![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
92
if(p==root) root=c;
93
else
94![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
95![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
96
if(p==pp->LeftChild) pp->LeftChild=c;
97
else pp->RightChild=c;
98
}
99
delete p;
100![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
101
return *this;
102
}
posted on 2008-09-18 17:17
杨彬彬 阅读(1220)
评论(0) 编辑 收藏 引用 所属分类:
数据结构