Thread: Trees in C++

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    18

    Trees in C++

    Hello all I'm trying to implement a tree in C++ with multiple children. There are compilers errors I'm trying to understand, but most likely it's implementation. I've looked at source codes for trees and most of them use struct to construct a tree node. Why is that?

    What I'm doing is using classes for the nodes inside the tree. I'm having problems instantiating/comparing objects to NULL. How would I check if the object is NULL? I can see a fix if I used structs and have a pointer to the nodes instead.

    Below is the code for the ".h" and .cpp" files

    Code:
    //bfTree.h
    //This is a best first search tree.
    #ifndef BFTREE_H
    #define BFTREE_H
    
    #include <iostream>
    #include <string>
    #include <vector>
    
    class bfTree
    {
     private:
      class tree_node
      {
        int visited;
        int result;
        double percentage;
        tree_node parent;
        std::vector<bfTree::tree_node> children;
      };
    
     public:
      bfTree::tree_node root;
          
      bool is_empty();
    };
    #endif
    Code:
    //bfTree.cpp
    #include <string>
    #include <vector>
    #include <iostream>
    
    #include "bfTree.h"
    
    bool bfTree::is_empty()
    {
      if (root == NULL)
        return true;
      else
        return false;
    }
    The compiler errors:
    Code:
    In file included from HexAI.h:9:0,
                     from Game_of_hex.cpp:9:
    bfTree.h:17:15: error: field ‘parent’ has incomplete type
    Game_of_hex.cpp:60:5: warning: unused parameter ‘argc’
    Game_of_hex.cpp:60:5: warning: unused parameter ‘argv’
    In file included from HexAI.h:9:0,
                     from HexAI.cpp:6:
    bfTree.h:17:15: error: field ‘parent’ has incomplete type
    In file included from bfTree.cpp:5:0:
    bfTree.h:17:15: error: field ‘parent’ has incomplete type
    bfTree.cpp: In member function ‘bool bfTree::is_empty()’:
    bfTree.cpp:9:15: error: no match for ‘operator==’ in ‘((bfTree*)this)->bfTree::root == 0l’
    bfTree.cpp:13:1: warning: control reaches end of non-void function
    I also realized that I might need to overload the "==" for object comparison. Is there any way to instantiate an object to NULL?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    > 18 tree_node parent;
    This needs to be a POINTER.
    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
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You can't instantiate a pointer to "NULL". Either an object exists, or it does not. A pointer works in such a way that it points to something or it does not (NULL).
    Regardless, the way you are doing it is wrong. You declare the object to always have a parent, which is not always true. So either you need some pseudo class that can tell if it's valid or not, or you need a pointer.
    The compile error comes from that you are trying to put an instance of a class you are currently defining into itself (infinite recursion).
    And don't try comparing an object to 0. That makes no sense. 0 is an integer (NULL is a macro that maps to 0) and hence it is WRONG to make a comparison of an existing instance, that is in no way an integer or has any possible integer semantics, to 0. You'd probably want some "is_valid" function.

    Think about that.
    Oh, and btw, don't use NULL. Use nullptr instead. Again, this only works (and should rightly so!) for pointers.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Think about it, if every tree_node contained a parent which was also a tree_node, then the structures size would be infinite.
    You need a pointer partly because you want the parent to either be a tree_node or *nothing*. Also because you want parent to be a link to the parent, not a copy of it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Trees MINI MAXING, probability trees
    By curlious in forum General AI Programming
    Replies: 3
    Last Post: 09-30-2005, 10:57 AM
  2. AVL & BS Trees
    By sweets in forum C++ Programming
    Replies: 1
    Last Post: 04-14-2004, 04:49 PM
  3. Help with (2,3,4)/2-4 trees
    By Nornny in forum C++ Programming
    Replies: 0
    Last Post: 04-10-2004, 04:58 PM
  4. Trees
    By samtay in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2004, 09:35 AM
  5. traversing binary trees or partial trees
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-05-2001, 09:19 PM