Expert: Joseph Moore - 5/27/2009

Question
Hi,

How are you? Thank you very much for taking questions.
I am experimenting with linked lists and trees in C++. I think I know how to declare nodes for trees and also how to connect them with pointers. However, I only know how to do it one node at a time. My program needs to automatically make unknown number new nodes during runtime. How do you make automatic nodes without having to give each node an individual name. Is an array of nodes the way to go? Or is there another automatic naming pattern that I’m unaware of.

 Below is my code:

class MyTree
{
   int *id, *count;
   MyTree *left, *right;

 public:   
     
    MyTree(int a, int b)
      {
      id = new int; count = new int;   *id = a; *count = b;
      left = NULL;
      right = NULL;
      }
      
   ~MyTree(){delete id; delete count;}
   };

int main()
{

MyTree first_node(1,1);
MyTree second_node(2,1);
.
.
MyTree onehundredth_node(100,1);
}


How could I create code that doesn’t need to know the names and numbers of the nodes beforehand.

My second question concerns FP-trees. Do you know of any implementation tutorials for FP-trees?

Sincerely,
                  Andres


Answer
Hi, Andres.  Hopefully I can answer your questions here.

Traditionally, linked lists and other similar data structures use dynamically allocated nodes.  By dynamically allocating the nodes, you can have a (theoretically) infinite number of nodes.  I would also suggest that you separate out the concept of the container and the node.

In your example tree code, you have a single class which represents both the container and the node.  While there isn't really anything wrong with this, keeping the two concepts separate allows you to define a nice interface class which you can use to interact with the list or tree.  For example, using your tree, I would recommend something like the following:

   struct myTreeNode
   {
       int id;
       int count;

       myTreeNode* left;
       myTreeNode* right;
   };

   class myTree
   {
       myTreeNode* rootNode;

   public:
       myTree() { rootNode = NULL; }
       ~myTree() { // do proper cleanup here }

       addNode(int a, int b)
       {
           myTreeNode* newNode = new myTreeNode;
           newNode->left = newNode->right = NULL;
           newNode->id = a;
           newNode->count = b;

           if (rootNode)
           {
               // do whatever insert logic you need here
           }
           else
           {
               rootNode = newNode;
           }
       }
   }

Then whenever you need to add a node to the tree, you simply call the addNode function on the instance of the class.  In this way, you can call add node anywhere within your code with the appropriate data and it will create and add the node for you.

In looking for some aids for FP trees, I found the following lecture slides dealing with FP trees:

http://www.cis.hut.fi/Opinnot/T-61.6020/2008/fptree.pdf

They obviously would be better if there were audio of the lecturer going over the slides, but they do convey the information fairly well.  Additionally, an academic paper dealing with FP trees may be found here:

http://www.cs.uiuc.edu/homes/hanj/pdf/dami04_fptree.pdf

Hopefully those deal enough with FP trees to help you out.  Please let me know if you have any further questions.