In C++ Given the following tnode class template: <template <typename T> class tn
ID: 3668379 • Letter: I
Question
In C++
Given the following tnode class template:
<template <typename T>
class tnode {
public:
T data;
tnode<T> *left, *right;
};
write the following functions:
(a)
template <typename T>
int occurs(tnode<T> *root, const T &elem);
This function returns the number of times elem appears in the tree whose root is root. Note that the tree may not be a binary search tree.
(b)
template <typename T>
bool equals(tnode<T> *root1, tnode<T> *root2);
This function returns true if the two binary trees have the same shape and value, i.e., if every corresponding pair of nodes in the two trees have the same value and the same number of children.
(c)
template <typename T>
bool search_tree(tnode<T> *root);
This function returns true if the binary tree with the given root is a binary search tree.
Explanation / Answer
Solution for Question A:
This below function will count the number of times given element is present in a tree.
template <typename T>
int occurs(tnode<T> *root, const T &elem)
{
tnode<T> *current = root;
int count = 0;
while (current != NULL)
{
if (current->data == elem)
count++;
current = current->next;
}
return count;
}
Solution for Question B:
This below function will compare the both the trees equal or not..if both the trees are equal in shape will return true else false.
template <typename T>
bool equals(tnode<T>* root1, tnode<T>* root2)
{
/*1. both empty */
if (root1==NULL && root2==NULL)
return 1;
/* 2. both non-empty -> compare them */
if (root1!=NULL && root2!=NULL)
{
return
(
root1->data == root2->data &&
identicalTrees(root1->left, root2->left) &&
identicalTrees(root1->right, root2->right)
);
}
/* 3. one empty, one not -> false */
return 0;
}
Solution for Question C:
Solution this function will return the given tree is binary search tree by just passing root node to
this below function.
template <typename T>
bool search_tree(tnode<T>* node)
{
if (node == NULL)
return 1;
/* false if left is > than node */
if (node->left != NULL && node->left->data > node->data)
return 0;
/* false if right is < than node */
if (node->right != NULL && node->right->data < node->data)
return 0;
/* false if, recursively, the left or right is not a BST */
if (!search_tree(node->left) || !search_tree(node->right))
return 0;
/* passing all that, it's a BST */
return 1;
}