builds the binary treetreewith a user-specified number of

/in /by

builds the binary treetreewith a user-specified number of

Problem
Make a copy of both of theBTabstract data type files BT.hand BT.cnaming the copies BT2.hand BT2.c, respectively. Now, make the following changes to the BT2.hand BT2.csource files.
(1)Add the member function OutputBT()to theBTabstract data type. Traverse the binary tree*btin pre-order, as each node is visited, invoke the client-defined call-back function pointed-to byOutputElementto output the object pointed-to by theelementfield of the node. The output of each node object (except for the root’s object) is indented(3*depth)spaces’ ‘to visually indicate thedepthof the node, and, each node element (except for the root element) is prefixed with a'<‘or a’>’to indicate whether the object is “contained in” a left-child node or a right-child node, respectively.NoteIt is the private “helper” (utility) function OutputBT2()that does all the “heavy lifting” for public member function OutputBT().
//————————————————————–
void OutputBT(FILE *OUT,const BT *bt,
void (*OutputElement)(FILE *OUT,const BTNODE *node))
//————————————————————–
{
if ( bt->root == NULL )
fprintf(OUT,”(empty)n”);
else
OutputBT2(OUT,bt->root,NULL,0,OutputElement);
}
//————————————————————–
static void OutputBT2(FILE *OUT,const BTNODE *node,const BTNODE *parent,const int depth,
void (*OutputElement)(FILE *OUT,const BTNODE *node))
//————————————————————–
{
if ( node != NULL )
{
int i;
for (i = 1; i
fprintf(OUT,” “);
if ( parent != NULL )
if ( parent->LLink == node )
fprintf(OUT,”
else//( parent->RLink == node )
fprintf(OUT,”>”);
OutputElement(OUT,node);
fprintf(OUT,”n”);
OutputBT2(OUT,node->LLink,node,depth+1,OutputElement);
OutputBT2(OUT,node->RLink,node,depth+1,OutputElement);
}
}
(2)Add the member function IsInBT()to theBTabstract data type. Traverse the binary tree*btin pre-order, as each node is visited, compare the element “contained in” the node (that is, pointed-to by the nodeelementfield) with the element pointed-to by theelementformal parameter using thebool-returning call-back function pointed-to byEQ.NoteIt is the private “helper” (utility) function IsInBT2()that does all the “heavy lifting” for public member function IsInBT().
//————————————————————–
bool IsInBT(const BT *bt,const void *element,
bool (*EQ)(const void *LHS,const void *RHS))
//————————————————————–
{
bool isIn = false;
IsInBT2(bt->root,element,&isIn,EQ);
return( isIn );
}
//————————————————————–
void IsInBT2(const BTNODE *node,const void *element,bool *isIn,
bool (*EQ)(const void *LHS,const void *RHS))
//————————————————————–
{
Student provides missing code. HintThe IO parameter isIn is initialized
to false by IsInBT() in anticipation of the traversal of the
binary tree *bt by IsInBT2() that visits every node in the binary
tree and computes
*isIn = *isIn || EQ(element,node->element);
NoteThis is an$xistential quantification that answers the
question, “Does there exist a node in the binary tree whose
element, node->element, is equal-to the formal parameter element?”
}
Sample Program Dialog
Computational and Critical Thinking Questions
1. Draw a picture of thetreeshown below. Which is the root node? Which are the internal nodesand the external (leaf) nodes? How many levelsdoes the tree have? ______ What is the depthof node 2003? ______ What is the heightof the tree? ______
4001
>1005
>2006
2. From the Problem2.c(the client-application) point-of-view, theBTobjecttreeis a binary tree that contains
A: integers B: pointer-to integers C: generic pointers D: objects of unknown data type
3. From theBTabstract data type point-of-view,treeis a binary tree that contains
A: integers B: pointer-to integers C: generic pointers D: objects of unknown data type
4. Given the over-all design intent for theBTabstract data type, is it absolutely necessary that all the objects contained in a single binary tree must have exactly the same data type? In other words, is aBT-supported binary tree a homogeneouscontainer? From my dictionary, “homogeneous [Greek homogenesof the same kind]composed of parts or elements that are all of the same kind; not heterogeneous”
5. Problem2.cbuilds the binary treetreewith a user-specified number oflevels. Everyinternal node alwayshas a left-subtree, but the node has only a50%chance of having a right-subtree. Every node—internal andexternal—“contains” an integer computed as the composite(levels*1000+CSN)with (1) every node in the tree has a “level-in-the-tree” attribute, that is, the root of the tree is at the user-specifiedlevels, the children of the root are at(levels-1), the children of the children of the root are at(levels-2), et cetera, the leaves of the tree are at(levels = 1), and the non-existent children of the leaves of the tree are at(levels = 0); and (2) a (C)reation (S)equence (N)umber,CSN, such that theCSNof first node created is 1, theCSNof the second node created is 2, et cetera. T or F? Based solely on the node’s integer value, you should be able to determine where the node is in the tree andwhen the node was created.
6. The call by main()to the function RandomBT()is innocent looking: How does this simple call manage to build an entire binary tree?
SetRootBT(&tree,RandomBT(levels,&CSN));
7. (Continuing 6) What kind of binary tree does the function RandomBT() build when(levels = 0)?
8. (Continuing 6) By design,levelsis anINformal parameter andCSNis a [ A:IN B:OUT C:IO] formal parameter.
9. T or F? The changes to the variableCSNmade by the function RandomBT()are made to theCSNvariable defined in the Problem2.cfunction main().
10. (Continuing 9) T or F? The expression(levels*1000+(*CSN)++)increments the integer thatCSNpoints-to.
11 (Continuing 9) T or F? The post-incremented value ofCSNis used to compute the new node integer element value.
12. (Continuing 9) Why is theelement“contained” in the binarytreeroot node assigned the largest integer value of all nodes in the tree?
13.RandomBT()does dynamic memory allocation, but does not check the malloc()return value to ensure that the allocation request for a single integer was successful: Do you believe that this approach is an example of poor programming practice (that is, bad software engineering)? If you believe it is a sloppy way to handle the dynamic allocation, fix it with some code of your own.
int *element = (int *) malloc(sizeof(int));
14. Explain how the function that the function pointerEQIntpoints-to “works”.
if ( IsInBT(&tree,&element,EQInt) )
printf(“%d is in treen”,element);
else
printf(“%d is not in treen”,element);
15. T or F? If theBTdestructor member function DestructBT()is notcalled by the outerwhile-statement in the function main(), a memory resource leakwill result.
16. Why would you judge the Problem2.cfunction RandomBT()to be a naturally-recursive function? What is the RandomBT()base-case? The general-case?
17. (Continuing 16) T or F? Thereturn( NULL );statement in the base-case of the recursive function RandomBT()fullyexplains how both theLLinkandRLinkfields of everyone of the leaf nodes intreeget assignedNULLvalues.
18. (Continuing 16) T or F? The function RandomBT()buildstreefrom bottom-to-top; namely, it creates leaf nodes first and creates the root node last.
19. T or F? The return value of the function GetElementBTNODE()shown in the statement below mustbe cast because the return value is a generic pointer.
printf(“%4d “,*(int *) GetElementBTNODE(node));
20.Carefullystudy the relationship between the public member function OutputBT()and it’s utility function OutputBT2()and the very similar relationship between the public member function IsInBT()and it’s “helper” function IsInBT2(): Why is the “helper” function needed? In other words, why doesn’t it make sense to change the interface to the public member function to that used by its “helper” function thus doing away with the need for the “helper” function and thereby simplifying the implementation of theBTabstract data type?! NoteThe very same relationship and the very same “solution” to the complication of the implementation of theBTabstract data type are associated with allof the traversal public member functions PreOrderBT(), InOrderBT(), and PostOrderBT()and the DestructBT()public member function!
21. T or F? The reference to its “helper” function in the function OutputBT()shown below contains the actual parameterNULLbecause the root node of a non-empty tree does nothave a parent.
OutputBT2(bt->root,NULL,0,OutputElement);
22. Why does the “helper” function OutputBT2()need to “know” theparentofnode?
23. (Continuing 22) How many spaces is a(level = 3)node indented? ______
24. (Continuing 22) Why must the OutputBT2()operations parent->LLinkandparent->RLinkbe “guarded” by theif-statement condition( parent != NULL )?
if ( parent != NULL )
if ( parent->LLink == node )
fprintf(OUT,”
else//( parent->RLink == node )
fprintf(OUT,”>”);
25. Re-write the following OutputBT2()code using the’*’width specification described in the note below. QuestionDoes a 0 value “work” for a’*’width specification?
int i;
for (i = 1; i
printf(” “);
NoteBased on April 2000 MSDN
If the width specification is an asterisk’*’, an integer argument from the argument list supplies the value; the widthargument must precedethe value being formatted in the argument list.
26. T or F? The OutputBT()“helper” function OutputBT2()mustuse a pre-order traversal algorithm to satisfy its requirements because neither in-order nor post-order traversal algorithms will “work”.
27. T or F? The IsInBT()“helper” function IsInBT2()mustuse a pre-order traversal algorithm to satisfy its requirements because neither in-order nor post-order traversal algorithms will “work”.
28. By design, thedepthformal parameter in the interface to OuptutBT2()is a
[ A:IN B:OUT C:IO] parameter.
void OutputBT2(FILE *OUT,const BTNODE *node,const BTNODE *parent,const int depth,
void (*OutputElement)(FILE *OUT,const BTNODE *node));
29. By design, theisInformal parameter in the interface to IsInBT2()is a
[ A:IN B:OUT C:IO] parameter.
void IsInBT2(const BTNODE *node,const void *element,bool *isIn,
bool (*EQ)(const void *LHS,const void *RHS))
30. (Continuing 29) Normally, the algorithm to compute existential quantificationuses a loop (that is, afor-statement, awhile-statement, or ado/while-statement), but IsInBT2()uses recursion to iterate over all the nodes in the binary tree*bt. Why use recursion instead of a loop?
31. (Continuing 29) Explain how the following IsInBT2()statement “works”, especially explain what the call-back function pointerEQis used for.
*isIn = *isIn || EQ(element,node->element);
32. (Continuing 29) Why is a call-back function needed to satisfy IsInBT()requirements? HintDoes IsInBT2()“know” the data type of the objects that it must compare for equals?
33. (Continuing 29) FactisInand EQare both pointers (that is, are both main memory addresses), therefore T or F? ( sizeof(isIn) == sizeof(EQ) )
34. What is the essential difference between the Problem2.cfunctions DisplayInt()and OutputInt()?
void DisplayInt(BTNODE *node);
void OutputInt(FILE *OUT,const BTNODE *node);
35. Why are the LHSand the RHSformal parameters each designed as generic pointer-to const-ant for the Problem2.cfunction EQInt()?
bool EQInt(const void *LHS,const void *RHS);
//————————————————————–
// Dr. Art Hanna
// BT ADT Problem #2
// Problem2.c
//————————————————————–
#include
#include
#include
#include “.BT2.h”
#include “….Random.h”
//————————————————————–
int main()
//————————————————————–
{
BTNODE *RandomBT(int levels,int *CSN);
void DestructInt(const void *element);
void DisplayInt(BTNODE *node);
void OutputInt(FILE *OUT,const BTNODE *node);
bool EQInt(const void *LHS,const void *RHS);
int levels;
SetRandomSeed();
printf(“————————————————–n”);
printf(“levels? “);
while ( scanf(“%d”,&levels) != EOF )
{
BT tree;
int element,CSN = 1;
ConstructBT(&tree,DestructInt);
SetRootBT(&tree,RandomBT(levels,&CSN));
printf(“nTree isn——-n”);
OutputBT(stdout,&tree,OutputInt); printf(“nn”);
printf(“element? “);
while ( scanf(“%d”,&element) != EOF )
{
if ( IsInBT(&tree,&element,EQInt) )
printf(“%d is in treen”,element);
else
printf(“%d is not in treen”,element);
printf(“nelement? “);
}
DestructBT(&tree);
printf(“nlevels? “);
}
system(“PAUSE”);
return( 0 );
}
//————————————————————–
BTNODE *RandomBT(int levels,int *CSN)
//————————————————————–
{
if ( levels == 0 )
return( NULL );
else
{
int *element = (int *) malloc(sizeof(int));
BTNODE *root;
*element = levels*1000+(*CSN)++;
root = NewBTNODE(element);
SetLLinkBTNODE(root,RandomBT(levels-1,CSN));
if ( RandomBool(0.5) )
SetRLinkBTNODE(root,RandomBT(levels-1,CSN));
return( root );
}
}
//————————————————————–
void DestructInt(const void *element)
//————————————————————–
{
free((int *) element);
}
//————————————————————–
void DisplayInt(BTNODE *node)
//————————————————————–
{
printf(“%4d “,*(int *) GetElementBTNODE(node));
}
//————————————————————–
void OutputInt(FILE *OUT,const BTNODE *node)
//————————————————————–
{
fprintf(OUT,”%4d “,*(int *) GetElementBTNODE(node));
}
//————————————————————–
bool EQInt(const void *LHS,const void *RHS)
//————————————————————–
{
return( *(int *) LHS == *(int *) RHS );
}