binary tree c++

Question

The program compiles, but when I run it it crashes when it tries to output
what is wrong
//-------------------------- Node.h
class Node
{
public:
Node* _RHand ;
Node* _LHand;
Node* _head;
int data ;
Node()=delete ;
Node (int input_data);
void insert_Node(int data , Node* Ihead = nullptr);
void get_min();

};
//--------------------Node.cpp
#include "node.h"
#include <iostream>
using std::cout;
Node::Node(int input_data)
{
this->data = input_data ;
this->_head = this ;
this->_LHand = nullptr ;
this->_RHand = nullptr ;
}
void Node::insert_Node(int data , Node* Ihead ){

if (Ihead == nullptr ) Ihead = this->_head ;
if (Ihead->data >data){
if (Ihead->_LHand == nullptr){

Node* tem = new Node (data) ;
Ihead ->_LHand = tem ;
delete tem ;
}else{

insert_Node(data, Ihead->_LHand);

}
}else {
if (Ihead->_RHand == nullptr){

Node* tem = new Node (data) ;
Ihead ->_RHand = tem ;
delete tem ;

}else {

insert_Node(data, Ihead->_RHand);

}
}

}
void Node::get_min(){

Node* tem = _head;

while (tem->_LHand !=nullptr) {
cout<< tem->data ;
tem =tem->_LHand ;
}

}
//------------main

#include "node.h"

int main()
{
Node* start = new Node (32);
start ->insert_Node(23);
start ->insert_Node(15);
start ->insert_Node(13);
start ->insert_Node(3);
start ->insert_Node(2);
start->get_min();

}
//---------------------output
Binary crashed.

Answer 1

It is the destructor's job to delete everything inside the binary tree when the tree goes out of scope.
However, because your Node is allocated on the heap, the destructor is not called when it goes out of scope, only when you call delete on it yourself.

Your options:
1. Call delete yourself when it goes out of scope. Not recommended.

2. Learn about smart pointers, which handle it for you.

3. Make a class like I showed you so you can implement a destructor and because binaryTree is allocated on the stack the destructor will be called when it goes out of scope.

4. Combine 2 and 3 to protect yourself better against exceptions.

Anything allocated inside your insert_node function is simply given to the node and then used later, you don't want to delete it right away.

Answer 2

Lets pick the following snipped:

Node* tem = new Node(data);
Ihead->_LHand = tem;
delete tem;

See the problem yet?

1st line: tem gets assigned an address
2nd line: then _LHand points to the SAME address.
3rd line: the address gets deallocated

So _LHand now ends up with a dangling pointer

Dito voor _RHand

So, removing delete tem; at both location should fix the crash.

Secondly I don't really recommend making a binary tree like this.

1. In your implementation every node has a head, which doesn't make sense.

2. Node should not be in global scope, what if you want to implement a linked list for example which also uses a node but has a different implementation?

3. This node only accepts ints, templates would be a nice improvement.

What you could do is nest the Node inside a BinaryTree class like this:

template<typename T> //Or template<class T>, whatever you want
class BinaryTree
{
public:
//...

private:
struct Node
{
Node* left = nullptr;
Node* right = nullptr;
T data;
};

private:
Node* mRoot = nullptr;
};

int main()
{
BinaryTree<int> binaryTree;
}

Feel free to ask questions if you don't understand something ^^.

Answer 3

thank you a lot, so how to avoid memory leaks in the program?
:)