bst.txt

资深C++讲师授课代码

#include <iostream>
using namespace std;

typedef int T;
class bst{
        struct Node{
                T data;
                Node* L;
                Node* R;
                Node(const T& d):data(d),L(0),R(0){++cnt;}
                static int cnt;
                ~Node(){--cnt;}
        };
        Node* root;
        static void clear(Node*& tr){
                if(tr==NULL) return;
                clear(tr->L);
                clear(tr->R);
                delete tr;
                tr = NULL;
        }
        static void travel(Node* tr){
                if(tr==NULL) return;
                travel(tr->L);
                cout << tr->data << ' ';
                travel(tr->R);
        }
        static void insert(Node*& tr, Node* p){
                if(tr==NULL) tr = p;
                else if(p->data < tr->data) insert(tr->L, p);
                else insert(tr->R, p);
        }
public:
        bst():root(NULL){}
        void clear(){clear(root);}
        void travel(){travel(root); cout<<endl;}
        int size(){return Node::cnt;}
        bool empty(){return root==NULL;}
        void insert(const T& d){insert(root, new Node(d));}
        bool erase(const T& d);
        bool find(const T& d);
        bool update(const T& od, const T& nd);
        ~bst(){clear();}
};
int bst::Node::cnt = 0;
int main()
{
        bst b;
        b.insert(53);
        b.insert(30);
        b.insert(72);
        b.insert(84);
        b.insert(61);
        b.insert(39);
        b.insert(14);
        b.insert(9);
        b.insert(23);
        b.insert(34);
        b.insert(47);
        b.insert(79);
        b.travel();
        cout << "count:" << b.size() << endl;
}

bash-2.05$