C++

Forum

 
Pointer Problems?

cymatic (7)
Can someone tell me why my nodes are not getting inserted using this technique?
I've never programmed in c++ before a couple weeks ago.
thanks in advance.


//Binary Tree Constructor
BinTree::BinTree(){
this->root=NULL;
}

void BinTree::insert(int n){
if (this->root==NULL){
Node* newNode = new Node(n); //create new node
this->root=newNode;
} else {
if(n < this->root->data){place(n,this->root->left);}
if(n > this->root->data){place(n,this->root->right);}
}
}

void BinTree::place(int n, Node* curr){
cout<<"in place()"<<endl;
if (curr==NULL){
Node* newNode = new Node(n);
curr = newNode;
//cout<<curr->data+" Node placed successfully?"<<endl;
}else{
if(n > curr->data){cout<<"placing r"<<endl;place(n,curr->right);}
if(n < curr->data){cout<<"placing l"<<endl;place(n,curr->left);}
}

}
mzimmers (578)
A couple of requests:

1. please put your code inside code tags; it's easier for us to read.
2. can you post the definition of the BinTree class
closed account (D80DSL3A)
Try passing the Node* to the place() by reference.
ciphermagi (807)
void BinTree::place(int n, Node &curr)
Try that.
cymatic (7)
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
 
#include <string>
#ifndef BINTREE_H
#define BINTREE_H

//Node Struct:
//Info Object
struct Node{
	int data;
	Node* left;
	Node* right;
	Node(int);
};

//Binary Tree List Class

class BinTree{
	Node* root;  //pointer to root of tree
	
	private:

	void place(int, Node*); //recursive placement method to help insert
	Node* seek(int, Node*);
	void rootRep(Node*);
	Node* pre(Node*);
	Node* post(Node*);
	void printTree(Node*);
	
	public:
	
	BinTree();        //constructor
	void insert(int);  //insert new node with int data
	void remove(int);  //remove node matching int data
	int next(int);   //returns the lowest number in tree gt int
	void print();
};
#endif


closed account (D80DSL3A)
@cymatic. Any thoughts on the advice you've been given so far?
cymatic (7)
I tried passing the pointer as a reference, but it didn't seem to help. references are a little strange to me. I don't understand why this isn't working. And it's the easy part (insertion). :( thanks for the prompt replies!
closed account (D80DSL3A)
I had hoped that would work. You tried changing the function to:
void BinTree::place(int n, Node*& curr) ?
This is needed so that the assignment curr = newNode; in the place() will affect the passed value of curr.

I don't see a definition of the Node constructor. It should assign left = right = NULL;

What is the program doing? Does the print() at least display the root node?
Could you post more code (function definitions and main() )?
Last edited on
cymatic (7)
It did work! Thanks. I need to wrap my head around references better.
closed account (D80DSL3A)
You're welcome. I'm glad that turned out to be the only problem.
cymatic (7)
that was the only problem because I hadn't gotten around to testing my remove method.
I'll just post the whole implementation file with the main() I'm using for testing below:
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
#include "BinTree.h"
#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

//Node Constructor
Node::Node(int n){
	this->data=n;
	this->left=NULL;
	this->right=NULL;
}

//Binary Tree Constructor	
BinTree::BinTree(){
	this->root=NULL;
}
//insertion method	
void BinTree::insert(int n){
	if (this->root==NULL){
		Node* newNode = new Node(n);  //create new node
		this->root=newNode;
	} else {
		if(n < this->root->data){place(n,this->root->left);}
		if(n > this->root->data){place(n,this->root->right);}
	}
}
//recursive helper method for insertion
void BinTree::place(int n, Node*& curr){
	if (curr==NULL){
		Node* newNode = new Node(n);
		curr = newNode;	
	}else{
		if(n > curr->data){place(n,curr->right);}
		if(n < curr->data){place(n,curr->left);}
	}
	
}
//remove method for deleting nodes
//checks node data from parent pointer
void BinTree::remove(int n){
	Node* pFound;
	Node* found;
	Node* tmp;
	cout<<"removing ";
	cout<<n<<endl;
	if(this->root->data!=n){
		if(n>this->root->data){
			if(root->right->data==n){
				pFound = this->root;
				found = this->root->right;
			}else{
				pFound = seek(n,this->root->right);
				if(n>pFound->data){
					found = pFound->right;
				}else{
					found = pFound->left;
				}
			}	
		}else{
			if(root->left->data==n){
				pFound = this->root;
				found = this->root->left;
			}else{
				pFound = seek(n,this->root->left);
				if(pFound->data<n){
					found = pFound->right;
				}else{
					found = pFound->left;
				}

			}
		}
		if((found->left==NULL)&&(found->right==NULL)){
			tmp = found;
			if(n>pFound->data){pFound->right=NULL;}else{pFound->left=NULL;}
			delete tmp;
		}else{
			if((found->left==NULL)&&(found->right!=NULL)){
				tmp = found;
				if(n>pFound->data){pFound->right=found->right;}else{pFound->left=found->right;}
				delete tmp;
			}else{
				if((found->right==NULL)&&(found->left!=NULL)){
					tmp = found;
					if(n>pFound->data){pFound->right=found->left;}else{pFound->left=found->left;}
					delete tmp;
				}else{
					if((found->right!=NULL&&found->left!=NULL)){
						found->data=rootReplace(found);
					}
				}	
			}
		}
	}else{
		this->root->data=rootReplace(this->root);
	}
}
//recursive method for locating a value in tree
//returns pointer to parent of node to be deleted
Node* BinTree::seek(int n, Node*& curr){
	if(curr==NULL){
		return NULL;
	}else{
		if(n==curr->right->data||n==curr->left->data){
			return curr;
		}else{
			if(n>curr->data){
				return seek(n, curr->right);
			}else{
				return seek(n, curr->left);
			}
		}
	}
}
//helper method for replacing nodes with 2 children
int BinTree::rootReplace(Node*& tmpRoot){
	Node* tmp;
	srand(time(NULL));
	if(((rand()%50+1)%2)==0){
		tmp= pre(tmpRoot);
	}else{
		tmp= post(tmpRoot);
	}
	int keep=tmp->data;
	remove(keep);
	return keep;
}

//finds next smallest value in tree
Node* BinTree::pre(Node*& tmpRoot){
	tmpRoot=tmpRoot->left;
	while(tmpRoot->right!=NULL){
		tmpRoot=tmpRoot->right;
	}
	return tmpRoot;
}

//finds next largest value in tree
Node* BinTree::post(Node*& tmpRoot){
	tmpRoot=tmpRoot->right;
	while(tmpRoot->left!=NULL){
		tmpRoot=tmpRoot->left;
	}
	return tmpRoot;
}

//returns number equal to or greater than argument
int BinTree::next(int n){
	Node* tmp;
	tmp=seek(n,this->root);
	if(tmp!=NULL){
		if(n>tmp->data){return tmp->right->data;}else{return tmp->left->data;}
	}else{
		tmp=this->root;
		while(tmp->data<n&&tmp!=NULL){
			if(n>tmp->data){tmp=tmp->right;}else{tmp=tmp->left;}
		}
		if(tmp!=NULL){
			return	tmp->data;
		}else{
			return -1;
		}
	}
}

//recursive method to help with print()
void BinTree::printTree(Node*& curr){
	if(curr!=NULL){
	cout << "(";
	printTree(curr->left);
	cout<<curr->data;
	printTree(curr->right);
	cout << ")";
	}
}

//method to print contents of tree
void BinTree::print(){printTree(this->root);cout<<endl;}
	
int main(){
	BinTree bt = BinTree();
	srand(time(0));
	int nums[10]={5,3,8,4,6,10,7,1,2,9};
	for(int i=0; i<10; i++){
		cout<<nums[i];
		cout<<" ";
	} 
	cout<<endl;
	for(int i=0; i<10; i++){
		bt.insert(nums[i]);
	}
	bt.print();
	bt.remove(nums[0]);
	bt.print();
	
}


I know it's not the best code. :( But what is interesting to me is that I can successfully remove any node initially except for 5 and 9.
8 can only be successfully removed if my rootReplace method randomly chooses to replace it with the next smallest number (7) instead of the next largest number(9). rootReplace on 3 works either way. I don't know that I'm dealing with these pointers properly still.

thanks again in advance for any input
Last edited on
closed account (D80DSL3A)
That's a somewhat more complicated function to troubleshoot!

I think you got carried away with passing pointers by reference in your program. It was necessary in the place function, but look what happens when rootReplace is called where you handle the 2 child case (lines 91,92):
1
2
 
if((found->right!=NULL&&found->left!=NULL)){
	found->data=rootReplace(found);

Here, found is passed by ref. to rootReplace, which passes it by ref. to pre() or post():
1
2
3
4
5
6
7
8
9
10
11
12
 
int BinTree::rootReplace(Node*& tmpRoot){
	Node* tmp;
	srand(time(NULL));
	if(((rand()%50+1)%2)==0){
		tmp= pre(tmpRoot);
	}else{
		tmp= post(tmpRoot);
	}
	int keep=tmp->data;
	remove(keep);
	return keep;
}

Then these functions change the pointer. Example is pre():
1
2
3
4
5
6
7
 
Node* BinTree::pre(Node*& tmpRoot){
	tmpRoot=tmpRoot->left;// found is being changed here!
	while(tmpRoot->right!=NULL){
		tmpRoot=tmpRoot->right;// and here!
	}
	return tmpRoot;
}

By the time replaceRoot() returns, found has been changed and the assignment:
found->data=rootReplace(found);
won't be changing the data for the 2 child node.
I suggest passing the Node* by value in all functions EXCEPT for the place().

I see another issue on line 107 in the seek function:
if(n==curr->right->data||n==curr->left->data)
If curr has only 1 child then I see a crash because one of curr->left or curr->right will = NULL.
You had no such problem when trying to remove the Node with data=9? It has a single child parent (with data=10).
cymatic (7)
ok, regrouped with some help from a teacher. as I understand it, this should work. in the 2-child case, the line where curr->data is being set using tmp->data, (which was set using getMax) is giving compile time error saying tmp was not declared in this scope. I thought that since tmp is a reference, it has access to the int data field of the node it's pointer's pointer is pointing to. haha sounds weird. is there any obvious reason I'm missing here:

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
 
void BinTree::remove(int n, Node*& curr){
	if(curr==NULL){
		return;
	}else{
		if(n<curr->data){remove(n,curr->left);
	}else{
		if(n>curr->data){remove(n,curr->right);
	}else{
		if(n==curr->data){
			if(curr->left==NULL&&curr->right==NULL){
				Node* tmp=curr;
				curr=NULL;
				delete tmp;
			}else{
				if(curr->left!=NULL&&curr->right==NULL){
					Node* tmp=curr;
					curr=curr->left;
					delete tmp;
			}else{
				if(curr->left==NULL&&curr->right==NULL){
					Node* tmp=curr;
					curr=curr->right;
					delete tmp;
			}else{
				if(curr->left!=NULL&&curr->right!=NULL){
					srand(time(NULL));
					if(((rand()%50+1)%2)==0){
						Node*& tmp= getMax(curr->right);
					}else{
						Node*& tmp= getMax(curr->left);}
					curr->data=tmp->data;
					remove(tmp->data,tmp);
				}
			}}}}}}}
}


//finds largest value in tree rooted at tmpRoot
Node*& BinTree::getMax(Node*& tmpRoot){
	if(tmpRoot->right!=NULL){
		return getMax(tmpRoot->right);
	}else{
		return tmpRoot;
	}
}
cymatic (7)
ok, so I figured out that tmp wasn't getting initialized in my random number if statement that chooses which side of the node to go down for a replacement value. why, though? If rand is divisible by 2, right, if not, left. Seems like it should always get one or the other. Is it a compiler issue?
Topic archived. No new replies allowed.