C++

Forum

 
problem with binary trees

kretze (17)
Write your question here.
hy guya i have a problem with binary trees(im total beginer in binary trees today is first time when i do something with that stuff) i konw that my question is litle wierd but i realy dont know how can i call function displayinorder in main program can someone please help me??? thanks guys

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
 
  #include <iostream>   
#include <stdlib.h> 
#include <string> 
using namespace std;

class intbinarySearch
{
private:
	int value;
	intbinarySearch *left;
	intbinarySearch *right;


	intbinarySearch*root;



public:
	intbinarySearch(intbinarySearch l, intbinarySearch r, int v)
	{
		*left = l;
		*right = r;
		value = v;
	}

	intbinarySearch()
	{
		root = nullptr;
	}

	void insert(intbinarySearch *&newnode, intbinarySearch*&nowptr)
	{
		if (newnode == nullptr)
			newnode = nowptr;
		else if (nowptr->value < newnode->value)
			insert(newnode->left, nowptr);
		else
			insert(newnode->right, nowptr);
		
	}

	void insertNood(int num)
	{
		intbinarySearch *newnode=nullptr;
		newnode = new intbinarySearch;
		newnode->value = num;
		newnode->left = newnode->right = nullptr;

		insert(root, newnode);


	}


	

	void displayInORder(intbinarySearch *nodeptr)const
	{
		if (nodeptr)
		{
			displayInORder(nodeptr->left);
			cout << nodeptr->value << endl;
			displayInORder(nodeptr->right);
		}
	}


};
int main()
{
	intbinarySearch tree;
	

	tree.insertNood(3);
	tree.insertNood(2);
	tree.insertNood(6);
	tree.insertNood(12);

	
	

	system("pause");// 
	return 0;
}
Ganado (6808)
Don't call the current function you have directly, call one without any arguments that then calls the recursive function.

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
 
	
  private:
	void displayInORder(intbinarySearch *nodeptr)const
	{
		if (nodeptr)
		{
			displayInORder(nodeptr->left);
			cout << nodeptr->value << endl;
			displayInORder(nodeptr->right);
		}
	}

  public:
	void displayInORder() const
	{
		if (root)
		{
		    displayInORder(root);
		}
	}

};
int main()
{
	intbinarySearch tree;
	

	tree.insertNood(3);
	tree.insertNood(2);
	tree.insertNood(6);
	tree.insertNood(12);

	tree.displayInORder();
	

	return 0;
}


Also note that you capitalized your R in ORder. C++ is case sensitive.
kretze (17)
now works....thank you so so much ganado :)
tpb (1495)
displayInORder(intbinarySearch *nodeptr) should be static.
kretze (17)
hy guys i have one question now i play little bit with threes does couple new functions in program in now doesent work(shocking) :)....can pleae anyone help me with that problem...problem is when i deleting a number and then wont to display new numbers in order just threw me next fail:Exception thrown: read access violation.





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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
 
#include <iostream>   
#include <stdlib.h> 
#include <string> 
using namespace std;

class intbinarySearch
{
private:
	int value;
	intbinarySearch *left;
	intbinarySearch *right;


	intbinarySearch*root;



public:
	intbinarySearch(intbinarySearch l, intbinarySearch r, int v)
	{
		*left = l;
		*right = r;
		value = v;
	}

	intbinarySearch()
	{
		root = nullptr;
	}

	void insert(intbinarySearch *&newnode, intbinarySearch*&nowptr)
	{
		if (newnode == nullptr)
			newnode = nowptr;
		else if (nowptr->value < newnode->value)
			insert(newnode->left, nowptr);
		else
			insert(newnode->right, nowptr);
		
	}

	void insertNood(int num)
	{
		intbinarySearch *newnode=nullptr;
		newnode = new intbinarySearch;
		newnode->value = num;
		newnode->left = newnode->right = nullptr;

		insert(root, newnode);


	}


	

	void displayInORder(intbinarySearch *nodeptr)const
	{
		if (nodeptr)
		{
			displayInORder(nodeptr->left);
			cout << nodeptr->value << endl;
			displayInORder(nodeptr->right);
		}
	}


	void displayInORder() const
	{
		if (root)
		{
			displayInORder(root);
		}
	}



	void displayPreeOrder(intbinarySearch *nodeptr)const
	{
		if (nodeptr)
		{
			cout << nodeptr->value << endl;
			displayPreeOrder(nodeptr->left);
			displayPreeOrder(nodeptr->right);
		}
	}


	void displayPreeOrder()
	{
		if (root)
		{
			displayPreeOrder(root);
		}
	}


	void displayPostOrder(intbinarySearch *nodeptr)
	{
		if (nodeptr)
		{
			displayPostOrder(nodeptr->left);
			displayPostOrder(nodeptr->right);
			cout << nodeptr->value << endl;
		}
	}

	void displayPostOrder()
	{
		if (root)
		{
			displayPostOrder(root);
		}
	}


	bool searchNode(int num)
	{
		intbinarySearch *nodeptr = root;
		while (nodeptr)
		{
			if (nodeptr->value == num)
				return true;
			else if (num < nodeptr->value)
				nodeptr = nodeptr->left;
			else
				nodeptr = nodeptr->right;

		}
		return false;
	}


	void makeDeletion(intbinarySearch *&nodeptr)
	{
		
		intbinarySearch *tempNodeptr = nullptr;
		if (nodeptr == nullptr)
			cout << "connot delete empty node ";
		else if (nodeptr->right == nullptr)
		{
			tempNodeptr = nodeptr;
			nodeptr = nodeptr->left;
			delete tempNodeptr;
		}
		else if (nodeptr->left == nullptr)
		{
			tempNodeptr = nodeptr;
			nodeptr = nodeptr->right;
			delete tempNodeptr;
		}
		else
		{
			tempNodeptr = nodeptr->right;
			while (tempNodeptr->left)
				tempNodeptr = tempNodeptr->left;
			tempNodeptr->left = nodeptr->left;
			tempNodeptr = nodeptr;
			nodeptr = nodeptr->right;
			delete tempNodeptr;
			
		}

	}

	void deleteNode(int num, intbinarySearch *nodeptr)
	{
		if (num < nodeptr->value)
			deleteNode(num, nodeptr->left);
		else if (num > nodeptr->value)
			deleteNode(num, nodeptr->right);
		else
			makeDeletion(nodeptr);

	}

	void remove(int num)
	{
		deleteNode(num, root);
	}

	
};
int main()
{
	intbinarySearch tree;
	
	
	tree.insertNood(5);
	tree.insertNood(8);
	tree.insertNood(3);
	tree.insertNood(12);
	tree.insertNood(9);




	cout << "displaying numbers in order.......\n";
	tree.displayInORder();


	cout << "displaying numbers in preeOrder........\n";
	tree.displayPreeOrder();


	cout << "displaynig numbers int postOrder..........\n";
	tree.displayPostOrder();


	if (tree.searchNode(8))
		cout << "8 was found in three.\n";
	else
		cout << "8 wasent found in the three\n";


	if (tree.searchNode(15))
		cout << "15 was found in the three\n";
	else
		cout << "15 wasnt found tn the three\n";




	cout << "again displaying in order\n";
	tree.displayInORder();

	cout << "now i gonna remove 8\n";
	tree.remove(8);

	cout << "and now i gonna remove 3\n";
	tree.remove(3);


	cout << "now numbers in order looks like that\n";
	tree.displayInORder();




	


	
	system("pause");// 
	return 0;
}
Last edited on
dhayden (5798)
First, You really need two classes here, a class for a node within a tree, and a class for the tree itself. The node class contains just the left and right pointers. The tree class contains a root pointer and all the methods. It's possible to write this so that the node class is within the tree class, but since you're a beginner, I'll assume that you don't know how to do that:

Second, I'd do displayInOrder() differently. Since it's a method, you can just have it operate on the object upon which it was called. The only challenge is that you then must check for nullptr in the code:
1
2
3
4
5
6
 
        void displayInOrder() const
        {
            if (left) left->displayInOrder();
            cout << value << endl;
            if (right) right->displayInOrder();
        }

and in main, you call it with:
tree.displayInOrder();

Third, the constructor is wrong. You're passing intbinarySearch instances by value. That means it's pointing left and right to the parameters that immediately get destroyed, causing memory corruption. It should be :
1
2
3
4
5
6
 
        intbinarySearch(intbinarySearch *l, intbinarySearch *r, int v)
        {
                left = l;
                right = r;
                value = v;
        }


kretze (17)
clas within class you mean something like that??
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
 
class node
{
private:
	node *left;
	node *right;

	class tree
	{
	private:
		int valuee;
		tree *root;
	};



	public:
		node(node *l, node*r)
		{
			left = l;
			right = r;
		}

	
	
};

Thomas1965 (4571)
Another option is to put the node into an anonymous namespace.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
namespace 
{
  template<class T>
  struct Node
  {
    T value;
    Node *left;
    Node *right;
  };  
}

template<class T>
class Tree
{
private:
  Node<T> *root = nullptr;
public:
  // all necessary funtions 
};
Last edited on
dhayden (5798)
class within class you mean something like that??

Yes, but the other way around. The node class should be within the tree class, no tthe other way around. The node class is just part of the tree's implementation so the user shouldn't need to see it.
1
2
3
4
5
6
7
8
 
class Tree {
private:
    class Node {
    public:
        ...
    };
....
};
kretze (17)
hy guys i ve been on vacation to today....so today a play little with this trees and i just get it i know that was not that hard but i dont just dont know why i dont get it(sory for my english im not form UK or US)....can anyone tell me what i did wrong 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
 
class tree
{
private:
	tree *left;
	tree *right;
	int val;

	class NODe
	{
	public:
		NODe *root;
		NODe()
		{
			root = nullptr;
		}

		
	
	};


	void insert(tree *&newNode, tree *&newPtr)
	{
		if (newNode == nullptr)
			newNode = newPtr;
		else if (newPtr->val < newPtr->val)
			insert(newNode->left, newPtr);
		else
			insert(newNode->right, newPtr);
	}

	void InsertNode(int num)
	{
		tree *newnode = nullptr;
		newnode = new tree;
		newnode->left = newnode->right = nullptr;
		

		
	}
};
Thomas1965 (4571)
Why don't you use the class variables left and right instead of local variables which go out of sciope and leak memory as well.

Why don't you get a book about data structures and learn it properly?
dhayden (5798)
Try starting with this.
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
 
class tree {
private:
    // A node in the tree has a value, and left & right pointers
    class Node {
    public:
	Node * left, *right;
	int val=0;

	// The constructor takes a value, left and right pointers,
	// all of them are optional
	Node(int v=0, Node *l=nullptr, Node *r=nullptr) :
	    left(l), right(r), val(v)
	{}
	    
    };

    // The only data member of the tree itself is the root pointer
    Node * root=nullptr;

    // The main insert method.
    void insert(int val)
    {
	// Create a new node and call the recursive insert method
	insert(root, new Node(val));
    }

private:    

    // Here is the recursive insert method. It takes a REFERENCE to
    // a Node ptr where the node should be inserted.
    // If that ptr is null then insert there, otherwise insert in one
    // of its children.
    void insert(Node *& ptr, Node *newNode)
    {
	if (ptr == nullptr) {
	    ptr = newNode;
	} else if (newNode->val < ptr->val) {
	    insert(ptr->left, newNode);
	} else {
	    insert(ptr->right, newNode);
	}
    }
};


kretze (17)
hey does anoyone know a good(great) book aoubt data structures and that stuff?? because im doing the same program that i do in my first post here but in the first post i do with one class and now i do with class within class and i dont know how to do(abviusly)....beaside that i have just one question...how do you initialize two classes?? 

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
 
#include <iostream>   
#include <stdlib.h> 
#include <string> 
using namespace std;



class tree
{
	class Node
	{
	public:
		Node *left;
		Node *right;
		int val;

		Node()
		{
			val = 0;
		}

		Node(Node *l, Node*r, int v)
		{
			left = l;
			right = r;
			val = v;
		}
	};


	Node *root = nullptr;


private:
	tree(tree *l,tree *r,int v):Node()
	{
	

		
	}
	
	

:
	void insert(Node *&newNode, Node *newPtr)
	{
		if (newNode == nullptr)
			newNode = newPtr;
		else if (newNode->val < newPtr->val)
			insert(newNode->left, newPtr);
		else
			insert(newNode->right, newPtr);
	}


	void InsertNood(int num)
	{
		Node *newNode = nullptr;
		newNode = new Node;
		newNode->val = num;
		newNode->left = newNode->right = nullptr;

		insert(root, newNode);
	}

	void displayInORder()const
	{
		Node *newnode = nullptr;
		newnode = new Node;

		if (left)
			left->displayInORder();

		
		


	

	}
};
dhayden (5798)
how do you initialize two classes?

You don't have to. Tree::Node is just the name of a class. When you create a Tree object, it does not create a Node object also. This is the difference between declaring a class within a class, and have one class (tree) derive from another. If tree derived from Node then each instance of tree would basically contain an instance of Node within it. That instance would have to be initialized.

A tree does not have a value, or a left or right pointer. The only data in a tree is the root pointer.
kretze (17)
so what i have to do to initialize?? i google it and i did not find a proper solution
Thomas1965 (4571)
There is not much to initialize
Start with an empty tree.
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
 
class Tree
{
  struct Node
  {
    Node *left;
    Node *right;
    int val;

    Node()
    {
      val = 0;
      left = right = nullptr;
    }

    Node(int v)
    {
      val = v;
      left = right = nullptr;
    }
  };
  Node *root = nullptr;
  // maybe add a var for count of nodes

  Tree()
  {
    // nothing to do - start with empty tree
  }
  ~Tree()
  {
     // delete all Nodes
  }

  void insert(Node *&newNode, Node *newPtr)
  {
    if (newNode == nullptr)
      newNode = newPtr;
    else if (newNode->val < newPtr->val)
      insert(newNode->left, newPtr);
    else
      insert(newNode->right, newPtr);
  }


  void InsertNood(int num)
  {
    Node *newNode = nullptr;
    newNode = new Node;
    newNode->val = num;
    newNode->left = newNode->right = nullptr;

    insert(root, newNode);
  }

  void displayInORder()const
  {
    // add your logic here
  }
};


BTW. What do you need a tree for?
The STL has map classes that are based on binary trees, why don't you have a look at them?
Last edited on
kretze (17)
any help please :) https://www.file.si/public/viewset/4064 (i dont know how input picture so i gave i link)

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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 


#include <iostream>   
#include <stdlib.h> 
#include <string> 
using namespace std;

class tree
{
private:
	struct Node
	{
		Node *left;
		Node *right;
		int val;

		Node()
		{
			val = 0;
			left = right = nullptr;
		}

		Node(int v)
		{
			left = right = nullptr;
			val = v;
		}
	};



	Node *root ;


public:
	tree()
	{
		root = nullptr;
	}
	
	void insert(Node *&newnode, Node *nePtr)
	{
		if (newnode == nullptr)
			newnode = nePtr;
		else if (newnode->val < nePtr->val)
			insert(newnode->left, nePtr);
		else
			insert(newnode->right, nePtr);
	}

	void InsertNood(int num)
	{
		Node *newnode = nullptr;
		newnode = new Node;

		newnode->val = num;
		newnode->left = newnode->right = nullptr;

		insert(root, newnode);

	}

	void displayInORde(Node *newNode)const
	{
		if (newNode)
		{
			displayInORde(newNode->left);
			cout << newNode->val<<endl;
			displayInORde(newNode->right);

		}

		
	}

	void displayInORde()const
	{
		if (root)
		{
			displayInORde(root);
		}
	}


	void displayPreeOrder(Node *newnode)const
	{
		if (newnode)
		{
			cout << newnode->val << endl;
			displayPreeOrder(newnode->left);
			displayPreeOrder(newnode->right);
		}
	}

	void displayPreeOrder()const
	{
		if (root)
		{
			displayPreeOrder(root);
		}
	}

	void displayPostOrder(Node *newnode)const
	{
		if (newnode)
		{
			displayPostOrder(newnode->left);
			displayPostOrder(newnode->right);
			cout << newnode->val << endl;
		}
	}


	void displayPostOrder()const
	{
		if (root)
		{
			displayPostOrder(root);
		}
	}


	bool searcNode(int num)
	{
		Node *newNode = root;

		while (newNode)
		{
			if (newNode->val == num)
				return true;
			else if (num < newNode->val)
				newNode = newNode->left;
			else
				newNode = newNode->right;


		}
		return false;
	}



	void makeDeletion(Node *newnode)
	{
		Node *tempNode = nullptr;
		if (newnode == nullptr)
			cout << "cannot delete empty node " << endl;
		else if (newnode->right == nullptr)
		{
			tempNode = newnode;
			newnode = newnode->left;
			delete tempNode;
		}

		else if (newnode->left == nullptr)
		{
			tempNode = newnode;
			newnode = newnode->right;
			delete tempNode;
		}
		else
		{
			tempNode = newnode->right;
			while (tempNode->left)
				tempNode = tempNode->left;
			tempNode->left = newnode->left;
			tempNode = newnode;
			newnode = newnode->right;
			delete tempNode;
		}


		
	}

	void deleteNode(int num,Node *&newnode)
	{
		if (num < newnode->val)
			deleteNode(num, newnode->left);
		else if (num > newnode->val)
			deleteNode(num, newnode->right);
		else
			makeDeletion(newnode);


	}
	void remove(int num)
	{
		deleteNode(num, root);

	}

};


int main() {


	tree t;
	cout << "inserting nodes ";
	t.InsertNood(5);
	t.InsertNood(4);
	t.InsertNood(13);
	t.InsertNood(1);
	t.InsertNood(21);

	cout << "numbers in order are " << endl;
	t.displayInORde();

	cout << endl;

	cout << "numbers in pre-order are " << endl;
	t.displayPreeOrder();

	cout << endl;

	cout << "numbers in post-order are " << endl;
	t.displayPostOrder();
	cout << endl;
	cout << endl;


	if (t.searcNode(1))
		cout << "1 was found in the tree " << endl;
	else
		cout << "1 was not found on the tree!!!" << endl;

	if (t.searcNode(73))
		cout << "73 was found in the tree" << endl;
	else
		cout << "73 was not found in the tree " << endl;


	cout << endl;
	cout << endl;

	cout << "here are values on tree " << endl;
	t.displayInORde();

	cout << "deletin 1.....\n";
	t.remove(1);

	cout << "deleting 21.......\n";
	t.remove(21);

	cout << "now here are the nodes\n";
	t.displayInORde();

	
	system("pause");// 
	return 0;
}

dhayden (5798)
Line 45: < should be >
Line 143: Since you want to change the value of newnode that was passed in,
you have to pass newNode by reference: void makeDeletion(Node * &newnode)
kretze (17)
you mean like that??
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
 
void insert(Node *&newnode, Node *nePtr)
	{
		if (newnode == nullptr)
			newnode = nePtr;
		else if (newnode->val < nePtr->val)
			insert(newnode->left, nePtr);
		else {
			insert(newnode->right, nePtr);
		}
	}



void makeDeletion(Node *&newnode)
	{
		Node *tempNode = nullptr;
		if (newnode == nullptr)
			cout << "cannot delete empty node " << endl;
		else if (newnode->right == nullptr)
		{
			tempNode = newnode;
			newnode = newnode->left;
			delete tempNode;
		}

		else if (newnode->left == nullptr)
		{
			tempNode = newnode;
			newnode = newnode->right;
			delete tempNode;
		}
		else
		{
			tempNode = newnode->right;
			while (tempNode->left)
				tempNode = tempNode->left;
			tempNode->left = newnode->left;
			tempNode = newnode;
			newnode = newnode->right;
			delete tempNode;
		}


		
	}
dhayden (5798)
Yes, except, as I wrote before, < should be > (in the insert() method)
Topic archived. No new replies allowed.