Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  dadada
Language: C/C++
Code:
// Ali Abdulnabi Alsaif 20146976 
#include <iostream>
#include <cassert>


using namespace std;

     //Definition of the node
template<class elemType>
struct nodeType
{
   elemType                info;
   nodeType<elemType>  *llink;
   nodeType<elemType>  *rlink;
};

    //Definition of the class
template <class elemType>
class binaryTreeType
{
public:
    const binaryTreeType<elemType>& operator=
                 (const binaryTreeType<elemType>&); 
      //Overload the assignment operator.
    bool isEmpty();
      //Function to determine if the binary tree is empty.
      //Postcondition: Returns true if the binary tree is empty;
      //               otherwise, returns false.
    void inorderTraversal();
      //Function to do an inorder traversal of the binary tree.
      //Postcondition: The nodes of the binary tree are output
      //               in the inorder sequence.
    void preorderTraversal();
      //Function to do a preorder traversal of the binary tree.
      //Postcondition: The nodes of the binary tree are output
      //               in the preorder sequence.
    void postorderTraversal();
      //Function to do a postorder traversal of the binary tree.
      //Postcondition: The nodes of the binary tree are output
      //               in the postorder sequence.

    int treeHeight();
      //Function to deteremine the height of the binary tree.
      //Postcondition: The height of the binary tree is returned.
    int treeNodeCount();
      //Function to determine the number of nodes in the 
      //binary tree.
      //Postcondition: The number of nodes in the binary tree
      //               is returned.
    int treeLeavesCount();
      //Function to determine the number of leaves in the 
      //binary tree.
      //Postcondition: The number of leaves in the binary tree
      //               is returned.
    void destroyTree();
      //Deallocates the memory space occupied by the binary tree.
      //Postcondition: root = NULL;

    binaryTreeType(const binaryTreeType<elemType>& otherTree); 
      //copy constructor

    binaryTreeType();   
      //default constructor

    ~binaryTreeType();   
      //destructor

protected:
    nodeType<elemType> *root;

private:
    void copyTree(nodeType<elemType>* &copiedTreeRoot,
                  nodeType<elemType>* otherTreeRoot);
      //Function to make a copy of the binary tree to 
      //which otherTreeRoot points. 
      //Postcondition: The pointer copiedTreeRoot points to
      //               the root of the copied binary tree.

    void destroy(nodeType<elemType>* &p);
      //Function to destroy the binary tree to which p points. 
      //Postcondition: The nodes of the binary tree to which
      //               p points are deallocated.
      //               p = NULL.

    void inorder(nodeType<elemType> *p);
      //Function to do an inorder traversal of the binary
      //tree to which p points.  
      //Postcondition: The nodes of the binary tree to which p
      //               points are output in the inorder sequence.
    void preorder(nodeType<elemType> *p);
      //Function to do a preorder traversal of the binary
      //tree to which p points.  
      //Postcondition: The nodes of the binary tree to which p
      //               points are output in the preorder sequence.
    void postorder(nodeType<elemType> *p);
      //Function to do a postorder traversal of the binary
      //tree to which p points.  
      //Postcondition: The nodes of the binary tree to which p
      //               points are output in the postorder sequence.

    int height(nodeType<elemType> *p);
      //Function to determine the height of the binary tree
      //to which p points. 
      //Postcondition: The height of the binary tree to which p
      //               points is returned.

    int max(int x, int y);
      //Function to determine the larger of x and y.
      //Postcondition: The larger of x and y is returned.

    int nodeCount(nodeType<elemType> *p);
      //Function to determine the number of nodes in the binary 
      //tree to which p points. 
      //Postcondition: The number of nodes in the binary tree
      //               to which p points is returned.

    int leavesCount(nodeType<elemType> *p);
      //Function to determine the number of leaves in the binary 
      //tree to which p points.
      //Postcondition: The number of nodes in the binary tree
      //               to which p points is returned.
};

     //Definition of member functions

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
     root = NULL;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
     return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
     inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
     preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
     postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
     return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
     return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
     return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
                      (nodeType<elemType>* &copiedTreeRoot,
                         nodeType<elemType>* otherTreeRoot)
{
     if(otherTreeRoot == NULL)
          copiedTreeRoot = NULL;
     else
     {
          copiedTreeRoot = new nodeType<elemType>;
          copiedTreeRoot->info = otherTreeRoot->info;
          copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
          copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
     }
} //end copyTree

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
     if(p != NULL)
     {
          inorder(p->llink);
          cout<<p->info<<" ";
          inorder(p->rlink);
     }
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
     if(p != NULL)
     {
          cout<<p->info<<" ";
          preorder(p->llink);
          preorder(p->rlink);
     }
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
     if(p != NULL)
     {
          postorder(p->llink);
          postorder(p->rlink);
          cout<<p->info<<" ";
     }          
}

   //Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
           operator=(const binaryTreeType<elemType>& otherTree)

     
     if(this != &otherTree) //avoid self-copy
     {
          if(root != NULL)  //if the binary tree is not empty, 
                             //destroy the binary tree
               destroy(root);

          if(otherTree.root == NULL) //otherTree is empty
               root = NULL;
          else
               copyTree(root, otherTree.root);
     }//end else

   return *this; 
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
     if(p != NULL)
     {
          destroy(p->llink);
          destroy(p->rlink);
          delete p;
          p = NULL;
     }
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
     destroy(root);
}

     //copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
              (const binaryTreeType<elemType>& otherTree)
{
     if(otherTree.root == NULL) //otherTree is empty
          root = NULL;
     else
          copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
     destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
{
     if(p == NULL)
          return 0;
     else
          return 1 + max(height(p->llink), height(p->rlink));
}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
{
     if(x >= y)
          return x;
     else
          return y;
}

template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
{
     cout<<"Write the definition of the function nodeCount"
          <<endl;

     return 0;
}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
     cout<<"Write the definition of the function leavesCount"
          <<endl;

     return 0;
}
template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
    bool search(const elemType& searchItem);
      //Function to determine if searchItem is in the binary 
      //search tree.
      //Postcondition: Returns true if searchItem is found in the 
      //             binary search tree; otherwise, returns false.

    void insert(const elemType& insertItem);
      //Function to insert insertItem in the binary search tree.
      //Postcondition: If no node in the binary search tree has 
      //           the same info as insertItem, a node with the 
      //           info insertItem is created and inserted in the
      //binary search tree.

    void deleteNode(const elemType& deleteItem);
      //Function to delete deleteItem from the binary search tree 
      //Postcondition: If a node with the same info as deleteItem 
      //               is found, it is deleted from the binary 
      //               search tree.

private:
    void deleteFromTree(nodeType<elemType>* &p);
      //Function to delete the node, to which p points, from the 
      //binary search tree.
      //Postcondition: The node to which p points is deleted
      //               from the binary search tree.
};


template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
    nodeType<elemType> *current;
    bool found = false;

    if(root == NULL)
       cerr<<"Cannot search the empty tree."<<endl;
    else
    { 
       current = root;

       while(current != NULL && !found)
       {
             if(current->info == searchItem)
                found = true;
              else
                  if(current->info > searchItem)
                     current = current->llink;
                  else
                     current = current->rlink;
       }//end while
    }//end else

    return found;
}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
    nodeType<elemType> *current;  //pointer to traverse the tree
    nodeType<elemType> *trailCurrent; //pointer behind current
    nodeType<elemType> *newNode;  //pointer to create the node

    newNode = new nodeType<elemType>;
    assert(newNode != NULL);
    newNode->info = insertItem;
    newNode->llink = NULL;
    newNode->rlink = NULL;

    if(root == NULL)
       root = newNode;
    else
    {
       current = root;
 
       while(current != NULL)
       {
           trailCurrent = current;

           if(current->info == insertItem)
           {
              cerr<<"The insert item is already in the list -- ";
              cerr<<"duplicates are not allowed."<<endl;
              return;
           }
           else
              if(current->info > insertItem)
                 current = current->llink;
              else
                 current = current->rlink;
       }//end while

       if(trailCurrent->info > insertItem)
          trailCurrent->llink = newNode;
       else
          trailCurrent->rlink = newNode;
   }
}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
     nodeType<elemType> *current;  //pointer to traverse the tree
     nodeType<elemType> *trailCurrent; //pointer behind current
     bool found = false;

     if(root == NULL)
          cerr<<"Cannot delete from the empty tree."<<endl;
     else
     {
          current = root;
          trailCurrent = root;

          while(current != NULL && !found)
          {
               if(current->info == deleteItem)
                    found = true;
               else
               {
                    trailCurrent = current;

                    if(current->info > deleteItem)
                         current = current->llink;
                    else
                         current = current->rlink;
               }
          }//end while

          if(current == NULL)
               cout<<"The delete item is not in the tree."<<endl;
          else
               if(found)
               {
                    if(current == root)
                         deleteFromTree(root);
                    else
                         if(trailCurrent->info > deleteItem)
                              deleteFromTree(trailCurrent->llink);
                         else
                              deleteFromTree(trailCurrent->rlink);
               }//end if
     }
}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
                                 (nodeType<elemType>* &p)
{
     nodeType<elemType> *current;    //pointer to traverse 
                                     //the tree
     nodeType<elemType> *trailCurrent;   //pointer behind current
     nodeType<elemType> *temp;        //pointer to delete the node

     if(p == NULL)
        cerr<<"Error: The node to be deleted is NULL."
            <<endl;
     else if(p->llink == NULL && p->rlink == NULL)
          {
             temp = p;
             p = NULL;
             delete temp;
          }
     else if(p->llink == NULL)
          {
             temp = p;
             p = temp->rlink;
             delete temp;
          }
     else if(p->rlink == NULL)
          {
             temp = p;
             p = temp->llink;
             delete temp;
          }
     else
     {
        current = p->llink;
        trailCurrent = NULL;

        while(current->rlink != NULL)
        {
            trailCurrent = current;
            current = current->rlink;
        }//end while

        p->info = current->info;

        if(trailCurrent == NULL) //current did not move; 
                                 //current == p->llink; adjust p
           p->llink = current->llink;
        else
           trailCurrent->rlink = current->llink;
 
        delete current;
     }//end else
}//end deleteFromTree

int main()
{
     bSearchTreeType<int> bst;
     bst.insert(100);
     bst.insert(40);
     bst.insert(20);
     bst.insert(15);
     bst.insert(30);
     bst.insert(40);
     bst.insert(35);
     bst.insert(77);
     bst.treeHeight();
     bst.treeNodeCount();
     bst.treeLeavesCount();
     bst.inorderTraversal();
     bst.preorderTraversal();
     bst.postorderTraversal();
     bst.deleteNode(30);
     bst.deleteNode(35);
     bst.treeNodeCount();
     
     return 0;
}

Comments: