esame-141008.cpp

#include <iostream>

using namespace std;

template <class H> class MultiBST{
    public:
        virtual MultiBST<H>* ins(H x) = 0;
        virtual int search(H x) = 0;
        virtual void inorder() = 0;
};

template <typename H> class Node{
    private:
        H key;
        int mul;
        Node<H> *parent, *left, *right;
    public:
        Node(H x){
            key = x;
            mul = 1;
            parent = left = right = NULL;
        }
        H getKey() { return key; }
        int getMul() { return mul; }
        Node<H>* getParent() { return parent; }
        Node<H>* getLeft() { return left; }
        Node<H>* getRight() { return right; }
        void setKey(H x){ key = x; }
        void setParent(Node<H> *par){ parent = par; }
        void setLeft(Node<H> *lef){ left = lef; }
        void setRight(Node<H> *rig){ right = rig; }
        void incMul(){ mul++; }
        void decMul(){ mul--; }
        int isLeaf() {
            if( left == NULL && right == NULL)
                return 1;
            return 0;
        }
        int onlyOneSon(){
            if(left!=NULL && right==NULL)
                return 1;
            else if(left==NULL && right!=NULL)
                return 2;
            return 0;
        }
};

template <typename H> class MyMultiBST: public MultiBST<H>{
    private:
        Node<H> *root;
    public:
        MyMultiBST(){ root = NULL; }
        int isEmpty(){
            if(root==NULL)
                return 1;
            return 0;
        }
        void _ins(Node<H> *aux, Node<H> *par, H x){
            if(aux!=NULL && aux->getKey() == x){
                aux->incMul();
                return;
            }
            if(aux==NULL){
                Node<H> *temp = new Node<H>(x);
                if(par==NULL){
                    root = temp;
                    return;
                }
                if( x < par->getKey() ){
                    par->setLeft(temp);
                    temp->setParent(par);
                    return;
                }
                else{
                    par->setRight(temp);
                    temp->setParent(par);
                    return;
                }
            }
            par = aux;
            if( x < aux->getKey() )
                aux = aux->getLeft();
            else
                aux = aux->getRight();
            _ins(aux, par, x);
        }
        MultiBST<H>* ins(H x){
            _ins(root, NULL, x);
            return this;
        }
        int search(H x){
            return 0;
        }
        void _inorder(Node<H> *aux){
            if(aux==NULL)
                return;
            _inorder(aux->getLeft());
            for(int i=0; i < aux->getMul(); i++) cout << aux->getKey() << " ";
            _inorder(aux->getRight());
        }
        void _postorder(Node<H> *aux){
            if(aux==NULL)
                return;
            _postorder(aux->getLeft());
            _postorder(aux->getRight());
            for(int i=0; i < aux->getMul(); i++) cout << aux->getKey() << " ";
        }
        void _preorder(Node<H> *aux){
            if(aux==NULL)
                return;
            _preorder(aux->getLeft());
            _preorder(aux->getRight());
            for(int i=0; i < aux->getMul(); i++) cout << aux->getKey() << " ";
        }
        void inorder(){
            _inorder(root);
            cout << endl;
        }
        void postorder(){
            _postorder(root);
            cout << endl;
        }
        void preorder(){
            _preorder(root);
            cout << endl;
        }
};
int main()
{
    MyMultiBST<int> *T = new MyMultiBST<int>();
    T->ins(10)->ins(5)->ins(2)->ins(7)->ins(17)->ins(12)->ins(3)->ins(15);
    T->inorder();
    T->postorder();
    T->preorder();
    return 0;
}