Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

Add two functions to a binary tree class. The first function returns an array li

ID: 3580541 • Letter: A

Question

Add two functions to a binary tree class. The first function  returns an array list or vector. It is modified version of the public in order tree traversal function. The first function invokes the second function, a modified version of the private in order tree traversal function. The second function copies the tree nodes' data to the array list or vector as it visits each node.  .

Write a program to test your function.

binaryTree.h

#ifndef H_binaryTree
#define H_binaryTree
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
struct binaryTreeNode
{
elemType info;
binaryTreeNode<elemType> *llink;
binaryTreeNode<elemType> *rlink;
};

template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty() const;
void inorderTraversal() const;
void preorderTraversal() const;
void postorderTraversal() const;
int treeHeight() const;
int treeNodeCount() const;
int treeLeavesCount() const;
   int singleParent()const;
   //function to determine the nubmer of nodes that are single
void destroyTree();
binaryTreeType(const binaryTreeType<elemType>& otherTree);
binaryTreeType();   
~binaryTreeType();   
protected:
binaryTreeNode<elemType> *root;

private:
void copyTree(binaryTreeNode<elemType>* &copiedTreeRoot,
binaryTreeNode<elemType>* otherTreeRoot);
void destroy(binaryTreeNode<elemType>* &p);
void inorder(binaryTreeNode<elemType> *p) const;
void preorder(binaryTreeNode<elemType> *p) const;
void postorder(binaryTreeNode<elemType> *p) const;
int height(binaryTreeNode<elemType> *p) const;
int max(int x, int y) const;
int nodeCount(binaryTreeNode<elemType> *p) const;
int leavesCount(binaryTreeNode<elemType> *p) const;

   int singleP(binaryTreeNode<elemType> *p) const;
   //parent in the binary tree to which P points.
};
template <class elemType>
int binaryTreeType<elemType>::singleParent()const
{
   return singleP(root);
}
template <class elemType>
int binaryTreeType<elemType>::singleP(binaryTreeNode<elemType> *p)const
{
   if (p == NULL)
       return 0;
   else if (p->llink == NULL && p->rlink != NULL)
       return 1 + singleP(p->rlink);
   else if (p->llink != NULL && p->rlink == NULL)
       return 1 + singleP(p->llink);
   else
       return singleP(p->llink) + singleP(p->rlink);
}
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}

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

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

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

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

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

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

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

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

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

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

template <class elemType>
void binaryTreeType<elemType>::postorder(binaryTreeNode<elemType> *p) const
{
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(binaryTreeNode<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(binaryTreeNode<elemType> *p) const
{
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) const
{
if (x >= y)
return x;
else
return y;
}

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

return 0;
}

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

return 0;
}

#endif

Explanation / Answer

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree


#include <iostream>

using namespace std;

     //Definition of the node
template <class elemType>
struct binaryTreeNode
{
    elemType info;
    binaryTreeNode<elemType> *llink;
    binaryTreeNode<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() const;
      //Returns true if the binary tree is empty;
      //otherwise, returns false.
    void inorderTraversal() const;
      //Function to do an inorder traversal of the binary tree.
    void preorderTraversal() const;
      //Function to do a preorder traversal of the binary tree.
    void postorderTraversal() const;
      //Function to do a postorder traversal of the binary tree.

    int treeHeight() const;
      //Returns the height of the binary tree.
    int treeNodeCount() const;
      //Returns the number of nodes in the binary tree.
    int treeLeavesCount() const;
      //Returns the number of leaves in the binary tree.
    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:
    binaryTreeNode<elemType> *root;

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

    void destroy(binaryTreeNode<elemType>* &p);
      //Function to destroy the binary tree to which p points.
      //Postcondition: p = NULL

    void inorder(binaryTreeNode<elemType> *p) const;
      //Function to do an inorder traversal of the binary
      //tree to which p points.
    void preorder(binaryTreeNode<elemType> *p) const;
      //Function to do a preorder traversal of the binary
      //tree to which p points.
    void postorder(binaryTreeNode<elemType> *p) const;
      //Function to do a postorder traversal of the binary
      //tree to which p points.

    int height(binaryTreeNode<elemType> *p) const;
      //Function to return the height of the binary tree
      //to which p points.
    int max(int x, int y) const;
      //Returns the larger of x and y.
    int nodeCount(binaryTreeNode<elemType> *p) const;
      //Function to return the number of nodes in the binary
      //tree to which p points
    int leavesCount(binaryTreeNode<elemType> *p) const;
      //Function to return the number of leaves in the binary
      //tree to which p points
};

    //Definition of member functions

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

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

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

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

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

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

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

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

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

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

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

template <class elemType>
void binaryTreeType<elemType>::postorder(binaryTreeNode<elemType> *p) const
{
    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(binaryTreeNode<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(binaryTreeNode<elemType> *p) const
{
    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) const
{
    if (x >= y)
        return x;
    else
        return y;
}

template <class elemType>
int binaryTreeType<elemType>::nodeCount(binaryTreeNode<elemType> *p) const
{
    if (p == NULL)
       return 0;
   else
       return 1 + nodeCount(p -> llink) + nodeCount(p -> rlink);
}

template <class elemType>
int binaryTreeType<elemType>::leavesCount(binaryTreeNode<elemType> *p) const
{
    if (p == NULL)
       return 0;
   else
       if (p -> llink == NULL && p -> rlink == NULL)
           return 1;
       else
           return leavesCount(p -> llink) + leavesCount(p -> rlink);
}

#endif

Related Questions

Add the following method to the Point class: public void flip() Negates and swap
Question #3680310
Add the following method to your Line class: Returns true if the given point is
Question #645062
Add the following methods to ArrayList and LinkedList implementations (code for
Question #3605074
Add the following methods to the Array Bounded Stack class, and create a test dr
Question #3793098
Add the following methods to the ArrayBoundedStack class Add the following metho
Question #3792764
Add the following methods to the ArrayList class that we wrote during lecture. Y
Question #3603258
Add the following methods to the ArrayList class that we wrote during lecture. Y
Question #3606152
Add the following methods to the ArrayList class that we wrote during lecture. Y
Question #3607019
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
Chat Now And Get Quote

Navigate

Previous
Add two functions to a binary tree class. The first function returns an array li
Next
Add two more statements to main() to test inputs 3 and -1. Use print statements

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.