If you can, please post the answer by tonight!!! Thanks!!!
----------------------
1. Using C++ design two data structures in order to implement a simple
binary tree. Do this as follows: First, implement a node structure that
references a single "FooBar" item. Second, implement a root structure that
references a single node.
CODE
/*
* This is the structure of a node in the Binary Tree
*/
struct TreeNode {
// An object of this TreeNode represents one node
// in a binary tree of strings.
string FooBar; // The data in this node.
TreeNode *left; // Pointer to left subtree.
TreeNode *right; // Pointer to right subtree.
TreeNode(string str = "") {
// This is the Constructor
// Make a node containing the specified string.
FooBar = str;
left = NULL;
right = NULL;
}
}; // end struct TreeNode
I don’t understand why need a structure for “root” node.
----
2. Implement the insert function for the binary tree you've just designed.
Assume that the function accepts the root of the binary tree, and the
"FooBar" item to be inserted. The resulting binary tree should not contain
duplicate values.
CODE
/*
* A recursive function named treeInsert is used to add the item to the binary sort tree to which the parameter "root" refers.
*/
void treeInsert(TreeNode *root, string newItem) {
// This sub function returns true if item is one of the items in the binary
// sort tree to which root points. Return false if not.
bool treeContains( TreeNode *root, string item ) {
if ( root == NULL ) {
// Empty tree
return false;
}
else if ( item == root->FooBar ) {
// Item being found in root node
return true;
}
else if ( item < root->Foobar ) {
// Search the lef tree
return treeContains( root->left, item );
}
else {
// Search the right tree
return treeContains( root->right, item );
}
} // end treeContains()
// Here begins the body of the insertion function
if ( root == NULL ) {
// Empty tree. Set root to point to a new node containing
// the new item. This becomes the only node in the tree.
root = new TreeNode( newItem );
return;
}
else if (treeContains(root, item)) {
// Do not insert if the item is already in the tree
cout << "\n That item is already in the tree. \n";
}
else if ( newItem < root->FooBar ) {
treeInsert( root->left, newItem );
}
else {
treeInsert( root->right, newItem );
}
}
} // end treeInsert()
----
3. Implement a non-recursive function that prints out the contents of the
"FooBar" items in order. Hint: You may need to modify the node structure
designed in section i) of this question in order to accomplish this
efficiently.
CODE
/ * Print the items in the tree in postorder, one item
* to a line.
*/
void traversalTree(TreeNode *root) {
stack stk;
TreeNode *temp;
if( root != NULL ) {
temp=root;
do {
while( temp != NULL) {
stk.push( temp );
temp = temp->left;
}/*end while*/
if( !stk.empty() ) {
temp = stk.pop();
cout<<” “ << temp->FooBar <<" ";
temp = temp->right;
}/*end if*/
else
break;
}while(1); /*end do while*/
}/* end if */
else
cout<<" Empty tree";
} /*end function */
16 Jul, 2007 - 01:27 PM
| 