C++版本的一个二叉搜索树(未平衡)
本帖最后由 andalousie 于 2014-3-1 17:18 编辑还以为自己要卡在BST这儿了呢。上回的错误找到了，因为我没有用引用类型，导致了我的变量用完直接被销毁了。:ton:
是在不幸，我的g++编译器出问题了，只能回归vc6.0了，也好。vc6.0的debug功能挺不错的。
queue.h#if !defined (QUEUE_H)
#define QUEUE_H
#include <cassert>
const int maxPuts=16;
template<typename T>
class Queue
{
public:
Queue();
T pop()
{
assert (_getIdx<_putIdx);
++_getIdx;
return _arr [(_getIdx-1) % maxPuts];
}
void push(T x)
{
assert (_putIdx < maxPuts + _getIdx);
_arr = x;
++_putIdx;
}
bool empty() { return _putIdx == _getIdx; }
private:
T _arr ;
int _putIdx;
int _getIdx;
};
template<typename T>
Queue<T>::Queue()
: _putIdx(0),
_getIdx(0)
{}
#endifBST.h#if !defined (BST_H)
#defind BST_H
#include "queue.h"
template<typename Index, typename Value>
class BST
{
private:
struct Node
{
Node(Index k, Value v, int n)
:key(k), val(v), N(n), left(0), right(0)
{}
Index key;
Value val;
Node *left, *right;
int N;
};
Node *root;
public:
BST():root(0){}
int size()
{
return size(root);
}
Index min()
{
return min(root)->key;
}
Index floor(Index key)
{
Node *x = floor(root, key);
if(!x) return 0;
return x->key;
}
Value get(Index key)
{
return get(root, key);
}
void put(Index key, Value val)
{ // Search for key. Update value if found; grow table if new.
root = put(root, key, val);
}
Value select(int k)
{
return select(root, k)->key;
}
int rank(Index key)
{
return rank(key, root);
}
void delMin()
{
root = delMin(root);
}
void del(Index key)
{
root = del(root, key);
}
void iterate()
{
Queue<Index> q;
inorder(root, q);
while(!q.empty())
{
Index key =q.pop();
std::cout << get(key);
}
}
private:
int size(Node *x)
{
if(!x) return 0;
else return x->N;
}
Node* min(Node* x)
{
if(!(x->left)) return x;
return min(x->left);
}
Node* floor(Node* x, Index& key)
{
if(!x) return 0;
int cmp = compare(key, x->key);
if (cmp == 0) return x;
if (cmp < 0) return floor(x->left, key);
Node* t = floor(x->right, key);
if(t) return t;
else return x;
}
Value get(Node *x, Index& key)
{ // Return value associated with key in the subtree rooted at x;
// return null if key not present in subtree rooted at x.
if (!x) return 0;
int cmp = compare(key, x->key);
if (cmp < 0) return get(x->left, key);
else if (cmp > 0) return get(x->right, key);
else return x->val;
}
Node* put(Node* x, Index key, Value val)
{
if(!x)
{
x = new Node(key, val, 1);
return x;
}
int cmp = compare(key, x->key);
if(cmp < 0)
x->left= put(x->left, key, val);
else if(cmp > 0)
x->right = put(x->right, key, val);
else
x->val = val;
x->N = size(x->left) + size(x->right) + 1;
return x;
}
Node* select(Node* x, int& k)
{ // Return Node containing key of rank k.
if(!x) return 0;
int t = size(x->left);
if (t > k) return select(x->left, k);
else if (t < k) return select(x->right, k-t-1);
else return x;
}
int rank(Index& key, Node* x)
{
if(!x) return 0;
int cmp = compare(key, x->key);
if (cmp < 0) return rank(key, x->left);
else if (cmp > 0) return 1 + size(x->left) + rank(key, x->right);
else return size(x->left);
}
Node* delMin(Node* x)
{
if (!(x->left)) return x->right;
x->left = delMin(x->left);
x->N = 1 + size(x->left) + size(x->right);
return x;
}
Node* del(Node* x, Index& key)
{
if(!x) return 0;
int cmp = compare(key, x->key);
/* search for key */
if (cmp < 0) x->left = del(x->left, key);
else if (cmp > 0) x->right = del(x->right, key);
else
{
if (!(x->right)) return x->left; //no right child
if (!(x->left)) return x->right; ;//no left child
/* replace with successor */
Node* t = x;
x = min(t->right);
x->right = delMin(t->right);
x->left = t->left;
}
x->N = size(x->left) + size(x->right) + 1; //update subtree counts
return x;
}
int compare(Index& v, Index& w) const
{
if(v > w) return1;
else if(v < w) return -1;
return 0;
}
void inorder(Node* x, Queue<Index>& q)
{
if(!x) return;
inorder(x->left, q);
q.push(x->key);
inorder(x->right, q);
}
};
#endifmain.cpp#include <iostream>
#include "BST.h"
int main()
{
BST<int, int> bst;
bst.put(5, 1);
bst.put(9, 0);
bst.put(2, 3);
bst.put(1, 5);
bst.put(4, 2);
bst.put(8, 3);
std::cout << bst.rank(1);
std::cout << bst.rank(5);
std::cout << bst.rank(9);
std::cout << std::endl;
bst.iterate();
std::cout << std::endl;
bst.delMin();
bst.del(4);
bst.iterate();
return 0;
}就是分享一下。也可能会有问题，大家提出来便是。 错误找到了， 谢谢分享经验 谢谢楼主分享！！！！！！！！ 回帖是一种美德
页:
[1]