Trees

This is a discussion on Trees within the C++ Programming forums, part of the General Programming Boards category; Hi people, How do I solve the following problem in C++ using trees ? I need to determin the frequency ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    10

    Trees

    Hi people,

    How do I solve the following problem in C++ using trees ?

    I need to determin the frequency and location of words in a document. After that list in alphabetical order the words and the reference to each line the word is used.

    for example,

    peter piper picked a peck of pickled peppers. a peck of pickled
    peppers peter piper picked. if peter piper picked a peck of pickeled peppers, where is the peck of that peter piper picked.

    it should display the folllowing information :

    .
    .
    .
    peppers 3:1, 2, 3
    peter 4:1, 2,3
    <word> <count>:<line number>

    i need to do this using trees date structure.


    pls assist.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,490
    I guess you would start with
    Code:
    class tree {
      private:
        tree *left; // sub-tree of words before this word
        tree *right; // sub-tree of words after this word
        int num_occurances; // how many times seen
        string word;  // the word in question
        vector <int> lines; // the lines it appears on
      public:
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    10
    thanks salem,

    but how to code the algorithm .... thats what i dunno.


    Quote Originally Posted by Salem
    I guess you would start with
    Code:
    class tree {
      private:
        tree *left; // sub-tree of words before this word
        tree *right; // sub-tree of words after this word
        int num_occurances; // how many times seen
        string word;  // the word in question
        vector <int> lines; // the lines it appears on
      public:
    }

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,490
    You have 4 cases
    node == NULL
    -> add a new node here, copy the word and line number, and set the num_occurances to 1

    node != NULL && word < node.word
    -> recurse down the left branch

    node != NULL && word > node.word
    -> recurse down the right branch

    node != NULL && word == node.word
    -> add the line number to the list, and increment the counter
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    10
    pardon mefor my ignorance....how do you get the line number?
    can you give me the actual coding?

    and after inserting every word how to i display it in alphabetical order?

    Quote Originally Posted by Salem
    You have 4 cases
    node == NULL
    -> add a new node here, copy the word and line number, and set the num_occurances to 1

    node != NULL && word < node.word
    -> recurse down the left branch

    node != NULL && word > node.word
    -> recurse down the right branch

    node != NULL && word == node.word
    -> add the line number to the list, and increment the counter

  6. #6
    Registered User WebSnozz's Avatar
    Join Date
    Oct 2001
    Posts
    102
    Try a search on google for "tree traversal" frequency "discrete math"

    One way you could use the strcture described and start at the root of the tree.
    I would add a function called
    addWord(const string & newword, int linenumber);

    In this function you would start at the root of the tree
    you need to check for 3 conditions, either
    if newword==treenode.word, then num_occurences+=1; lines.PushBack(linenumber); return;

    if newword<treenode.word, then traverse to the left node
    if newword>treenode.word, then traverse to the right node

    You would continue checking and traversing until you either find the word already in the tree OR
    If you get to a "leaf"(a leaf is a term used to describe a node in a tree that had no left or right subtrees, in other words the pointers left and right are null) and don't find the word in the tree, then that means you need to add a new node for that word. You would do a lessthan greaterthan check against the current node to see if you need to add the new node to the right or left.

    Once you have processed all the words in your file, then it shouldn't be a hard task to output all the data in your tree one node at a time.

    You need to read up on tree traversal.

    If you aren't familier with linked list, then it is important you understand that concept first and how to implement them. This will give you the skills you need to deal with pointers and nodes in a tree.

    Good luck!
    WebSnozz-
    Cats have no butt cheeks.
    If one farted, then it would make a flute noise.

  7. #7
    Registered User
    Join Date
    Mar 2004
    Posts
    10
    can someone show me the code for retrieving line number ... can show me the whole segment of codes on how to read in the text?

    and also to print out in alphabetical order

    Quote Originally Posted by WebSnozz
    Try a search on google for "tree traversal" frequency "discrete math"

    One way you could use the strcture described and start at the root of the tree.
    I would add a function called
    addWord(const string & newword, int linenumber);

    In this function you would start at the root of the tree
    you need to check for 3 conditions, either
    if newword==treenode.word, then num_occurences+=1; lines.PushBack(linenumber); return;

    if newword<treenode.word, then traverse to the left node
    if newword>treenode.word, then traverse to the right node

    You would continue checking and traversing until you either find the word already in the tree OR
    If you get to a "leaf"(a leaf is a term used to describe a node in a tree that had no left or right subtrees, in other words the pointers left and right are null) and don't find the word in the tree, then that means you need to add a new node for that word. You would do a lessthan greaterthan check against the current node to see if you need to add the new node to the right or left.

    Once you have processed all the words in your file, then it shouldn't be a hard task to output all the data in your tree one node at a time.

    You need to read up on tree traversal.

    If you aren't familier with linked list, then it is important you understand that concept first and how to implement them. This will give you the skills you need to deal with pointers and nodes in a tree.

    Good luck!

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,490
    > can someone show me the code for retrieving line number
    You count them as you read them
    Code:
    while ( file.getline(string) ) {
      linenum++;
      // now split string into words, and add each one
    }
    > and also to print out in alphabetical order
    The tree makes in in alphabetical order, that's what the left/right decisions you made previously ensure.
    It's just another recursive function based on
    - print left tree
    - print current node
    - print right tree
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trees
    By masterg in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2008, 12:42 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Huffman Trees
    By ChadJohnson in forum C Programming
    Replies: 1
    Last Post: 05-04-2004, 12:35 PM
  4. Binary Trees...
    By SirCrono6 in forum C++ Programming
    Replies: 5
    Last Post: 11-25-2003, 03:54 PM
  5. AVL Trees
    By kwigibo in forum C Programming
    Replies: 2
    Last Post: 04-17-2002, 05:46 PM

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