Thread: Trouble with binary tree

  1. #1
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166

    Trouble with binary tree

    I'm currently playing around with binary trees, but it seems I can't even get my insert function to work correctly. When I try to compile my code, i get the following error:

    Code:
    Unhandled exception at 0x0121145c in testing.exe: 0xC0000005: Access violation reading location 0xcdcdcdcd.
    Here is the code

    binTree.h
    Code:
    #ifndef GUARD_BINTREE
    #define GUARD_BINTREE
    
    struct node
    {
        int data;
        node* link[2];
    };
    
    class binTree
    {
    private:
        node* root;
    public:
        binTree(): root(0){}
        void insert(int data);
    };
    
    void binTree::insert(int data)
    {
        node* new_node = new node;
        new_node->data = data;
        
        //search and insert
        if(root == 0)
        {
            root = new_node;
            return;
        }
    
        else
        {
            node* it = root;
            int dir;
            while(true)
            {
                dir = it->data < data;
    
                if(it->link[dir] == 0)
                    break;
                else if(it->data == data)
                    return;
    
                it = it->link[dir];
            }
    
            it->link[dir] = new_node;
        }
    }
    #endif
    main.cpp
    Code:
    #include "binTree.h"
    int main(int argc, char** argv)
    {
    
        binTree tree;
        for(int i = 0; i != 10; i++)
            tree.insert(i);
        return 0;
    }
    Stepping through with a debugger shows that it is at the location 0xcdcdcdcd. and supposedly happens at
    Code:
    dir = it->data < data;
    Can anyone see what's wrong?

    Thanks
    Last edited by dra; 05-29-2009 at 03:51 PM.

  2. #2
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    You're not initializing link[] anywhere, for one thing.

  3. #3
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166
    d'oh! How embarrassing! Thanks for the observation.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Can we assume that has solved your problem?

    I like the way you've separated the allocation of the new item from the insertion of it. Most beginners don't do that.

  5. #5
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166
    Yes it has, thank you.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM