Thread: Enter and write out words into a tree of nodes

  1. #1
    Registered User
    Join Date
    Nov 2016
    Posts
    84

    Enter and write out words into a tree of nodes

    Hi guys,

    I want to write a function for entering new words into a tree of Tnodes,a function to write out a tree of Tnodes, a function to write out a tree of Tnodes from left to right in alphabetical order. This is my code:

    Code:
    #include <iostream> 
    #include <string> 
    #include <string.h> 
     
    using namespace std; 
      
    struct Tnode 
    { 
         char* word; 
     int count; 
          Tnode* left; 
          Tnode* right; 
    }; 
     Tnode* addNode(Tnode* root, string word) 
     { 
           Tnode* node;
           if (!root) 
           { 
               node = new Tnode; 
               node->word = new char[64+1]; 
               strcpy(node->word, word.c_str()); 
               node->left = 0; 
               node->right = 0; 
               node->count = 1; 
               return (node); 
           } 
     
     
           int cmp = strcmp(word.c_str(), root->word);
     
           if (cmp < 0) 
      { 
               node = addNode(root->left, word); 
               if(!root->left) 
       {
        root->left = node;
       } 
           } 
           else if (cmp > 0) 
      { 
               node = addNode(root->right, word); 
               if(!root->right) 
       {
        root->right = node;
       } 
           } 
           else
      { 
               root->count++;
      } 
      
           return (node); 
     } 
     
     
     void printTree(Tnode* root, int indent) 
     { 
      if(!root) 
      {
       return;
      } 
     
           cout << string(indent, ' ') << root->word << "[" << root->count << "]" << endl;
     
           printTree(root->left, indent+4); 
           printTree(root->right, indent+4); 
     } 
     
     
     void aPrintTree(Tnode* root) 
     { 
          if(!root) 
      {
       return;
      } 
    
          aPrintTree(root->left); 
           cout << root->word << "[" << root->count << "]" << endl; 
           aPrintTree(root->right); 
     } 
     
     
     void printTree(Tnode* root) 
     { 
           printTree(root, 0); 
     } 
     
     
     void freeTree(Tnode* root) 
     { 
           if(!root) 
      {
       return;
      }
     
           freeTree(root->left); 
           freeTree(root->right);
     
           delete root->word; 
           delete root;
     } 
     
    };
     
    int main(int argc, char* argv[]) 
    { 
          Tnode* root = 0; 
     
     
          string word; 
     
     
          for(int i = 1; i < argc; i++) 
          { 
              word = string(argv[i]); 
              Tnode* node = addNode(root, word); 
              if (!root) 
      {
       root = node;
      } 
          } 
     
          cout << "Tree:" << endl;
     
          printTree(root);
     
          cout << "Alphabetical:" << endl;
     
          aPrintTree(root); 
      
          freeTree(root); 
    }
    1.) Is that correct or do someone has an idea how it can be improved?
    2.) I want to create a "wrapping" class Tnode. How I can do that?

    Thank you in advance.
    Last edited by Joe1903; 11-10-2016 at 08:55 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    My first suggestion would be better indentation.
    Indent style - Wikipedia

    > 1.) Is that correct or do someone has an idea how it can be improved?
    Is it?
    I mean, have you tested it and got satisfactory results?

    For me, replacing that char*word with a string would simplify the code no end, not to mention fix the bug when you attempt to delete the string memory.
    Presuming that strings have an upper fixed length is another no-no.

    Also, in main, all you need is this
    root = addNode(root, word);
    It saves the clumsiness you have at present, and still works as an idea in case you start balancing the tree later on (when the root can change more than once).



    > 2.) I want to create a "wrapping" class Tnode. How I can do that?
    Replace 'struct' with 'class' in your declaration of Tnode perhaps?
    Then add member functions.
    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.

  3. #3
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    DO I have a memory leak in my current version?Or do you I overrun memory?

    The 'struct' is given, I have to use it.Could you write a small example for class Tnode?

    I am not sure whether my adding is really go from "left to right".

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    The only potential memory leak I see is that you need to allocate enough storage for the given word by using word.size() and not just 64 (and adding 1).
    Code:
            node->word = new char[word.size()+1];
    And although it is not causing a memory leak, you're allowing your addNode routine to return garbage (uninitialized data) in the "else" case. That necessitates the extra tests. Instead you could always return proper data and use it like this:
    Code:
    // Normally in C++ this would be a constructor.
    Tnode* newNode(string word) {
        Tnode* node = new Tnode;
        node->word = new char[word.size()+1];
        strcpy(node->word, word.c_str());
        node->left = node->right = nullptr;
        node->count = 1;
        return node;
    }
    
    Tnode* addNode(Tnode* root, string word) { 
        if (!root) return newNode(word);
    
        int cmp = strcmp(word.c_str(), root->word);
        if (cmp < 0)
            root->left = addNode(root->left, word); 
        else if (cmp > 0) 
            root->right = addNode(root->right, word); 
        else
            root->count++;
    
        return root;
    }
    And in main:
    Code:
            root = addNode(root, word);

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    > DO I have a memory leak in my current version?Or do you I overrun memory?
    Well your
    delete root->word;
    should be
    delete [ ] root->word;

    And if you input a sufficiently long word, then you'll have an overrun as well.
    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.

  6. #6
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    > DO I have a memory leak in my current version?Or do you I overrun memory?
    Well your
    delete root->word;
    should be
    delete [ ] root->word;

    And if you input a sufficiently long word, then you'll have an overrun as well.
    Do you see any logical errors in my Code?Is it adding new words from left to right?I am not sure.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    I suppose the real test is whether aPrintTree() does what you want.

    > Do you see any logical errors in my Code?
    Not on first glance.

    > Is it adding new words from left to right?
    Is it?
    I dunno, you wrote it and presumably tested it - what are your results?

    I mean, if you had a specific test case which fails, then I might actually get around to testing your code in a debugger. But at the moment, it looks like you're just trying to outsource some of your homework.

    > I am not sure.
    Being able to test your own code just as important as being able to write it in the first place.
    Might I suggest the following series of tests
    - no words
    - one word
    - two words, in order
    - two words, out of order
    - several random sentences.

    Either using debug "print" statements, a debugger or a profiler, make sure every line of code gets executed at least once.
    It might still have bugs in it, but at least you'll be able to make some definitive statements about the limitations (or otherwise).
    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.

  8. #8
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    I suppose the real test is whether aPrintTree() does what you want.

    > Do you see any logical errors in my Code?
    Not on first glance.

    > Is it adding new words from left to right?
    Is it?
    I dunno, you wrote it and presumably tested it - what are your results?

    I mean, if you had a specific test case which fails, then I might actually get around to testing your code in a debugger. But at the moment, it looks like you're just trying to outsource some of your homework.

    > I am not sure.
    Being able to test your own code just as important as being able to write it in the first place.
    Might I suggest the following series of tests
    - no words
    - one word
    - two words, in order
    - two words, out of order
    - several random sentences.

    Either using debug "print" statements, a debugger or a profiler, make sure every line of code gets executed at least once.
    It might still have bugs in it, but at least you'll be able to make some definitive statements about the limitations (or otherwise).
    I have tested it,it works fine.Thanks for your suggestion.
    One last thing: I can't get this wrapping class Tnode.Could you show me that please?Just with one data member,e.g. addnode.

  9. #9
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    I suppose the real test is whether aPrintTree() does what you want.

    > Do you see any logical errors in my Code?
    Not on first glance.

    > Is it adding new words from left to right?
    Is it?
    I dunno, you wrote it and presumably tested it - what are your results?

    I mean, if you had a specific test case which fails, then I might actually get around to testing your code in a debugger. But at the moment, it looks like you're just trying to outsource some of your homework.

    > I am not sure.
    Being able to test your own code just as important as being able to write it in the first place.
    Might I suggest the following series of tests
    - no words
    - one word
    - two words, in order
    - two words, out of order
    - several random sentences.

    Either using debug "print" statements, a debugger or a profiler, make sure every line of code gets executed at least once.
    It might still have bugs in it, but at least you'll be able to make some definitive statements about the limitations (or otherwise).
    This is my output:

    ==> free hello c++ foo faz
    Tree:
    free[1]
    (Tab)c++[1]
    (Tab Tab)foo[1]
    (Tab Tab Tab)faz[1]
    (Tab)hello[1]
    Alphabetical:
    c++[1]
    faz[1]
    foo[1]
    free[1]
    hello[1]

    I don`t know,it looks strange. The tabs are because of indent+4. Do someone see the reason why it looks like this? I wanted to add from left to right.
    Last edited by Joe1903; 11-14-2016 at 03:24 AM.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    The first word in the input will always be the root node, regardless of where it is in the sorted order.

    Try this, to show you where all the left/right decisions are being made.
    Code:
           cout << "<" ; aPrintTree(root->left); 
           cout << "=" << root->word << "[" << root->count << "]" << endl; 
           cout << ">" ; aPrintTree(root->right);
    Experiment with a list of words which are already sorted (or reverse sorted). The result should basically be a linked list.
    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.

  11. #11
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    The first word in the input will always be the root node, regardless of where it is in the sorted order.

    Try this, to show you where all the left/right decisions are being made.
    Code:
           cout << "<" ; aPrintTree(root->left); 
           cout << "=" << root->word << "[" << root->count << "]" << endl; 
           cout << ">" ; aPrintTree(root->right);
    Experiment with a list of words which are already sorted (or reverse sorted). The result should basically be a linked list.
    I have done, and yes the result is a linked list (for already sorted words).But I am not sure about this left to right thing.
    One question: Do you think the code is doing that what it should do?

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    Let me show you something.

    gcov shows you which lines of code were executed (##### lines were never touched - why was this?), and how many times.

    Questions you need to ask yourself are
    - are the numbers in line with expectations of how you understand the code is supposed to work.
    - lines with hashes are untested lines; can you think of test cases to exercise them? If you can't, then ask why you have that code in the first place.


    Code:
    $ g++ -fprofile-arcs -ftest-coverage main.cpp
    $ ./a.out free hello c++ foo faz
    Tree:
    free[1]
        c++[1]
            foo[1]
                faz[1]
        hello[1]
    Alphabetical:
    c++[1]
    faz[1]
    foo[1]
    free[1]
    hello[1]
    $ gcov main.cpp
    File 'main.cpp'
    Lines executed:98.04% of 51
    Creating 'main.cpp.gcov'
    
    $ cat main.cpp.gcov
            -:    0:Source:main.cpp
            -:    0:Graph:main.gcno
            -:    0:Data:main.gcda
            -:    0:Runs:1
            -:    0:Programs:1
            -:    1:#include <iostream>
            -:    2:#include <string>
            -:    3:#include <string.h>
            -:    4:
            -:    5:using namespace std;
            -:    6:
            -:    7:struct Tnode {
            -:    8:  char *word;
            -:    9:  int count;
            -:   10:  Tnode *left;
            -:   11:  Tnode *right;
            -:   12:};
            -:   13:
           12:   14:Tnode *addNode(Tnode * root, string word)
            -:   15:{
            -:   16:  Tnode *node;
           12:   17:  if (!root) {
            5:   18:    node = new Tnode;
            5:   19:    node->word = new char[64 + 1];
            5:   20:    strcpy(node->word, word.c_str());
            5:   21:    node->left = 0;
            5:   22:    node->right = 0;
            5:   23:    node->count = 1;
            5:   24:    return (node);
            -:   25:  }
            -:   26:
            7:   27:  int cmp = strcmp(word.c_str(), root->word);
            -:   28:
            7:   29:  if (cmp < 0) {
            4:   30:    root->left = addNode(root->left, word);
            3:   31:  } else if (cmp > 0) {
            3:   32:    root->right = addNode(root->right, word);
            -:   33:  } else {
        #####:   34:    root->count++;
            -:   35:  }
            -:   36:
            7:   37:  return (root);
            -:   38:}
            -:   39:
            -:   40:
           11:   41:void printTree(Tnode * root, int indent)
            -:   42:{
           11:   43:  if (!root) {
            6:   44:    return;
            -:   45:  }
            -:   46:
           10:   47:  cout << string(indent, ' ') << root->word
           10:   48:      << "[" << root->count << "]" << endl;
            5:   49:  printTree(root->left, indent + 4);
            5:   50:  printTree(root->right, indent + 4);
            -:   51:}
            -:   52:
            -:   53:
           11:   54:void aPrintTree(Tnode * root)
            -:   55:{
           11:   56:  if (!root) {
            6:   57:    return;
            -:   58:  }
            -:   59:
            5:   60:  aPrintTree(root->left);
            5:   61:  cout << root->word << "[" << root->count << "]" << endl;
            5:   62:  aPrintTree(root->right);
            -:   63:}
            -:   64:
            -:   65:
            1:   66:void printTree(Tnode * root)
            -:   67:{
            1:   68:  printTree(root, 0);
            1:   69:}
            -:   70:
            -:   71:
           11:   72:void freeTree(Tnode * root)
            -:   73:{
           11:   74:  if (!root) {
            6:   75:    return;
            -:   76:  }
            -:   77:
            5:   78:  freeTree(root->left);
            5:   79:  freeTree(root->right);
            -:   80:
            5:   81:  delete[]root->word;
            5:   82:  delete root;
            -:   83:}
            -:   84:
            1:   85:int main(int argc, char *argv[])
            -:   86:{
            1:   87:  Tnode *root = 0;
            -:   88:
            2:   89:  string word;
            -:   90:
            6:   91:  for (int i = 1; i < argc; i++) {
            5:   92:    word = string(argv[i]);
            5:   93:    root = addNode(root, word);
            -:   94:  }
            -:   95:
            1:   96:  cout << "Tree:" << endl;
            1:   97:  printTree(root);
            -:   98:
            1:   99:  cout << "Alphabetical:" << endl;
            1:  100:  aPrintTree(root);
            -:  101:
            1:  102:  freeTree(root);
            4:  103:}
    > One question: Do you think the code is doing that what it should do?
    I'm not going to answer it, because it's something you need to be able to figure out for yourself.

    What is all the evidence you have telling you?
    - does it compile?
    - does it run?
    - does it produce expected output?
    - how many tests have you done?
    - how much of the code passes test coverage?
    What do you think?
    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.

  13. #13
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    Let me show you something.

    gcov shows you which lines of code were executed (##### lines were never touched - why was this?), and how many times.

    Questions you need to ask yourself are
    - are the numbers in line with expectations of how you understand the code is supposed to work.
    - lines with hashes are untested lines; can you think of test cases to exercise them? If you can't, then ask why you have that code in the first place.


    Code:
    $ g++ -fprofile-arcs -ftest-coverage main.cpp
    $ ./a.out free hello c++ foo faz
    Tree:
    free[1]
        c++[1]
            foo[1]
                faz[1]
        hello[1]
    Alphabetical:
    c++[1]
    faz[1]
    foo[1]
    free[1]
    hello[1]
    $ gcov main.cpp
    File 'main.cpp'
    Lines executed:98.04% of 51
    Creating 'main.cpp.gcov'
    
    $ cat main.cpp.gcov
            -:    0:Source:main.cpp
            -:    0:Graph:main.gcno
            -:    0:Data:main.gcda
            -:    0:Runs:1
            -:    0:Programs:1
            -:    1:#include <iostream>
            -:    2:#include <string>
            -:    3:#include <string.h>
            -:    4:
            -:    5:using namespace std;
            -:    6:
            -:    7:struct Tnode {
            -:    8:  char *word;
            -:    9:  int count;
            -:   10:  Tnode *left;
            -:   11:  Tnode *right;
            -:   12:};
            -:   13:
           12:   14:Tnode *addNode(Tnode * root, string word)
            -:   15:{
            -:   16:  Tnode *node;
           12:   17:  if (!root) {
            5:   18:    node = new Tnode;
            5:   19:    node->word = new char[64 + 1];
            5:   20:    strcpy(node->word, word.c_str());
            5:   21:    node->left = 0;
            5:   22:    node->right = 0;
            5:   23:    node->count = 1;
            5:   24:    return (node);
            -:   25:  }
            -:   26:
            7:   27:  int cmp = strcmp(word.c_str(), root->word);
            -:   28:
            7:   29:  if (cmp < 0) {
            4:   30:    root->left = addNode(root->left, word);
            3:   31:  } else if (cmp > 0) {
            3:   32:    root->right = addNode(root->right, word);
            -:   33:  } else {
        #####:   34:    root->count++;
            -:   35:  }
            -:   36:
            7:   37:  return (root);
            -:   38:}
            -:   39:
            -:   40:
           11:   41:void printTree(Tnode * root, int indent)
            -:   42:{
           11:   43:  if (!root) {
            6:   44:    return;
            -:   45:  }
            -:   46:
           10:   47:  cout << string(indent, ' ') << root->word
           10:   48:      << "[" << root->count << "]" << endl;
            5:   49:  printTree(root->left, indent + 4);
            5:   50:  printTree(root->right, indent + 4);
            -:   51:}
            -:   52:
            -:   53:
           11:   54:void aPrintTree(Tnode * root)
            -:   55:{
           11:   56:  if (!root) {
            6:   57:    return;
            -:   58:  }
            -:   59:
            5:   60:  aPrintTree(root->left);
            5:   61:  cout << root->word << "[" << root->count << "]" << endl;
            5:   62:  aPrintTree(root->right);
            -:   63:}
            -:   64:
            -:   65:
            1:   66:void printTree(Tnode * root)
            -:   67:{
            1:   68:  printTree(root, 0);
            1:   69:}
            -:   70:
            -:   71:
           11:   72:void freeTree(Tnode * root)
            -:   73:{
           11:   74:  if (!root) {
            6:   75:    return;
            -:   76:  }
            -:   77:
            5:   78:  freeTree(root->left);
            5:   79:  freeTree(root->right);
            -:   80:
            5:   81:  delete[]root->word;
            5:   82:  delete root;
            -:   83:}
            -:   84:
            1:   85:int main(int argc, char *argv[])
            -:   86:{
            1:   87:  Tnode *root = 0;
            -:   88:
            2:   89:  string word;
            -:   90:
            6:   91:  for (int i = 1; i < argc; i++) {
            5:   92:    word = string(argv[i]);
            5:   93:    root = addNode(root, word);
            -:   94:  }
            -:   95:
            1:   96:  cout << "Tree:" << endl;
            1:   97:  printTree(root);
            -:   98:
            1:   99:  cout << "Alphabetical:" << endl;
            1:  100:  aPrintTree(root);
            -:  101:
            1:  102:  freeTree(root);
            4:  103:}
    > One question: Do you think the code is doing that what it should do?
    I'm not going to answer it, because it's something you need to be able to figure out for yourself.

    What is all the evidence you have telling you?
    - does it compile?
    - does it run?
    - does it produce expected output?
    - how many tests have you done?
    - how much of the code passes test coverage?
    What do you think?
    First of all: This is not a homework, it is something for my job.But not for the job itself. I am working with Cobol normally.
    The code is compiling and running fine.I have done the test cases you told me before.Everything is fine.I am just confused with the ordering.I wanted to sort the words from left to right in alphabetical order.As I am very new in C++,I need some help.
    Could you just tell me whether it is doing the sort from left to right alphabetically correctly? Just no or yes.Not more info.I will going to search for improvement then.The code is produced with my understanding of C++,but not sure whether it is correct.

  14. #14
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    One last question:

    In this snippet

    Code:
    struct Tnode 
    { 
         char* word; 
     int count; 
          Tnode* left; 
          Tnode* right; 
    }; 
     Tnode* addNode(Tnode* root, string word) 
     { 
           Tnode* node;
           if (!root) 
           { 
               node = new Tnode; 
               node->word = new char[64+1]; 
               strcpy(node->word, word.c_str()); 
               node->left = 0; 
               node->right = 0; 
               node->count = 1; 
               return (node); 
           }
    What would be the difference between char word[64 + 1] (in struct Tnode) and node->word = new char[64+1];

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,677
    Alphabetical:
    c++[1]
    faz[1]
    foo[1]
    free[1]
    hello[1]
    Yes, this looks like it's sorted to me, at least according to the dictionary that I have.

    > What would be the difference between char word[64 + 1] (in struct Tnode) and node->word = new char[64+1];
    You don't need to call delete[] node->word; later on.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. actions on tree with 4 nodes
    By Dave11 in forum C Programming
    Replies: 2
    Last Post: 05-09-2014, 12:07 PM
  2. Write/Read tree nodes into a binary file
    By frank1 in forum C Programming
    Replies: 2
    Last Post: 10-21-2013, 12:37 AM
  3. Issue with tree nodes
    By coffee_cups in forum C++ Programming
    Replies: 19
    Last Post: 06-14-2013, 08:16 PM
  4. total nodes in a tree
    By BEN10 in forum C Programming
    Replies: 5
    Last Post: 01-10-2010, 11:37 AM
  5. Binary Tree - sum of nodes
    By Tiffanie in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2008, 08:49 AM

Tags for this Thread