# how to apply Binary Sort Tree to my program

Page 1 of 1

## 3 Replies - 6396 Views - Last Post: 16 June 2007 - 08:33 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=29415&amp;s=32e63afc3e6b55ef87030fc85a7b1ee6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 yeungsam

Reputation: 0
• Posts: 2
• Joined: 14-June 07

# how to apply Binary Sort Tree to my program

Posted 14 June 2007 - 09:32 AM

would anyone teaching me how to correct or amend the sort tree program into my task1 program. i need as below:
a) Form an array of words which occur in at least 10 sentences.
Create a binary sort tree comprised of the common words given in a).
c) Scan this binary sort tree created in so that the words can be printed in the descending order.

binary sort tree program:
```/*

This program demonstrates a few routines for processing binary
sort trees.  It uses a binary sort tree of strings.  The user
types in strings.  The user's string is converted to lower case, and --
if it is not already in the tree -- it is inserted into the tree.
Then the number of nodes in the tree and a list of items in the tree
are output.  The program ends when the user enters an empty string.
*/

#include <iostream>
#include <string>

using namespace std;  //<string>

struct TreeNode {
// An object of type TreeNode represents one node
// in a binary tree of strings.

//  A variable in the main program of type pointer-to-TreeNode points to the binary sort tree that
//  is used by the program:
//  TreeNode *root;  // Pointer to the root node in the tree.

string item;	   // The data in this node.
TreeNode *left;	// Pointer to left subtree.
TreeNode *right;   // Pointer to right subtree.
TreeNode(string str = "") {
// Constructor, defined for convenience.
// Make a node containing the specified string.
item = str;
left = NULL;
right = NULL;
}
};  // end struct TreeNode

void treeInsert(TreeNode *&root, string newItem) {
// Add the item to the binary sort tree to which the parameter
// "root" refers.  Note that root is passed by reference since
// its value can change in the case where the tree is empty.
if ( root == NULL ) {
// The tree is empty.  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 ( newItem < root->item ) {
treeInsert( root->left, newItem );
}
else {
treeInsert( root->right, newItem );
}
}  // end treeInsert()

//A recursive function named treeContains is used to search for a given item in the tree.
//This routine implements the search algorithm for binary trees that was outlined above:
bool treeContains( TreeNode *root, string item ) {
// Return true if item is one of the items in the binary
// sort tree to which root points.   Return false if not.
if ( root == NULL ) {
// Tree is empty, so it certainly doesn't contain item.
return false;
}
else if ( item == root->item ) {
// Yes, the item has been found in the root node.
return true;
}
else if ( item < root->item ) {
// If the item occurs, it must be in the left subtree.
return treeContains( root->left, item );
}
else {
// If the item occurs, it must be in the right subtree.
return treeContains( root->right, item );
}
}  // end treeContains()

void treeList(TreeNode *node) {
// Print the items in the tree in postorder, one item
// to a line.  Since the tree is a sort tree, the output
// will be in increasing order.
if ( node != NULL ) {
treeList(node->left);		   // Print items in left subtree.
cout << "  " << node->item << endl;  // Print item in the node.
treeList(node->right);		  // Print items in the right subtree.
}
} // end treeList()

int countNodes(TreeNode *node) {
// Count the nodes in the binary tree to which node
if ( node == NULL ) {
// Tree is empty, so it contains no nodes.
return 0;
}
else {
// Add up the root node and the nodes in its two subtrees.
int leftCount = countNodes( node->left );
int rightCount = countNodes( node->right );
return  1 + leftCount + rightCount;
}
} // end countNodes()

int main() {

TreeNode *root;  // Pointer to the root node in a binary tree.  This
// tree is used in this program as a binary sort tree.
// The tree is not allowed to contain duplicate
// items.  When the tree is empty, root is null.

cout << "This programs stores strings that you enter in a binary sort\n";
cout << "tree.  After each items is inserted, the contents of the tree\n";
cout << "are displayed.  The number of nodes in the tree is also output.\n";
cout << "	Any string you enter will be converted to lower case.\n";
cout << "Duplicate entries are ignored.\n";

while (true) {
// Get one string from the user, insert it into the tree,
// and print some information about the tree.  Exit if the
// user enters an empty string.  Note that all strings are
// converted to lower case.
cout << ("\n\nEnter a string to be inserted, or press return to end.\n");
cout << ("?  ");
string item;  // The user's input.
if (cin.peek() == '\n')
break;
cin >> item;
cin.ignore(10000,'\n');
if (treeContains(root,item)) {
// Don't insert a second copy of an item that is already
// in the tree.
cout << "\nThat item is already in the tree.\n";
}
else {
treeInsert(root,item);  // Add user's string to the tree.
cout << "\nThe tree contains " << countNodes(root) << " items.\n";
cout << "\nContents of tree:\n\n";
treeList(root);
}
}  // end while

cout << "\n\nExiting program.\n\n";

}  // end main()
```

#### Attached File(s)

Is This A Good Question/Topic? 0

## Replies To: how to apply Binary Sort Tree to my program

### #2 born2c0de

• printf("I'm a %XR",195936478);

Reputation: 175
• Posts: 4,667
• Joined: 26-November 04

## Re: how to apply Binary Sort Tree to my program

Posted 15 June 2007 - 01:54 AM

What problems are you experiencing when you run the program?

### #3 rameshg87

Reputation: 3
• Posts: 34
• Joined: 06-June 07

## Re: how to apply Binary Sort Tree to my program

Posted 15 June 2007 - 06:41 AM

Assuming that you enter a string of many words, you have to convert the string of those words into a binary sort tree and then display those items in the descending order.

This is my code .....
```
#include <iostream>
#include <string>

using namespace std;  //<string>

struct TreeNode {
// An object of type TreeNode represents one node
// in a binary tree of strings.

//  A variable in the main program of type pointer-to-TreeNode points to the binary sort tree that
//  is used by the program:
//  TreeNode *root;  // Pointer to the root node in the tree.

string item;	   // The data in this node.
TreeNode *left;	// Pointer to left subtree.
TreeNode *right;   // Pointer to right subtree.
TreeNode(string str = "") {
// Constructor, defined for convenience.
// Make a node containing the specified string.
item = str;
left = NULL;
right = NULL;
}
};  // end struct TreeNode

void treeInsert(TreeNode *&root, string newItem) {
// Add the item to the binary sort tree to which the parameter
// "root" refers.  Note that root is passed by reference since
// its value can change in the case where the tree is empty.
if ( root == NULL ) {
// The tree is empty.  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 ( newItem < root->item ) {
treeInsert( root->left, newItem );
}
else {
treeInsert( root->right, newItem );
}
}  // end treeInsert()

//A recursive function named treeContains is used to search for a given item in the tree.
//This routine implements the search algorithm for binary trees that was outlined above:
bool treeContains( TreeNode *root, string item ) {
// Return true if item is one of the items in the binary
// sort tree to which root points.   Return false if not.
if ( root == NULL ) {
// Tree is empty, so it certainly doesn't contain item.
return false;
}
else if ( item == root->item ) {
// Yes, the item has been found in the root node.
return true;
}
else if ( item < root->item ) {
// If the item occurs, it must be in the left subtree.
return treeContains( root->left, item );
}
else {
// If the item occurs, it must be in the right subtree.
return treeContains( root->right, item );
}
}  // end treeContains()

void treeList(TreeNode *node) //I changed the preorder to postorder
{
// Print the items in the tree in postorder, one item
// to a line.  Since the tree is a sort tree, the output
// will be in increasing order.
if ( node != NULL ) {
treeList(node->right);
cout << "  " << node->item << endl;  // Print item in the node.
// Print items in the right subtree.

treeList(node->left);

}
} // end treeList()

int countNodes(TreeNode *node) {
// Count the nodes in the binary tree to which node
if ( node == NULL ) {
// Tree is empty, so it contains no nodes.
return 0;
}
else {
// Add up the root node and the nodes in its two subtrees.
int leftCount = countNodes( node->left );
int rightCount = countNodes( node->right );
return  1 + leftCount + rightCount;
}
} // end countNodes()

int main() {

TreeNode *root;
root = NULL;

int i,j,length,wordcount;
char string[4000];
char words[100][40];

cout << "Enter the string : ";
gets (string);
cout <<"\n\n";

length = strlen (string);
for (i=0,j=0,wordcount=0;i<length;i++,j++)
{
words[wordcount][j] = string[i];
if (words[wordcount][j]==' ')
{
words[wordcount][j]='\0';
j=-1;
wordcount++;
}
}//This for loop converts the strings to seperate words

for (i=0;i<=wordcount;i++)
if (!treeContains(root,words[i]))
treeInsert(root,words[i]);

treeList(root);

cin.get();
}

```

This post has been edited by rameshg87: 15 June 2007 - 06:42 AM

### #4 yeungsam

Reputation: 0
• Posts: 2
• Joined: 14-June 07

## Re: how to apply Binary Sort Tree to my program

Posted 16 June 2007 - 08:33 AM

thanks rameshg87. would you please showing me how to make the program to read a text file contains 100 English sentence (read the file and create a 100-element array of strings) instead of keying in? and what about the symbol, just like > , . ? " & (space), i just wanna ignore it when read from file. and at last, when running the program, there were some funny characters had been shown, how to fix it?