Binary Search Tree...

This is a discussion on Binary Search Tree... within the C++ Programming forums, part of the General Programming Boards category; Really appreciate it if anyone can helo me out on a C++ problem on tree sorting. Problem: Write a sorting ...

  1. #1
    D'oh
    Guest

    Unhappy Binary Search Tree...

    Really appreciate it if anyone can helo me out on a C++ problem on tree sorting.
    Problem:
    Write a sorting algorithm that sorts the individual words in a given article. Using tree sort, list only words of length four or greater, and list a word only once with a notation for the number of times it appears. For example :

    alpha
    beta(3)
    gamma(4)
    delta
    ...



    I am using a binary tree and using an inorder search to print out the words

    my question is :

    1. after loading the file, should I read the words line by line using getline, check it character by character and copy it into a string? Is there a better way?

    2. is there any defined function that is able to check whether a character is an alphabet or not? coz' I only want to print out alphabets and not any of the punctuations. The way I did it is that if thre is a non-alphabet word after the last alphabet, then the word ends there.

    3. say for example the word "don't", the puctuation will mess things up. How do I do it so that it will still print out the word "don't"

    Thanks a lot. I a complete newbie, hope I can get as much advice from more experienced coders.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    I'm going to make a few assumptions, if I'm wrong let me know. I'll assume that the file is in a normal typing format, such as this post where there are many words for each line. I'll assume that you are going to increment a counter for a certain leaf of the tree when you encounter the same word as binary trees cannot have two nodes of the same item.

    With all of that in mind, use an instance of the string class as your buffer to read from the file, don't use getline but instead just use cin as when reading a string it will stop at the first space character it sees. Iterate through the buffer to first determine if the word contains more than 3 characters while ignoring anything but alphabetic characters. Use a counter there, something like:
    Code:
    int cnt = 0;
    for( int i = 0; !isspace(buffer[i]); ++i )
      if( isalpha(buffer[i]) ) cnt++;
    cnt is declared outside of the loop because you will use it later when adding the word to the list, if cnt is greater than 3 then you add it, otherwise you discard and start over with the next word.

    -Prelude
    My best code is written with the delete key.

  3. #3
    D'oh
    Guest

    more questions

    I'm sorry if I am asking too much questions... I really suck at programming.

    Yes, you are right, I am reading from a normal typing format and will increment a counter for a certain leaf if the same word repeats it self.

    isalplha() is very usefull, thanks

    for the buffer, does it get strings or characters? Do you mind elaborating more on the getting the words from the text..

    if I do it using cin, how does it know when to go from one word to another?

    Thanks a lot ...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21