Please help with BST

This is a discussion on Please help with BST within the C++ Programming forums, part of the General Programming Boards category; I'm working on a BST for the first time and need some big time help. I've gotten some of the ...

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    37

    Please help with BST

    I'm working on a BST for the first time and need some big time help. I've gotten some of the functionality written and was wanting to test it so I've got this simple code that Inserts a node into the tree and then reads it:

    Code:
    #include <string>
    
    using namespace std;
    
    void main()
    {
    	CharString name = "Tyson";
    	CharString att1 = "Is a scud";
    	CharString att2 = "Is Married";
    	int attcnt = 2;
    	TreePtr X = new Node;
    	strcpy(X->Info.Name, name);
    	X->Info.AttributeCount = attcnt;
    	strcpy(X->Info.Attribute[0], att1); 
    	strcpy(X->Info.Attribute[1], att2); 
    
    	BST Original;
    
    	Original.Insert (X);
    	Original.TestPrint (X);
    
    	cout << "Do you want to continue?"<<endl;
    	int spare;
    	cin >> spare;
    	
    }
    When I debug its getting an error in the TestPrint function, which is here:
    Code:
    void BST::TestPrint (TreePtr P)
    {
    	if (P)
    	{
    		TestPrint (P->Left);
    		cout << Root->Info.Name << endl;
    		TestPrint (P->Right);
    	}
    }
    It goes through the loop fine the first time but when it hits TestPrint (P->Left) the second time it dies. I get this message:

    Unhandled exception at 0x00433f4c in Binary_Search_Tree.exe: 0xC0000005: Access violation reading location 0xcdcdcee9.

    Can someone help find the problem. I would appreciate it.

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    0xcdcd it what MSVC puts in allocated memory when in debug mode. Are you initializing your Left/Right pointers to NULL when you create a new node? If you are, then you're doing something bad in code you didn't post.

    Zip up all your code and post it - the problem could be anywhere.

    gg

  3. #3
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    try this:

    Code:
    void BST::TestPrint (TreePtr *P)
    Not sure if this solves the problem. But my guess would be the same as Salemīs. When you add a node are you "linking" the links(pointers) correctly???

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    37
    Thanks for the replies, here's all the code.
    Attached Files Attached Files

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    Looks like I called this one , although it really could have been any number of things:
    Code:
    P->Left = NULL;
    P->Left = NULL; //Poor Right, he's all left out (no pun intended)
    You also have some memory leaks...
    Code:
    TreePtr P = new Node;
    ...
    P = data; //nevermind mr. new, I think I'll use this instead
    Haven't looked at the rest of your code, but your test program will run properly when you fix these problems.

    gg

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    37
    Thanks for the help, that fixed it. But I'm not sure what you mean here:

    ---------------------------------------------------------------------------------
    You also have some memory leaks...

    Code:
    TreePtr P = new Node;
    ...
    P = data; //nevermind mr. new, I think I'll use this instead
    ----------------------------------------------------------------------------------

    What should I do instead?

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    In your design, you have to decide who is going to manage memory, the tree or the user. I'd let the tree do it.

    When you say "P = data", you just overwrote the pointer that new returned to you - memory that will never be deleted, thus a memory leak. If you want to copy the node data then you can say "*P = *data".

    Remember, every new should have a cooresponding delete - you're missing one in main().

    gg

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    37
    Should I also have done "*P->Left = NULL"? (notice the *)

  9. #9
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    NULL is an address, so you can go:

    P->left = NULL;

    without the preceding * before P, assuming left is a pointer, too. the * preceding a pointer says use the value stored at the address, not the address itself.

    the * in front of data in CodePlugs post:

    *P = *data;

    is only necessary if data and P are both pointers. If data is a routine variable, and not a pointer per se, then you don't need the * in front of data. Likewise for P.
    Last edited by elad; 04-09-2003 at 09:13 AM.

  10. #10
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    No. "*" will dereference the Left pointer, which will give you type Node, not a pointer, so setting it to NULL doesn't make sense.

    Don't confuse setting a pointer value and setting the value of what the pointer points to.

    Code:
    int *p = new int; //assign the pointer p a new value
    *p = 5; //assign what p points to a new value
    gg

  11. #11
    Registered User
    Join Date
    Mar 2002
    Posts
    37
    I need some more help with this program,


    from main...
    Code:
    BST Original;
    
    Original.Insert (X);
    Original.Insert (Y);
    Original.InOrder (cout);
    I think the insertion works alright but when I get to InOrder it fails. Here's the function...
    Code:
    void BST::InOrder (ostream &x)
    {
    	InOrderTraversal (Root, x);
    }
    
    void BST::InOrderTraversal (TreePtr root, ostream & file)
    {
    	
    	if (root)
    	{
    		InOrderTraversal (root->Left, file); <----- here's the error 
    		file << root->Info.Name << endl;
    		InOrderTraversal (root->Right, file); 
    		
    	}
    }
    The error message I'm getting is:
    Unhandled exception at 0x00432b00 in Binary_Search_Tree.exe: 0xC0000005: Access violation reading location 0xfeef000a.

    Any idea what's wrong?

  12. #12
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    gonna have to post your code again...

    gg

  13. #13
    Registered User
    Join Date
    Mar 2002
    Posts
    37
    here ya go.
    Attached Files Attached Files

  14. #14
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    Don't "delete P" on Insert(), that's what DestroyTree() is for - to delete everything you new'd.

    Code:
    int *p = new int;
    int *q = p;
    
    delete p;  //the memory pointed to by both p and q is now invalid
    Also, you need to heed your compiler's warnings:
    BST.cpp(70) : warning C4390: ';' : empty controlled statement found; is this the intent?
    BST.cpp(88) : warning C4700: local variable 'Parent' used without having been initialized
    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST array
    By Iron_Shortage in forum C Programming
    Replies: 5
    Last Post: 04-20-2009, 03:04 PM
  2. bst in postorder to file algorithm?
    By iunah in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 05:13 AM
  3. problem inserting into recursive BST
    By nfrandsen in forum C Programming
    Replies: 4
    Last Post: 09-13-2008, 07:03 PM
  4. I would love some input on my BST tree.
    By StevenGarcia in forum C++ Programming
    Replies: 4
    Last Post: 01-15-2007, 12:22 AM
  5. Splitting BST General
    By cpp_is_fun in forum C++ Programming
    Replies: 1
    Last Post: 11-25-2005, 01:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21