C++

Forum

 
Binary Tree -> DeleteItems

warfist (4)
Hi guys! First of all i have to say that i am new to this forum. I've been learning c++ for few months now and still feel kinda unexperienced in many ways.
I hope to find good support from you guys :) Thank you!

Here is my problem: I had to program a binary tree which includes a deleteNode method. It's almost working fine. There is just a problem buth my root. Lets say i add 10 nodes to the tree and 2 are left after i deleted 8 parts. Whenever i try to delete the last 2 parts i am getting an error message.
I really hope you guys can help me out here, i've spent too many hours on this.
Here is the code:

//Treenode.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
#pragma once
class treenode
{
public:
	int data;
	treenode *left;
	treenode *right;


	treenode(int value);
	treenode();
	~treenode(void);
};


//Treenode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include "treenode.h"


treenode::treenode(int value)
{
	left = 0;
	right = 0;
	data = value;
}
treenode::treenode()
{
	left = 0;
	right = 0;
	data = 0;
}


treenode::~treenode(void)
{
}


//binarytree.h (includes all methods to modify/edit a tree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#pragma once
#include "treenode.h"
class BinaryTree
{
public:
	treenode *head;
	treenode *nullnode;

	BinaryTree(void);
	~BinaryTree(void);
	void insertItem(treenode* node, int value);		
	bool deleteItem(treenode* parent,int k);	
	treenode *findNode(treenode *root,int k);		
	treenode *max();								
	treenode *min();								
	int niveau(treenode *root);						
	void niveauPrint(treenode *root, int level);	
	void printInorder(treenode *root);			
	void printPreorder(treenode *root);				
	void printPostorder(treenode *root);			
	void printLevelorder(treenode *root);			
};


//binarytree.cpp (just the delete method, if u need more just ask me :))

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
bool BinaryTree::deleteItem(treenode* parent, int k)
{
	bool found = false;
	treenode *current = parent;
	treenode *prev = parent;
	//if(current->left==nullptr && current->data==k)
	if(current == nullptr)
	{
		cout<<"Tree is empty!"<<endl;
		return false;
	}
	prev = current;
	while(current!=nullptr)
	{
		if(current->data==k)
		{
			found = true;
			break;
		}
		else
		{
			prev = current;

			if(k > current->data)
			{
				current = current->right;
			}
			else 
			{
				current = current->left;
			}
		}
	}
	if(!found)
	{
		cout<<k<<" not found!"<<endl;
		return false;
	}
	
	if((current->left==nullptr&&current->right!=nullptr)||current->left!=nullptr&&current->right==nullptr)
	{
		if(current->left==nullptr&&current->right!=nullptr)
		{
			if(prev->left==current)
			{
				prev->left = current->right;
				delete current;
				current = nullptr;
				cout<<"Element "<<k<<" deleted"<<endl;
				return true;
			}
			
			else
			{
				
				prev->right = current->right;
				delete current;
				current = nullptr;
				cout<<"Element "<<k<<" deleted"<<endl;
				return true;
			}
		}
		else	
		{
			if(prev->left == current)
			{
				prev->left = current->left;
				delete current;
				current = nullptr;
				cout<<"Element "<<k<<" deleted"<<endl;
				return true;
			}
			else
			{
				prev->right = current->left;
				delete current;
				current = nullptr;
				cout<<"Element "<<k<<" deleted"<<endl;
				return true;
			}
		}		
	}
	
	if(current->left==nullptr&&current->right==nullptr)
	{
		if(prev->left==current)
		{
			prev->left=nullptr;
		}
		else
		{
			prev->right = nullptr;
		}
		delete current;
		cout<<"Element "<<k<<" deleted"<<endl;
		return true;
	}

	if(current->left!=nullptr&&current->right!=nullptr)
	{
		treenode *check = current->right;
		if((current->left==nullptr)&&(current->right==nullptr))
		{
			current = check;
			delete check;
			current->right = nullptr;
			cout<<"Element "<<k<<" deleted"<<endl;
			return true;
		}
		else	
		{
			if((current->right)->left!=nullptr)
			{
				treenode *ltemp;
				treenode *ltempPrev;

				ltempPrev = current->right;
				ltemp = (current->right)->left;

				while(ltemp->left!=nullptr)
				{
					ltempPrev = ltemp;
					ltemp = ltemp->left;
				}
				current->data = ltemp->data;
				delete ltemp;
				ltempPrev->left = nullptr;
				cout<<"Element "<<k<<" deleted"<<endl;
				return true;
			}
			else
			{
				treenode* temp= current->right;
				current->data = temp->data;
				current->right = temp->right;
				delete temp;
				cout<<"Element "<<k<<" deleted"<<endl;
				return true;
			}
		}
	}
}



First part: Node with a child
Part two: removing a leaf
Part three: Node with 2 children

LB (13399)
Your deleteItem function is over 50 lines long, it seems unnecessarily complex. I think you should be able to simplify it dramatically, and most likely if that does not eliminate the problem it will make it easier to find.
Last edited on
SeiZa (37)
I also think there is little reasearch made on understanding why it doesn't work.

You should try and give a number to the nodes and see which ones are left... try to see if there is some kind of "pattern" that makes your 2 nodes impossible to delete.
warfist (4)
Thanks for your answers. I will try to reduce it. It's just hard for me to lower it since i tried to code is as easy as possible.
Last edited on
SeiZa (37)
I believe you can print out some output while you're deleting the nodes so you know which one are currently being deleted. And you can have a clear idea on how your tree is being run through.

My personal idea is that you lose the pointer on where the 2 nodes are left. :)
warfist (4)
Thats what i thought too. Wait, i will give it a try

Edit: Ok, if i delete the tree from both parts until i reach the root everything works fine. Even the Root can be deleted.

The problem right now is that the cout can't access my head->data now...
i can't even test if head==nullptr or anything else.
Last edited on
SeiZa (37)
You lost/delete your head pointer somewhere :)

try to use valgrind or gdb to check where you lost it.
Topic archived. No new replies allowed.