Thread: binary search trees and text

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    83

    binary search trees and text

    hi,

    i have to create a program that takes a line of text and puts it in a binary search tree.

    from my understanding, a bst is balanced where the root node is an item and if the next item is less than the root, then it gets pointed to by the root's left pointer. and if it's greater than the root, then it gets pointed to by the root's right pointer. and throw in some recurssion and you have yourself a balanced bst.

    my main problem is comprehending the part about the line of text and the bst. so far i've only dealt with numbers. how can i do this using words? given a line of text, i can separate it using getline and other methods to manipulate strings.

    thanks,
    barneygumble742

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    Hi,

    <string>'s can be compared just like numbers:
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
      
    int main()
    { 
    	string str1 = "akkkkk";
    	string str2 = "zkkkkk";
    
    	string str3 = "mmmmmma";
    	string str4 = "mmmmmmz";
    
    	cout<<( (str1 < str2)? str1:str2)<<endl;
    	cout<<( (str3 < str4)? str3:str4)<<endl;
    
    	return 0;
    }
    The comparison operator < looks at the first character of both strings and compares their integer ascii codes. Characters are stored internally as their ascii codes, so you should take a brief look at an ascii table to see how the character codes are ordered. The comparison operator< returns true or false depending on the ascii codes of the first chars in the string. If the first chars are the same, then the 2nd chars in each string are examined.

    In the example code, with the first pair of strings the comparison< operator results in true after examining only the first char of each string. With the second pair, the comparison progresses along each string until the chars differ.

    While you think of a string as a collection of characters, a computer views a string as a collection of integers. Computers can only store numbers, so anything stored inside a computer has to be converted to a number.
    Last edited by 7stud; 11-23-2005 at 12:41 AM.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by barneygumble742
    hi,
    from my understanding, a bst is balanced where the root node is an item and if the next item is less than the root, then it gets pointed to by the root's left pointer. and if it's greater than the root, then it gets pointed to by the root's right pointer. and throw in some recurssion and you have yourself a balanced bst.
    That has nothing to do with whether or not the tree is balanced, it is simply a matter of how the data structure is ordered, lesser items take one path (left for example) and greater items take the other path.

    Definition of a balanced binary tree (coutesy of NIST.GOV ):

    A binary tree where no leaf is more than a certain amount farther from the root than any other. After inserting or deleting a node, the tree may rebalanced with "rotations."
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    If you can do this with numbers then you shouldn't have any problem doing this with words.

    Let's say you were given a bunch of words in this particular order:-

    Code:
    John  Joe  Alice Susan
    And you were asked to insert them into a binary tree. Using the rules already established for binary trees.

    First of all lets convert the names into numbers. Using Alphabetical order as a guideline.

    So:-

    Code:
    John = 3
    Joe = 2
    Alice = 1
    Susan = 4
    If we were to enter these numbers (in this particular order), the binary tree would look like this:-

    Insert 3:
    Code:
      
    3
    Insert 2:
    Code:
        
            3
           /
         2
    Insert 1:
    Code:
         
              3
             /
            2
           /
          1
    Insert 4:
    Code:
     
             3
            / \
           2  4
          /
         1
    You should be comfortable with this.

    Inserting names or words would be exactly the same.

    Because you can use 'strings' it makes life a lot easier than using char arrays.
    You can compare strings just like you would compare numbers. See 7Stud's explanation

    Therefore the Tree would look like this:-
    Code:
           John
            / \
          Joe  Susan
          /
        Alice
    See here for more details...

    http://math.hws.edu/eck/cs225/s03/binary_trees/

    This may also be useful
    http://www.cs.usask.ca/resources/tut...ree_index.html

    Reading in a line would be no different. You would just split the line into words using the whitespace as a delimiter. So long as your structure for defining a BST is up to scratch you should have no problems.
    Last edited by treenef; 11-23-2005 at 07:09 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Newbie binary tree confusion
    By Sharke in forum C Programming
    Replies: 2
    Last Post: 04-08-2009, 06:59 AM
  2. Binary Trees
    By wvu2005 in forum C Programming
    Replies: 7
    Last Post: 10-15-2005, 04:59 PM
  3. Binary Search Trees
    By chaos in forum C Programming
    Replies: 1
    Last Post: 06-14-2005, 05:42 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Newbie questions regarding binary search trees
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 07:48 AM