• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 350
  • Last Modified:

Tree traversal/pointers

This program enters outline items into a first child next sibling tree, and then prints the resulting tree. The printTree() function logic seems to be correct, becasue the first 2 nodes print out correctly, but I seem to be losing the pointer references after this point. On the third recursive call, myRoot->nextSibling shouldn't be null, but it is. I know something is screwey with my pointer assignments, but I have been over and over it, and I can't figure it out.

Here's my code:

#include "OutlineItem.h"
#include <iostream>

static int padWidth = 0;

int main()
{
      MultiTree myTree;
      
      void printTree(OutlineItemNode theRoot);

      OutlineItemNode node1("Music", 0);
      OutlineItemNode node2("Rock", 1);
      OutlineItemNode node3("Pop", 2);

      myTree.addRoot(node1);      
      myTree.addFirstChild(node1, node2);
      myTree.addNextSibling(node2, node3);

      printTree(node1);
}

void printTree(OutlineItemNode theRoot)
{
      OutlineItemNode* rootPtr = new OutlineItemNode(theRoot.item.text, theRoot.item.id);

      rootPtr->firstChild = theRoot.firstChild;
      rootPtr->nextSibling = theRoot.nextSibling;
      rootPtr->parent = theRoot.parent;

      if(rootPtr)
      {
            cout << getPadding(padWidth) << *rootPtr << endl;

            if(rootPtr->firstChild)
            {
                  padWidth += 5;
                  printTree(*rootPtr->firstChild);
            }

            if(rootPtr->nextSibling)
            {
                  printTree(*rootPtr->nextSibling);
            }

            if(rootPtr->parent)
            {
                  padWidth -= 5;
                  printTree(*rootPtr->parent);
            }
      }
}



And here is "OutlineItem.h" (sorry it's ugly!)



#include <string>
#include <iostream>

using namespace std;

class OutlineItem
{
      public:

      string text;
      int id;

      OutlineItem()
      {
        //setOutlineItem("", 0);
            text = "";
            id = 0;
      };

      OutlineItem(string theText, int theId)
      {
            text = theText;
            id = theId;
            //setOutlineItem(theText, theId);
      };

      string getText()
      {
            return text;
      };

      int getId()
      {
            return id;
      };

};//End class OutlineItem

class OutlineItemNode
{
      public:

      OutlineItemNode* firstChild;
      OutlineItemNode* nextSibling;
      OutlineItemNode* parent;
      OutlineItem item;

      friend ostream& operator << (ostream& lhs, const OutlineItemNode &rhs);
      friend bool operator == (OutlineItemNode& lhs, OutlineItemNode& rhs);

      OutlineItemNode(string theText, int theId)
      {
            item.text = theText;
            item.id = theId;
            //item.setOutlineItem(theText, theId);
            firstChild = nextSibling = parent = NULL;                  
      };

};//End class OutlineItemNode

ostream& operator << (ostream& lhs, OutlineItemNode& rhs)
{
      lhs << "(" << rhs.item.getId() << ") " << rhs.item.getText();      
      return(lhs);
}

bool operator == (OutlineItemNode& lhs, OutlineItemNode& rhs)
{
      return(lhs.item.getId() == rhs.item.getId());
}

class MultiTree
{
      public:

      OutlineItemNode* root;
      OutlineItemNode* current;
      OutlineItemNode* last;

      friend ostream& operator << (ostream& lhs, const MultiTree& rhs);

      MultiTree()
      {
            root = current = last = NULL;
      };

      bool isEmpty()
      {
            return(root == NULL);
      };

      bool isRoot(OutlineItemNode currentNode)
      {
            return(      currentNode == *root);      
      };

      void addRoot(OutlineItemNode& newRoot)
      {
            if(isEmpty())
            {
                  OutlineItemNode* newNodePtr;
                  newNodePtr = new OutlineItemNode(newRoot.item.getText(), newRoot.item.getId());
                  root = current = last = newNodePtr;
            }
      };

      void addFirstChild(OutlineItemNode& currentNode, OutlineItemNode& newNode)
      {            
            OutlineItemNode* newNodePtr;
            OutlineItemNode* currentPtr;
            newNodePtr = new OutlineItemNode(newNode.item.getText(), newNode.item.getId());
            currentPtr = new OutlineItemNode(currentNode.item.getText(), currentNode.item.getId());

            currentPtr->firstChild = currentNode.firstChild;
            currentPtr->nextSibling = currentNode.nextSibling;
            currentPtr->parent = currentNode.parent;
            
            if(isEmpty())
            {
                  cout << "The tree is empty, try to add this item as the root." << endl << endl;
            }

            else
            {
                  if(currentNode.firstChild==NULL)
                  {
                        newNode.parent = currentPtr;
                        currentNode.firstChild = newNodePtr;
                        last = newNodePtr;
                  }

                  else
                  {                        
                        newNode.parent = currentPtr;
                        newNodePtr->nextSibling = currentNode.firstChild;
                        currentNode.firstChild = newNodePtr;
                        last = newNodePtr;                        
                  }
           }

      };//End addFirstChild

      void addNextSibling(OutlineItemNode& currentNode, OutlineItemNode& newNode)
      {
            
            OutlineItemNode* newNodePtr;
            OutlineItemNode* currentPtr;
            newNodePtr = new OutlineItemNode(newNode.item.getText(), newNode.item.getId());
            currentPtr = new OutlineItemNode(currentNode.item.getText(), currentNode.item.getId());
            
            if(isEmpty())
            {
                  cout << "The tree is empty, try to add this item as the root." << endl << endl;
            }

            else
            {
                  if(currentNode.nextSibling==NULL)
                  {
                        currentNode.nextSibling = newNodePtr;
                        last = newNodePtr;
                        newNode.parent = currentNode.parent;                        
                  }

                  else
                  {      
                        newNodePtr->nextSibling = currentNode.nextSibling;
                        currentNode.nextSibling = newNodePtr;
                        last = newNodePtr;
                        newNode.parent = currentNode.parent;                        
                  }
           }

      };//End addFirstChild

};//End class MultiTree

string getPadding(int width)
{
      string str = "";
      for(int i =0; i<=width; i++)
            str+=" ";
      return(str);
}

ostream& operator << (ostream& lhs, const MultiTree& rhs)
{
      //How can I make this recursive in order to traverse the tree?
      return(lhs);
}













0
Heather_B
Asked:
Heather_B
  • 6
  • 2
1 Solution
 
jkrCommented:
The problem is how you are willing the tree - that should IMHO be

     myTree.addRoot(node1);    
     myTree.addFirstChild(node1, node2);
     myTree.addNextSibling(node1, node3);

resulting in

 (0) Music
firstChild
      (1) Rock
nextSibling
      (2) Pop


0
 
Heather_BAuthor Commented:
Maybe I'm not catching your meaning, but it seems that

myTree.addNextSibling(node1, node3);

would add node3 as the next sibling of the root (node1).

I want node1 to be the root, node2 & node3 to be one level beneath the root.

When I include this code in main() for testing purposes:

      cout << "Root:" << *myTree.root << endl;   //root=node1
      cout << "First child of root:" << *node1.firstChild << endl; //first child of root
      cout << "Next sibling of " << *node1.firstChild << ":" << *node2.nextSibling;

I get the desired result, so I son't think that's the problem.
However, if I try myTree.root->firstChild instead of node1.firstChild, I get a Null Pointer exception.

That's more my problem I think.

0
 
jkrCommented:
Try it - I did, it works like that, the output I posted is coped from my console window ;o)

Oh, BTW, it is a little more efficiant to use

void printTree(OutlineItemNode theRoot)
{

    OutlineItemNode* rootPtr = &theRoot;

     if(rootPtr)
     {
          cout << getPadding(padWidth) << *rootPtr << endl;

          if(rootPtr->firstChild)
          {
cout << "firstChild" << endl;
               padWidth += 5;
               printTree(*rootPtr->firstChild);
          }

          if(rootPtr->nextSibling)
          {
cout << "nextSibling" << endl;
               printTree(*rootPtr->nextSibling);
          }

          if(rootPtr->parent)
          {
cout << "parent" << endl;
               padWidth -= 5;
               printTree(*rootPtr->parent);
          }
     }
}

The 'cout' statements are for diagnostic purposes only.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
Heather_BAuthor Commented:
That appears correct when you print to the console window, but it's not logically correct. Node1 should be the root,
and node2 & node3 should be one level beneath. There should not be any nodes on the same level as node1. Making node3 the next sibling of the root puts it in the same level as the root. It looks correct when it prints out, but the way I'm doing the padding is probably wrong too.

Node1 should be the root, node2 should be the first child of node1, and node 3 should be the next sibling of node2.

When I pass node1 to the print tree function, all of its pointers point to the proper nodes, so these print out properly.
When I try to make another recursive call, passing another node:
 
          printTree(*rootPtr->firstChild);

when this node enters the function as the new root, all of its pointers are NULL, even though the actual nodes that they are supposed to point to have pointers that are not NULL.






0
 
Heather_BAuthor Commented:
I changed the nodes as below, and only the first 2 print out.

                OutlineItemNode node1("Music", 0);
      OutlineItemNode node2("Rock", 1);
      OutlineItemNode node3("Pop", 2);
      OutlineItemNode node4("New Wave", 4);

      myTree.addRoot(node1);      
      myTree.addFirstChild(node1, node2);
      myTree.addFirstChild(node2, node3);
      myTree.addFirstChild(node3, node4);

Anything that's more than one level removed from the root doesn't print.
0
 
Heather_BAuthor Commented:
Do I need a copy constructor?
0
 
Heather_BAuthor Commented:
I added a copy constructor:            

OutlineItemNode(OutlineItemNode &rhs)
{
    item.text = rhs.item.getText();
    item.id = rhs.item.getId();
    firstChild = rhs.firstChild;
    nextSibling = rhs.nextSibling;
    parent = rhs.parent;

};

...and it did nothing different. I am really at my wit's end here. I would like to make this question worth 5,000 points.
0
 
chip3dCommented:
Your code is a little wired
do u want to link the nodes you have created in main or do you want to copy them to keep them independently in the tree?
Well i guess the second, right?

So you have to change youe addchild and addsibling a little...

void addFirstChild(OutlineItemNode& currentNode, OutlineItemNode& newNode)
     {    
         
           // currentNode already added to Tree, why create a new one?
          OutlineItemNode* newNodePtr;
          newNodePtr = new OutlineItemNode(newNode.item.getText(), newNode.item.getId());


         if(isEmpty())
          {
               cout << "The tree is empty, try to add this item as the root." << endl << endl;
          }
          else
          {
               if(currentNode.firstChild==NULL)
               {
                    newNodePtr->parent = &currentNode;
                    currentNode.firstChild = newNodePtr;
                    last = newNodePtr;
                    current = newNodePtr;
               }
                // this make no sense to me...
               else
               {                    
                    newNodePtr->parent = &currentNode;
                    newNodePtr->nextSibling = currentNode.firstChild;
                    currentNode.firstChild = newNodePtr;
                    last = newNodePtr;  
                    current = newNodePtr;
               }
          }

     };//End addFirstChild

     void addNextSibling(OutlineItemNode& currentNode, OutlineItemNode& newNode)
     {
          // same as addFirstChild, no recreation of currentNode...
          OutlineItemNode* newNodePtr;
          newNodePtr = new OutlineItemNode(newNode.item.getText(), newNode.item.getId());
         
          if(isEmpty())
          {
               cout << "The tree is empty, try to add this item as the root." << endl << endl;
          }

          else
          {
               if(currentNode.nextSibling==NULL)
               {
                    currentNode.nextSibling = newNodePtr;
                    newNodePtr->parent = currentNode.parent;                    
                    last = newNodePtr;
                    current = newNodePtr;
               }
                // well, you never checkt if both siblings have the same parent...
               else
               {    
                    newNodePtr->nextSibling = currentNode.nextSibling;
                    currentNode.nextSibling = newNodePtr;
                    newNodePtr->parent = currentNode.parent;                    
                    last = newNodePtr;
                    current = newNodePtr;
               }
          }

     };//End addFirstChild

you have to modify your main a little:

int main()
{
     MultiTree myTree;
     
     void printTree(OutlineItemNode theRoot);

     OutlineItemNode node1("Music", 0);
     OutlineItemNode node2("Rock", 1);
     OutlineItemNode node3("Pop", 2);
     OutlineItemNode node4("New Wave", 4);

     myTree.addRoot(node1);    
     myTree.addFirstChild(*myTree.current, node2);
     myTree.addNextSibling(*myTree.current, node3);
     myTree.addNextSibling(*myTree.current, node4);
     myTree.addFirstChild(*myTree.current, node1);
     myTree.addFirstChild(*myTree.current, node4);
     myTree.addNextSibling(*myTree.current, node2);

     printTree(myTree.root);

     char d;
     std::cin >> d;
     return 0;
}

also fixed your printTree:

void printTree(OutlineItemNode *rootPtr)
{
     if(rootPtr)
     {
          cout << getPadding(padWidth) << *rootPtr << endl;

          if(rootPtr->firstChild)
          {
               padWidth += 5;
               printTree(rootPtr->firstChild);
          }

          if(rootPtr->nextSibling)
          {
               printTree(rootPtr->nextSibling);
          }

          // um, this will lead to endless recursion -> stack overflow
          /*if(rootPtr->parent)
          {
               padWidth -= 5;
               printTree(rootPtr->parent);
          }*/
     }
}
0
 
Heather_BAuthor Commented:
Thanks chip3d! Believe me, my code looks weird to me too. I'll be sure not to quit my day job and all that. Thanks for your help.
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 6
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now