二叉搜索樹實現(xiàn)(繼承于二叉樹)
1
#include "BinTree.h"
2
3template<class K,class E>
4class BinSearchTree:public BinTree<E>
5
{
6
public:
7 bool Search(const K &k,E &e);//以關(guān)鍵字K進行搜索，結(jié)果返回到e中
8 BinSearchTree<K,E>& Insert(const E &e);//將元素e插入到樹中
9 BinSearchTree<K,E>& Delete(const K &k,E &e);//通過指定關(guān)鍵字k進行節(jié)點的刪除
10
11
};
12
13//----------------------------------------------------------
14template<class K,class E>
15bool BinSearchTree<K,E>::Search(const K &k,E &e)
16{
17
18BinTreeNode<E> *p=root;
19while(p)
20
{
21if(k<p->data)
22p=p->LeftChild;
23else if(k>p->data)
24p=p->RightChild;
25else//找到元素
26{
27e=p->data;
28return true;
29
}
30}
31return false;
32}
33//----------------------------------------------------------
34template<class K,class E>
35BinSearchTree<K,E>& BinSearchTree<K,E>::Insert(const E &e)
36{
37
38BinTreeNode<E> *p=root,*pp=NULL;
39while(p)
40{
41pp=p;
42if(e<=p->data)
43p=p->LeftChild;
44else
45p=p->RightChild;
46}
47
48BinTreeNode<E> *NewNode=new BinTreeNode<E>(e);
49if(root)
50{
51if(e<=pp->data)
52pp->LeftChild=NewNode;
53else
54pp->RightChild=NewNode;
55}
56else
57 root=NewNode;
58return *this;
59}
60
61//----------------------------------------------------------
62template<class K,class E>
63BinSearchTree<K,E>& BinSearchTree<K,E>::Delete(const K &k,E &e)
64{
65BinTreeNode<E> *p=root,*pp=NULL;
66
67while(p&&p->data!=k)
68{pp=p;
69if(k<p->data) p=p->LeftChild;
70else p=p->RightChild;
71}
72
73if(!p) {throw exception("沒有找到指定元素");}
74e=p->data;
75if(p->LeftChild&&p->RightChild)//p的左右孩子均不為空
76{
77BinTreeNode<E> *s=p->LeftChild,*ps=p;
78while(s->RightChild)
79{
80ps=s;
81s=s->RightChild;
82}
83
84p->data=s->data;
85p=s;
86pp=ps;
87}//if
88BinTreeNode<E> *c;
89if(p->LeftChild) c=p->LeftChild;
90else c=p->RightChild;
91
92if(p==root) root=c;
93else
94{
95
96if(p==pp->LeftChild) pp->LeftChild=c;
97else pp->RightChild=c;
98}
99delete p;
100
101return *this;
102}
posted on 2008-09-18 17:17
楊彬彬 閱讀(1237)
評論(0) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)