Jump to content
  • Advertisement
Sign in to follow this  
flatearther43

Tree Node Deletion

This topic is 995 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites

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, 

Edited by RaoulJWZ

Share this post


Link to post
Share on other sites
Drawing pointer operations on paper as suggested Khatharr works great! When doing pointermanipulation, I often also draw variables (like p and q) pointing to the nodes as well, so it's easy to see what "p->next = q->prev" actually does. If you experience crashes with pointers, you may want to print the nodes and their addresses. Something like
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);
}
Around this, add a loop that follows the pointer, and prints each node. If you have only a few nodes, it's easy to check whether the nodes point to each other properly.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!