二叉探索ツリーC++実装
1、二叉検索ツリー
2、main.cpp
Bin_Search_tree.h
1
2 #include <iostream>
3 using namespace std;
4
5 template<class T>
6 struct BSTNode
7 {
8 T data;
9 BSTNode<T> *leftchild,*rightchild;
10 BSTNode(const T d=T())
11 :data(d),leftchild(NULL),rightchild(NULL)
12 {}
13 };
14
15 template<class T>
16 class BSTree
17 {
18 private:
19 T _value;
20 BSTNode<T> *root;
21 public:
22 BSTree(const T value=T()):_value(value),root(NULL)
23 {}
24 private:
25 BSTNode<T>* search(const T key,BSTNode<T> *cur)
26 {
27 if(cur==NULL)
28 return NULL;
29 if(key==cur->data)
30 return cur;
31 else if(key <cur->data)
32 search(key,cur->leftchild);
33 else if(key > cur->data)
34 search(key,cur->rightchild);
35 }
36 private:
37
38 void insert(const T key,BSTNode<T> *&cur)
39 {
40 //BSTNode<T> *tmp=search(key,cur);
41 if(cur==NULL)
42 {
43 cur=new BSTNode<T>(key);
44 //cur=tmp;
45 }else if(key <cur->data)
46 insert(key,cur->leftchild);
47 else if(key > cur->data)
48 insert(key,cur->rightchild);
49 else
50 return;
51 }
52 void InOrder(BSTNode<T> *cur)
53 {
54 if(cur !=NULL)
55 {
56 InOrder(cur->leftchild);
57 cout<<cur->data<<" ";
58 InOrder(cur->rightchild);
59 }
60 }
61 void Remove(BSTNode<T> *&cur,const T key)
62 {
63 BSTNode<T> *tmp=NULL;
64 if(cur !=NULL)
65 {
66 if(cur->data > key)
67 Remove(cur->leftchild,key);
68 else if(cur->data < key)
69 Remove(cur->rightchild,key);
70 else if(cur->leftchild !=NULL && cur->rightchild !=NULL)
71 {
72 tmp=cur->rightchild;
73 while(tmp->leftchild !=NULL)
74 tmp=tmp->leftchild;
75 cur->data=tmp->data;
76 Remove(cur->rightchild,cur->data);
77 //Remove(cur->data,cur->rightchild);
78 }else
79 {
80 tmp=cur;
81 if(cur->leftchild==NULL)
82 cur=cur->rightchild;
83 else
84 cur=cur->leftchild;
85 delete tmp;
86 tmp=NULL;
87 }
88 }
89 }
90 public:
91
92 void remove(const T key)
93 {
94 Remove(root,key);
95 }
96 void get(const T key)
97 {
98 BSTNode<T> *cur=search(key,root);
99 if(cur !=NULL)
100 cout<<cur->data<<endl;
101 else
102 cout<<"not found"<<endl;
103 }
104 void create(const T value)
105 {
106 insert(value,root);
107 }
108 void insert(const T key)
109 {
110 insert(key,root);
111 }
112 public:
113 void InOrder()
114 {
115 InOrder(root);
116 }
117 };
2、main.cpp
2 #include "Bin_Search_tree.h"
3
4 int main()
5 {
6 BSTree<int> t;
7 cout<<"please enter value:";
8 int value=0;
9 while(cin>>value && value !=-1)
10 t.create(value);
11 t.InOrder();
12 cout<<"
please enter value:";
13 cin>>value;
14 t.get(value);
15 cout<<"
please enter value:";
16 cin>>value;
17 t.remove(value);
18 t.InOrder();
19
20 cout<<"
********end**********"<<endl;
21 return 0;
22 }