Question 8. Recursion and efficiency [9]
Below are the definitions for nodes in a linked list (lnodes) and nodes in a binary search tree (tnodes).
Below that are recursive functions to search the linked list (findL) and to search the tree (findT).
Below that are recursive functions to compare values across
the two data structures:
compareL returns true if every data value in the list
is also in the tree,
compareT returns true if every data value in the tree
is also in the list.
// structure of a list node
struct lnode {
float data;
lnode *next;
};
|
// structure of a tree node
struct tnode {
float data;
tnode *left, *right;
};
|
// recursively searches the list for value f
bool findL(float f, lnode *n)
{
if (!n) return false;
if (n->data == f) return true;
return findL(f, n->next);
}
|
// recursively searches the tree for value f
bool findT(float f, tnode *t)
{
if (!t) return false;
if (t->data == f) return true;
if (findT(f, t->left)) return true;
if (findT(f, t->right)) return true;
return false;
}
|
// return true if every value in the list
// is also in the tree,
// false otherwise
bool compareL(lnode *n, tnode *root)
{
if (n == NULL) return true;
cout << "searching tree for " << n->data << endl;
if (!findT(n->data, root)) return false;
if (!compareL(n->next, root)) return false;
return true;
}
|
// return true if every value in the tree
// is also in the list,
// false otherwise
bool compareT(tnode *t, lnode *front)
{
if (t == NULL) return true;
cout << "searching list for " << t->data << endl;
if (!findL(t->data, front)) return false;
if (!compareT(t->left, front)) return false;
if (!compareT(t->right, front)) return false;
return true;
}
|
Assuming we are working with large data sets, front is a pointer to the front list node and root is a pointer to the root tree node, the two data structures have the same set of data values stored, and we have a "good" binary search tree structure, answer the following questions: