C++版本的一个二叉搜索树(未平衡)

andalousie

还以为自己要卡在BST这儿了呢。上回的错误找到了，因为我没有用引用类型，导致了我的变量用完直接被销毁了。:ton:
是在不幸，我的g++编译器出问题了，只能回归vc6.0了，也好。vc6.0的debug功能挺不错的。
queue.h

1. #if !defined (QUEUE_H)
   
2. #define QUEUE_H
   
3. #include <cassert>
   
4. 
   
5. const int maxPuts=16;
   
6. 
   
7. template<typename T>
   
8. class Queue
   
9. {
   
10. public:
    
11.         Queue();
    
12.         
    
13.         T    pop()
    
14.         {
    
15.                 assert (_getIdx<_putIdx);
    
16.                 ++_getIdx;
    
17.                 return _arr [(_getIdx-1) % maxPuts];
    
18.         }
    
19.         
    
20.         void push(T x)
    
21.         {
    
22.                 assert (_putIdx < maxPuts + _getIdx);
    
23.                 _arr [_putIdx % maxPuts] = x;
    
24.                 ++_putIdx;
    
25.         }
    
26.         
    
27.         bool empty() { return _putIdx == _getIdx; }
    
28. private:
    
29.         T   _arr [maxPuts];
    
30.         int _putIdx;
    
31.         int _getIdx;
    
32. };
    
33. 
    
34. template<typename T>
    
35. Queue<T>::Queue()
    
36. : _putIdx(0),
    
37.   _getIdx(0)
    
38. {}
    
39. 
    
40. #endif

复制代码

BST.h

1. #if !defined (BST_H)
   
2. #defind BST_H
   
3. #include "queue.h"
   
4. 
   
5. template<typename Index, typename Value>
   
6. class BST
   
7. {
   
8. private:
   
9.         struct Node
   
10.         {
    
11.                 Node(Index k, Value v, int n)
    
12.                 :key(k), val(v), N(n), left(0), right(0)
    
13.                 {}
    
14.                 Index key;
    
15.                 Value val;
    
16.                 Node *left, *right;
    
17.                 int   N;
    
18.         };
    
19.         Node *root;
    
20. public:
    
21.         BST():root(0){}
    
22.         int   size()
    
23.         {
    
24.                 return size(root);
    
25.         }
    
26. 
    
27.         Index min()
    
28.         {
    
29.                 return min(root)->key;
    
30.         }
    
31. 
    
32.         Index floor(Index key)
    
33.         {
    
34.                 Node *x = floor(root, key);
    
35.                 if(!x) return 0;
    
36.                 return x->key;
    
37.         }
    
38. 
    
39.         Value get(Index key)
    
40.         {
    
41.                 return get(root, key);
    
42.         }
    
43. 
    
44.         void put(Index key, Value val)
    
45.         { // Search for key. Update value if found; grow table if new.
    
46.                 root = put(root, key, val);
    
47.         }
    
48. 
    
49.         Value select(int k)
    
50.         {
    
51.                 return select(root, k)->key;
    
52.         }
    
53. 
    
54.         int rank(Index key)
    
55.         {
    
56.                 return rank(key, root);
    
57.         }
    
58. 
    
59.         void delMin()
    
60.         {
    
61.                 root = delMin(root);
    
62.         }
    
63. 
    
64.         void del(Index key)
    
65.         {
    
66.                 root = del(root, key);
    
67.         }
    
68. 
    
69.         void iterate()
    
70.         {
    
71.                 Queue<Index> q;
    
72.                 inorder(root, q);
    
73.                 while(!q.empty())
    
74.                 {
    
75.                         Index key =  q.pop();
    
76.                         std::cout << get(key);
    
77.                 }
    
78.         }
    
79. private:
    
80.         int   size(Node *x)
    
81.         {
    
82.                 if(!x) return 0;
    
83.                 else   return x->N;
    
84.         }
    
85. 
    
86.         Node* min(Node* x)
    
87.         {
    
88.                 if(!(x->left)) return x;
    
89.                 return min(x->left);
    
90.         }
    
91. 
    
92.         Node* floor(Node* x, Index& key)
    
93.         {
    
94.                 if(!x) return 0;
    
95.                 int cmp = compare(key, x->key);
    
96. 
    
97.                 if (cmp == 0) return x;
    
98. 
    
99.                 if (cmp < 0) return floor(x->left, key);
    
100. 
     
101.                 Node* t = floor(x->right, key);
     
102.                 if(t) return t;
     
103.                 else return x;
     
104.         }
     
105.         
     
106.         Value get(Node *x, Index& key)
     
107.         { // Return value associated with key in the subtree rooted at x;
     
108.           // return null if key not present in subtree rooted at x.
     
109.                 if (!x) return 0;
     
110.                 int cmp = compare(key, x->key);
     
111.                 if (cmp < 0) return get(x->left, key);
     
112.                 else if (cmp > 0) return get(x->right, key);
     
113.                 else return x->val;
     
114.         }
     
115.         
     
116.         Node* put(Node* x, Index key, Value val)
     
117.         {
     
118.                 if(!x)
     
119.                 {
     
120.                         x = new Node(key, val, 1);
     
121.                         return x;
     
122.                 }
     
123.                 int cmp = compare(key, x->key);
     
124.                 if(cmp < 0)
     
125.                         x->left  = put(x->left, key, val);
     
126.                 else if(cmp > 0)
     
127.                         x->right = put(x->right, key, val);
     
128.                 else
     
129.                         x->val = val;
     
130.                 x->N = size(x->left) + size(x->right) + 1;
     
131.                 return x;
     
132.         }
     
133. 
     
134.         Node* select(Node* x, int& k)
     
135.         {   // Return Node containing key of rank k.
     
136.                 if(!x) return 0;
     
137.                 int t = size(x->left);
     
138.                 if (t > k) return select(x->left, k);
     
139.                 else if (t < k) return select(x->right, k-t-1);
     
140.                 else return x;
     
141.         }
     
142. 
     
143.         int   rank(Index& key, Node* x)
     
144.         {
     
145.                 if(!x) return 0;
     
146.                 int cmp = compare(key, x->key);
     
147.                 if (cmp < 0) return rank(key, x->left);
     
148.                 else if (cmp > 0) return 1 + size(x->left) + rank(key, x->right);
     
149.                 else return size(x->left);
     
150.         }
     
151. 
     
152.         Node* delMin(Node* x)
     
153.         {
     
154.                 if (!(x->left)) return x->right;
     
155.                 x->left = delMin(x->left);
     
156.                 x->N = 1 + size(x->left) + size(x->right);
     
157.                 return x;
     
158.         }
     
159. 
     
160.         Node* del(Node* x, Index& key)
     
161.         {
     
162.                 if(!x) return 0;
     
163.                 int cmp = compare(key, x->key);
     
164.                 /* search for key */
     
165.                 if (cmp < 0) x->left = del(x->left, key);
     
166.                 else if (cmp > 0) x->right = del(x->right, key);
     
167.                 else
     
168.                 {
     
169.                         if (!(x->right)) return x->left;            //no right child
     
170.                         if (!(x->left)) return x->right;           ;//no left child
     
171. 
     
172.                         /* replace with successor */
     
173.                         Node* t = x;
     
174.                         x = min(t->right);
     
175.                         x->right = delMin(t->right);
     
176.                         x->left = t->left;
     
177.                 }
     
178.                 x->N = size(x->left) + size(x->right) + 1; //update subtree counts
     
179.                 return x;
     
180.         }
     
181.         
     
182.         int   compare(Index& v, Index& w) const
     
183.         {
     
184.                 if(v > w)      return  1;
     
185.                 else if(v < w) return -1;
     
186.                 return 0;
     
187.         }
     
188. 
     
189.         void inorder(Node* x, Queue<Index>& q)
     
190.         {
     
191.                 if(!x) return;
     
192.                 inorder(x->left, q);
     
193.                 q.push(x->key);
     
194.                 inorder(x->right, q);
     
195.         }
     
196. };
     
197. 
     
198. #endif

复制代码

main.cpp

1. #include <iostream>
   
2. #include "BST.h"
   
3. 
   
4. int main()
   
5. {
   
6.         BST<int, int> bst;
   
7.         bst.put(5, 1);
   
8.         bst.put(9, 0);
   
9.         bst.put(2, 3);
   
10.         bst.put(1, 5);
    
11.         bst.put(4, 2);
    
12.         bst.put(8, 3);
    
13.         std::cout << bst.rank(1);
    
14.         std::cout << bst.rank(5);
    
15.         std::cout << bst.rank(9);
    
16.         std::cout << std::endl;
    
17.         bst.iterate();
    
18.         std::cout << std::endl;
    
19.         bst.delMin();
    
20.         bst.del(4);
    
21.         bst.iterate();
    
22.         return 0;
    
23. }

复制代码

就是分享一下。也可能会有问题，大家提出来便是。

网络学习

错误找到了，

网络学习

谢谢分享经验

cable5881

谢谢楼主分享！！！！！！！！

黑暗漩涡

回帖是一种美德