Binary Tree implementation C++

Question

Binary Tree insertion:

#include "stdafx.h"
#include <iostream>

using namespace std;

struct TreeNode {
  int value;
  TreeNode* left;
  TreeNode* right;
};

struct TreeType {
  TreeNode* root;

  void insert(TreeNode* tree, int item);

  void insertItem(int value) {
    insert(root, value);
  }
};

void TreeType::insert(TreeNode* tree, int number) {
  if (tree == NULL) {
    tree = new TreeNode;
    tree->left = NULL;
    tree->right = NULL;
    tree->value = number;
    cout << "DONE";
  } else if (number < tree->value) {
    insert(tree->left, number);
  } else {
    insert(tree->right, number);
  }
}

int main() {
  TreeType* MyTree = new TreeType;
  MyTree->insertItem(8);

  return 0;
}

I am currently learning Data structures in C++ and this is the code that make insertion in binary trees.

After it is compiled, everything looks fine, however when i try to execute this program, it crashed.

Can anybody tell me where I am wrong?

Have you tried using debugger and/or valgrind?

Erbureth
– Erbureth

2013-12-07 18:02:27 +00:00
Commented Dec 7, 2013 at 18:02 — Erbureth
– Erbureth, Commented Dec 7, 2013 at 18:02

Homer6 · Accepted Answer · 2020-11-12 01:24:18Z

In your tree constructor, you need to initialize the root pointer to NULL. It's not guaranteed to be initialized as NULL.

When you compile in linux, you can use gdb to show where the source of the segfault is coming from.

Some other notes:

You should assign the value back to root after you've allocated the new node. You're not doing that because you're missing one of the fundamentals of c++. That is, it's based on c. And the thing about c is that is strictly a "by-value" function/method calling paradigm. So all parameters in a function call are by value. When you pass in the memory address for root, you're actually copying the value of the pointer. Then, you're only updating the local value. You need to assign it back to root. If you'd like to learn that concept front to back, I highly recommend watching Jerry Cain's Programming Paradigms course at Stanford.
In your main function, you should try to keep the symbol names as lower_case instead of CamelCase. This helps differentiate variables from types (types should stay CamelCase).
In your TreeType::insert method, you should call the variable tree_node instead of tree. Doing so helps reflect the correct type and avoids confusion.
Whenever possible, try you use the this->root and this->insert notation. Not only will it correctly resolve if you accidentally create a locally scoped root variable, but it's also clearer to the reader where the data or method is defined. Great coding is about communication. It may only take 100-500ms less for the reader to understand where the symbol points to; however, the tiny savings that you can accumulate in avoiding ambiguities add up into a much clearer piece of software. Your future self (and your colleagues) will thank you. See http://msmvps.com/blogs/jon_skeet/archive/2013/09/21/career-and-skills-advice.aspx

Lastly, I can't overstate enough how important learning from the source is. If you're learning c or c++ for the first time, read http://www.amazon.com/The-Programming-Language-4th-Edition/dp/0321563840 and http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628. It will save you hours, upon hours, upon hours. After having learned from the source, programming is also A LOT more enjoyable because you understand a good portion of the concepts. And, the truth is, things are more fun when you have a decent level of competence in them.

Mike Minaev · Accepted Answer · 2015-02-25 14:26:40Z

8

Try something like this-

 struct Node {
    int Data;
    Node* Left;
    Node* Right; 
};

Node* Find( Node* node, int value )
{
    if( node == NULL )
        return NULL;
    if( node->Data == value )
        return node;
    if( node->Data > value )
        return Find( node->Left, value );
    else
        return Find( node->Right, value );
};

void Insert( Node* node, int value )
{
    if( node == NULL ) {
        node = new Node( value );
        return;
    }
    if( node->Data > value )
        Insert( node->Left, value );
    else
        Insert( node->Right, value );
};

edited Feb 25, 2015 at 14:26

answered Dec 7, 2013 at 18:02

Mike Minaev

2,1224 gold badges25 silver badges33 bronze badges

1 Comment

albin Over a year ago

You should use 'void Insert(Node** node, int value)', otherwise you cannot create root node...

Abhishek Bansal · Accepted Answer · 2013-12-07 17:58:38Z

1

In your TreeType constructor I think you should explicitly make root point to NULL.

TreeType::TreeType() {
  root = NULL;
}

answered Dec 7, 2013 at 17:58

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

Collectives™ on Stack Overflow

Binary Tree implementation C++

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related