3 Replies - 1109 Views - Last Post: 16 July 2007 - 09:41 PM Rate Topic: -----

#1 neokelly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 16-July 07

URGENT HELP, please review my code related to binary tree

Post icon  Posted 16 July 2007 - 02:27 PM

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.

/*
 * 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.


/*
 * 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.


/ * 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 */




Is This A Good Question/Topic? 0
  • +

Replies To: URGENT HELP, please review my code related to binary tree

#2 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: URGENT HELP, please review my code related to binary tree

Posted 16 July 2007 - 06:36 PM

Do you have a question?
Was This Post Helpful? 0
  • +
  • -

#3 neokelly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 16-July 07

Re: URGENT HELP, please review my code related to binary tree

Posted 16 July 2007 - 08:15 PM

View PostAmadeus, on 16 Jul, 2007 - 06:36 PM, said:

Do you have a question?


my question is: is the code correctly written?
Was This Post Helpful? 0
  • +
  • -

#4 MorphiusFaydal  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 43
  • View blog
  • Posts: 1,376
  • Joined: 12-May 05

Re: URGENT HELP, please review my code related to binary tree

Posted 16 July 2007 - 09:41 PM

Compile it. See if it works.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1