mardi 18 octobre 2016

binary tree random insertion to left or right

im having a problem with the random insertion of a node into a binary tree, i know the basic implementation of binary trees however i have never used typedef enum in a program at all and in fact this is the first time ive ever had to use it. can anyone point me in the right direction of how i would implement the typedef statement into my program so that a new node will be created randomly in the right or left subtree?

this is the typedef statement i have to use and have no idea how to use.

 typedef enum { left_side, right_side } SIDE;
 SIDE rnd ( ) { return rand ( ) % 2 ? right_side : left_side; }

this is my binary tree class and the insertion function.

template < class T > class binTree {
    public:
        binTree ( ); // default constructor
        unsigned height ( ) const; // returns height of tree
        virtual void insert ( const T& ); // inserts a node in tree
        void inorder ( void ( * ) ( const T& ) ); // inorder traversal of tree
    protected:
        Node < T >* root; // root of tree
    private:
        unsigned height ( Node < T >* ) const; // private version of height ( )
        void insert ( Node < T >*&, const T& ); // private version of insert ( )
        void inorder ( Node < T >*, void ( * ) ( const T& ) ); // private version of inorder ( )
};

 // inserts a node in shortest subtree
template <class T>
void binTree <T>::insert( const T& v )
{ //thi is how i am used to  inserting into binary trees
    insert( root, v ); // call recursive
}

//private version of insert
template <class T>
void binTree <T>::insert( Node <T>* & p, const T& v )
{

     if( p == NULL )
     {
        Node <T> * newNode;
        newNode = new Node <T>( v ); // new node with new value
        p = newNode; // set ptr to new node
     }

    else
    {
        int lHeight = height( p->left );
        int rHeight = height( p->right );

        if( lHeight <= rHeight )
        {
            insert( p->left, v );
        }
        else
        {
            insert( p->right, v );
        }
    }
}




Aucun commentaire:

Enregistrer un commentaire