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

andalousie

还以为自己要卡在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 [_putIdx % maxPuts] = x;
                ++_putIdx;
        }
        
        bool empty() { return _putIdx == _getIdx; }
private:
        T   _arr [maxPuts];
        int _putIdx;
        int _getIdx;
};

template<typename T>
Queue<T>::Queue()
: _putIdx(0),
  _getIdx(0)
{}

#endif

BST.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)      return  1;
                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);
        }
};

#endif

main.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;
}

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

网络学习

错误找到了，

网络学习

谢谢分享经验

cable5881

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

黑暗漩涡

回帖是一种美德