C++

Forum

 
delete function for binary tree

drunkenmonk (8)
I'm having trouble with the delete function for my binary tree. After thorough testing, I have discovered that the only time I have a crash is after deleting a leaf, and only after deletion when I try traversal again. Here is my functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
 void BinaryTree::DeleteNode(int deleteItem)
 {
	 TNode *current;
	 TNode *trailCurrent;
	 bool found = false;

	 if (root == NULL)
		 cout << "THE TREE IS EMPTY. THERE IS NOTHING TO DELETE." << endl;
	 else
	 {
		 current = root;
		 trailCurrent = root;

		 while (current != NULL && !found)
		 {
			 if (current->datum == deleteItem)
				 found = true;
			 else
			 {
				 trailCurrent = current;
				 if (current->datum > deleteItem)
					 current = current->leftPtr;
				 else
					 current = current->rightPtr;
			 }
		 }
		 if (current == NULL)
			 cout << "THE ITEM TO BE DELETED IS NOT IN THE TREE." << endl;
		 else if (found)
		 {
			 if (current == root)
				 DeleteFromTree(root);
			 else if (trailCurrent->datum > deleteItem)
				 DeleteFromTree(trailCurrent->leftPtr);
			 else
				 DeleteFromTree(trailCurrent->rightPtr);
		 }
		 else
			 cout << "THE ITEM TO BE DELETED IS NOT IN THE TREE." << endl;
	 }


void BinaryTree::DeleteFromTree(TNode* p)
{
	TNode *current;
	TNode *trailCurrent;
	TNode *temp;

	if (p == NULL)
		cout << "ERROR: THE NODE TO BE DELETED IS NULL." << endl;
	else if (p->leftPtr == NULL && p->rightPtr == NULL)
	{
		temp = p;
		p = NULL;
		delete temp;
	}
	else if (p->leftPtr == NULL)
	{
		temp = p;
		p = temp->rightPtr;
		delete temp;
	}
	else if (p->rightPtr == NULL)
	{
		temp = p;
		p = temp->leftPtr;
		delete temp;
	}
	else
	{
		current = p->leftPtr;
		trailCurrent = NULL;

		while (current->rightPtr != NULL)
		{
			trailCurrent = current;
			current = current->rightPtr;
		}

		p->datum = current->datum;

		if (trailCurrent == NULL)
			p->leftPtr = current->leftPtr;
		else
			trailCurrent->rightPtr = current->leftPtr;

		delete current;
	}

}//End DeleteFromTree
//===================


Any help is appreciated.
Athar (4466)
What does the debugger say to this?
drunkenmonk (8)
Actually, gives me one of these:

Unhandled exception at 0x010d256c in ProjectTwo.exe: 0xC0000005: Access violation reading location 0xfeeefef2.
Athar (4466)
That doesn't really sound like you ran it in the debugger.
You need to use the debug version.
Which line does cause it?
Last edited on
drunkenmonk (8)
It happens, not when deleting, but when I'm traversing again afterwards, no matter which traversal method(post, pre, inorder, both recursive and iterative). I'm assuming that after deletion, I am setting pointers wrong.
drunkenmonk (8)
anybody?
Athar (4466)
If you don't know what the debugger is, just say so.
Or rather, look up how to use it with your IDE.
A tip: there'll probably a menu called Debug, select "Start" or "Step into" from there.
Albatross (4553)
When you figure out how to use your debugger, set breakpoints just after all possible problem lines, to isolate your problem. Run the program, and be prepared to hit something like "Continue".

-Albatross
drunkenmonk (8)
I've been trying to debug, but as I said, the problem happens when I try traversal, not when the delete function is called, so when I debug, it breaks during traversal. I am no expert, or I wouldn't be asking for help. It's very difficult to track it that way, meaning that, yes, it is beyond me.
drunkenmonk (8)
solved it, I missed:

void BinaryTree::DeleteFromTree(TNode* &p)//forgot &
Topic archived. No new replies allowed.