Thread: bintree and count (withouth using template)?

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    30

    bintree and count (not adding any template)?

    Hi all!
    sorry, title is using existing template.

    I wanna add words into a bintree with count with them. If the word is already existed it will increase 1.

    first my words class has 2 variable

    Code:
    class words
    {
       private:
       string s;
       int count;
       
       public:
       words() : s(""), count(1)
       {}
       
       words(const string st, int counting) : s(st), count(counting) 
       {}
       
       string getWord() const
       {
          return s;
       }
       
       int getCount()
       {
          return count;
       };
    then i define bintree to add words into bintree

    Code:
    bintree<words> word;
    words* dup = word.find(words(new_word)); // error here. How can i find only new_word matching without count
    string::const_iterator itr = letter.begin();
    while (itr != letter.end())
       {
          if (ispunct(*itr) || isspace(*itr) || *itr == '\n')
          {
             count++; // increasement for count
             if (!dup) // if not duplicate set count back to 1
             {
                count = 1;
                word.insert(words(new_word, count));
                new_word.clear();
             }
          }
          else
          {
             new_word += *itr;
          }
         itr++;
       }
       
       if (!dup)
       {
          count = 1;
          word.insert(words(new_word, count));
          new_word.clear();
       }
       else
          count++;
    first: how can i find() only new_word in bintree without count?
    second: how can i insert() count only into existing word?

    Thx and regard
    Last edited by cubimongoloid; 05-22-2009 at 05:39 PM.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    What is this bintree? Does it accept predicates?

    Such a thing should be rather straightforward with a std::map<string, int>.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    30
    This is avl bintree. I am not allowed to use map, because this app will be base on bintree. Many ppl also suggest me using map (much easier) but i cannot.

    Code:
    #ifndef BINTREE_H_
    #define BINTREE_H_
    
    #include <stdexcept>
    #include <math.h>
    
    #include "binnode.h"
    
    /********************************************************\
       template class for a binary tree
    \********************************************************/
    
    
    template <typename dataType> class bintree
    {
       private:
          binNode<dataType> *root;
          int numItems;
    
       public:
          /*******************************************************\
             constructors & destructors
          \*******************************************************/
    
          // constructor
          bintree() : root(NULL), numItems(0) {}
    
          // destructor
          ~bintree() {
             if (root != NULL) delete root;
          }
    
          /*******************************************************\
             misc functions
          \*******************************************************/
    
          bool empty() const {
             return (numItems == 0);
          }
    
          int size() const {
             return numItems;
          }
    
          int numNodes() const {
             if (root == NULL) {
                return 0;
             } else {
                return root->numNodes();
             }
          }
    
          int maxTreeDepth() const {
             if (root == NULL) {
                return 0;
             } else {
                return root->maxTreeDepth();
             }
          }
    
          int numLeafNodes() const {
             if (root == NULL) {
                return 0;
             } else {
                return root->numLeafNodes();
             }
          }
    
          double balance() const {
             // Returns a measure of how balanced a tree is.
             // A value of 1 is a prefectly balanced tree.
             // The closer to 0 the value is the more unbalanced
             // the tree.
             // A value < 0.5 indicates a tree that is seriously unbalanced
    
             // case of no nodes in tree
             if (numItems == 0) return 1.0;
    
             // calculate balance
             double log2numItems = log10(numItems + 1) / log10(2);
             return log2numItems / maxTreeDepth() * (numLeafNodes() * 2) / (numItems + 1);
          }
    
          void rebalance() {
             // Rebalance tree using the AVL algorithm
             // While this does not guarantee a perfectly balanced tree
             // it does make it mostly balanced by guranteeing that the diference
             // in depth between every right and left subtree is at most 1
    
             if (root != NULL) {
                while (root->rebalance(root));
             }
          }
    
          /*******************************************************\
             insertion and erasure functions
          \*******************************************************/
    
          void insert(const dataType& newData) {
             if (root == NULL) {
                root = new binNode<dataType>(newData);
             } else {
                root->insert(newData);
             }
             numItems++;
          }
    
          void erase(const dataType& delData) {
    
             if (root == NULL) {
                throw std::invalid_argument("data does not exist in tree to erase");
             }
    
             root->erase(&root, delData);
    
             numItems--;
          }
    
          dataType* find(const dataType &findData) const {
                 // this function looks for findData in ther tree.
                     // If it find the data it will return the address of the data in the tree
                     // otherwise it will return NULL
             if (root == NULL) return NULL;
             else return root->find(findData);
          }
    
          /*******************************************************\
             print function for assignment.
                     assumes dataType has print() function
          \*******************************************************/
    
              void print() const {
                 if (root != NULL) root->print();
          }
    };
    
    #endif

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I don't see, based on what you've written, why you can't use a map with this bintree. (You will have to specialize the insert function for the map so that it will increase the count instead of just not adding the thing.)

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Your class should overload operator== (and operator!=), so it can be used with the find method (uses only the string to compare for equality). Instead of a constructor that takes a string and a count, consider one that takes only a string and manages the count automatically (setting it to 0 or 1). It should also have a member function that allows you to increment the count. If find returns NULL, you'll insert the new word, else increment the word count.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    30
    in the increment function: if find() increase else return NULL, is that what u meant?

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    30
    in class words i defined string and int for count

    Code:
    class words
    {
       private:
       string s;
       int count;
       
       public:
       words() : s(""), count(1)
       {}
       
       words(const string st, int counting) : s(st), count(counting) 
       {}
       
       string getWord() const
       {
          return s;
       }
       
       int getCount()
       {
          return count++; // count will automatically increase when callled
       }
       
       bool operator == (const words &other) const 
       {
          return (s == other.s);
       }
       bool operator != (const words &other ) const
       {
          return (s > other.s);
       }
       bool operator < (const words &other ) const
       {
          return (s < other.s);
       }
    
       string toString() const
       {
          stringstream ss;
          ss << "   " << count << "  | " << s;
          return ss.str();
       }
    };
    but the result still 1, doesn't increase at all.

    Code:
    for(itr = token.begin();itr!=token.end();itr++)
       {
             w.getCount();
             new_word = *itr;
             if (!word.find(words(new_word, count)))
             {
                count = 1;
                word.insert(words(new_word, count));
                new_word.clear();
             }
             else
             {
                w.getCount(); // i don't know is it enough for increment
             }
       }
    the result only 1 for every word.
    Last edited by cubimongoloid; 05-24-2009 at 06:00 AM.

  8. #8
    Registered User
    Join Date
    May 2009
    Posts
    30
    ive checked cout for w.getCount() it increased, but print out only 1

    Code:
    string toString() const
       {
          stringstream ss;
          ss << "   " << count << "  | " << s;
          return ss.str();
       }

Popular pages Recent additions subscribe to a feed