The class definition of a binary tree class is given below. It contains an attri

Question

The class definition of a binary tree class is given below.
It contains an attribute called root that represents the
root of a tree. It has a constructor that sets the root to
NULL. There are also other methods that manipulates the tree.
These methods are findLongestLength(), NumOfNodesDivisibleBy3(),
searchForAnElement() and printPreOrder(). The constructor is
already implemented. You are required to implement the other
four methods.

#include<iostream>
#include<string>
using namespace std;
//--------------------------------------------

class Node;
typedef Node* NodePtr;

class Node
{
public:
   int number;
   NodePtr left;
   NodePtr right;
   Node(){number=0; left=right=NULL;}
   Node(int n){number=n; left=right=NULL;}
};
//----------------------------------------------

class tree
{
public:
   NodePtr root;
   tree(){root=NULL;};
   int NumOfNodesDivisibleBy3(NodePtr root);
   int findLongestLength(NodePtr root);
   int searchForAnElement(NodePtr root, int key);
   int printPreOrder(NodePtr root);
};

Explanation / Answer

Complete Program

#include<iostream>
#include<string>
using namespace std;
//--------------------------------------------
class Node;
typedef Node* NodePtr;
class Node
{
public:
int number;
NodePtr left;
NodePtr right;
Node(){number=0; left=right=NULL;}
Node(int n){number=n; left=right=NULL;}
};
//----------------------------------------------
class tree
{
public:
NodePtr root;
tree(){root=NULL;};
int NumOfNodesDivisibleBy3(NodePtr root);
int findLongestLength(NodePtr root);
int searchForAnElement(NodePtr root, int key);
int printPreOrder(NodePtr root);
bool tree::Insert(Node *newNode);
void tree::printTree();
};

bool tree::Insert(Node *newNode)
{
Node *temp;
Node *back;

temp = root;
back = NULL;

while(temp != NULL) // Loop till temp falls out of the tree
{
back = temp;
if(newNode->number < temp->number)
temp = temp->left;
else
temp = temp->right;
}

// Now attach the new node to the node that back points to
if(back == NULL) // Attach as root node in a new tree
root = newNode;
else
{
if(newNode->number < back->number)
back->left = newNode;
else
back->right = newNode;
}
return true ;
}

int tree::NumOfNodesDivisibleBy3(NodePtr root)
{
int ValueInTree = false;
Node *temp;
   int c=0;
temp = root;
  
if(root!=NULL)
{
       if(root->number % 3 ==0)
           return 1+ NumOfNodesDivisibleBy3(root->left) + NumOfNodesDivisibleBy3(root->right);
       else
           return NumOfNodesDivisibleBy3(root->left) + NumOfNodesDivisibleBy3(root->right);
   }
   else return 0;
  
  
}
int tree::searchForAnElement(NodePtr root,int Key)
{
int ValueInTree = false;
Node *temp;

temp = root;
while((temp != NULL) && (temp->number != Key))
{
if(Key < temp->number)
temp = temp->left; // Search key comes before this node.
else
temp = temp->right; // Search key comes after this node
}
if(temp == NULL) return -1; // Search key not found
else
return(temp->number); // Found it so return a duplicate
}

int tree::findLongestLength(NodePtr node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = findLongestLength(node->left);
int rDepth = findLongestLength(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

int tree::printPreOrder(NodePtr root)
{
   if(root != NULL)
{
printPreOrder(root->left);
cout << root->number<<" - ";
printPreOrder(root->right);
}
}
void tree::printTree()
{
  
   printPreOrder(root);
}

int main()
{
   tree t;
   Node n(14), n1(11), n2(29),n3(20);
   t.Insert(&n);
   t.Insert(&n1);
   t.Insert(&n2);
   t.Insert(&n3);
   t.printTree();
  
   cout <<" Longest Length is "<< t.findLongestLength(t.root)<<endl;
   cout <<" Num divisibke by 3 is "<< t.NumOfNodesDivisibleBy3(t.root)<<endl;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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