Hello,

I'm working through an example from the book Data Structures and Algorithms for Game Developers. I've reached a brick wall and suspect an issues with the book's source code. Dealing with trees, we have the following data structure and implementation:

#include<iostream>

using namespace std;


class Node
{
   public:
      Node(int obj) : m_object(obj), m_next(NULL),
                      m_prev(NULL), m_child(NULL)
      {
         cout << "Node created!" << endl;
      }


      ~Node()
      {
         m_prev = NULL;

         if(m_child != NULL)
            delete m_child;

         if(m_next != NULL)
            delete m_next;

         m_child = NULL;
         m_next = NULL;

         cout << "Node deleted!" << endl;
      }


      void AddChild(Node *node)
      {
         if(m_child == NULL)
            m_child = node;
         else
            m_child->AddSibling(node);
      }


      void AddSibling(Node *node)
      {
         Node *ptr = m_next;

         if(m_next == NULL)
            {
               m_next = node;
               node->m_prev = this;
            }
         else
            {
               while(ptr->m_next != NULL)
                  ptr = ptr->m_next;

               ptr->m_next = node;
               node->m_prev = ptr;
            }
      }


      void DisplayTree()
      {
         cout << m_object;

         if(m_next != NULL)
            {
               cout << " ";
               m_next->DisplayTree();
            }

         if(m_child != NULL)
            {
               cout << endl;
               m_child->DisplayTree();
            }

      }


      bool Search(int value)
      {
         if(m_object == value)
            return true;

         if(m_child != NULL)
            {
               if(m_child->Search(value) == true)
                  return true;
            }

         if(m_next != NULL)
            {
               if(m_next->Search(value) == true)
                  return true;
            }

         return false;
      }


   private:
      int m_object;
      Node *m_next, *m_prev, *m_child;
};


int main(int args, char *arg[])
{
   cout << "Simple Tree Data Structure" << endl;
   cout << "Chapter 9: Trees" << endl << endl;


   // Manually create the tree...
   Node *root = new Node(1);
   Node *subTree1 = new Node(3);

   root->AddChild(new Node(2));

   subTree1->AddChild(new Node(5));
   subTree1->AddChild(new Node(6));

   root->AddChild(subTree1);
   root->AddChild(new Node(4));

   cout << endl;


   // Display the tree...
   cout << "Tree contents by level:" << endl;

   root->DisplayTree();

   cout << endl << endl;



   
   delete subTree1;

   root->DisplayTree();

   cout << endl << endl;

   return 1;
}

The issue is with deleting the "subTree1". When I do this, and then call DisplayTree() on the root node, I get an infinite loop. Any suggestions on what the issue is? I would expect calling delete on the subTree1 would remove that node and any sub nodes, but clearly this is not the case. Please help!

Rhetorical question: If 'root' owns 'child' and you delete 'child', where/how does root's child pointer get set to null?

"I would expect calling delete on the subTree1 would remove that node and any sub nodes, but clearly this is not the case"

If your pointer points to memory that has been freed already, but you are still trying to access it, it might just-so-happen to still be storing the old memory (if by chance it hasn't been overwritten yet), and your code may seem to still work when it really doesn't. So I think the nodes are removed, but it just looks like it isn't, because your parent node is still pointing at the non-existant node's old memory.

Also:

m_prev = NULL; //Why? How does this benefit you?

if(m_child != NULL) //You don't need to check for null before calling 'delete', 'delete' already checks for null for you.
delete m_child;

if(m_next != NULL) //Ditto for the previous comment.
delete m_next;

m_child = NULL; //If this class is destructing, why set its pointers to null? That is pointless.
m_next = NULL;

I'd consider those 'mistakes', but ones that don't cause bugs.

For a non-mistake nitpick: If you are using a modern compiler with C++11 or greater enabled, you should be using 'nullptr' instead of 'NULL'.

Also, if you are using C++11, code looks much nicer like this:

class Node
{
public:
    //...

private:
    int m_object = 0;
    Node *m_next = nullptr; //Initialized directly in the class itself.
    Node *m_prev = nullptr;
    Node *m_child = nullptr;
};

Make sure you don't actually manually create your tree in real code. Instead, you need a class that handles that for you, because it's too easy to make mistakes.

EDIT: Well apparently, Servant of the Lord was a bit quicker, you can still

read this if you want another way of solving it.

Hello,

Excuse me, as I don't have enough time yet to completely check what causes the

bug. For now it seems that you don't increment the value of m_child or m_next.

When I want to display my nodes I do it like this:

First I make a class List. In this class I have a pointer to the first Node in the list

and a function to add a Node and to print the Nodes (and ofcourse a contructor and a

desctructor).

This is the print function to help you a bit:

void displayTree()
{
    Node* index = beginPointer; // index is a pointer that points to the Node's in the list
    while(index != NULL){
         cout << index->printNodeValue();
         index = index->getNextNode();
    }
}

I could have given you the code for the whole class, but its way better for

your understanding to first try and make it youself (if you want to go this way ofcourse).

If you really don't know how to do it (after you tried) you can always post here,

then I will help you more. (But first really try, it will help you!).

Excuse me that I couldn't help you yet with your answer directly.

I will be back soon and, if the answer isn't given, I will give it still.

Good luck!

-RaoulJWZ

Good luck and remember,

void pnode(Node *p)
{
    printf("Node at %p\n", p);
    printf("  next at %p\n", p->m_next);
    printt("  prev at %p\n", p->m_prev);
    printf("  child at %p\n", p->child);
}