Troubled with this binary tree code (in c++)?

Question

This is the code I am writing for insertion and inorder traversal of a binary tree. However I am kind of messed up now. Could you please help me in correcting this? The while loop in the insert-code is not getting anything getting inside into it. Thanks for your help.

#include<iostream>
#include<string>
using namespace std;

class binarynode
{public:
string data;
binarynode *left;
binarynode *right;  
};

class tree
{
binarynode *root;
public:
    tree()
    {
        root=new binarynode;
        root=NULL;
    }
    binarynode* createnode(string value)
    {
        binarynode * temp;
        temp=new binarynode;
        temp->data=value;   
        temp->left=NULL;
        temp->right=NULL;
        return temp;
    }
    void insert(string value)
    {//cout<<"entered 1"<<endl;
        binarynode * nroot;
        nroot=root;

        while(nroot!=NULL)
        {//cout<<"here 2"<<endl;
        if(value> nroot->data )
        {
        //  cout<<"here 3"<<endl;
            nroot=nroot->right;
        }
        else
        if(value<nroot->data)
        {//cout<<"here 4"<<endl;
            nroot=nroot->left;
        }
        }
        nroot=createnode(value);
    }
    void inorder()
    {
        binarynode *nroot;
        nroot=root;
        printinorder(nroot);
    }
    void printinorder(binarynode * nroot)
    {
    //cout<<"entered 5"<<endl;
        if(nroot->left==NULL&&nroot->right==NULL)
        {
            cout<<nroot->data<<" ";
        }
            printinorder(nroot->left);
    cout<<nroot->data<<" ";
    printinorder(nroot->right);
    }
};

int main()
{
    tree a;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string value;
        cin>>value;
        a.insert(value);
    }
    a.inorder();
}

score 2 · Answer 1 · answered Jun 21 '15 at 15:39

2

You are assigning NULL to root in the constructor:

root = NULL;

so your while loop will never be entered.

answered Jun 21 '15 at 15:39

albertoqa

525
3
11

What you are telling is wrong. Root has to be null. The problem is with the pointers. I really wonder how you got so many upvotes! – MAD CODER Jun 22 '15 at 08:01

ssemilla · Answer 2 · 2015-06-22T08:17:41.457

1

Note that nroot=createnode(value); won't append a node to the tree. You can use double pointers for this.

Edit: as requested by yeldar

  void insert(const std::string& value) {

    binarynode **node = &root;

    while (*node) {
      if (value >= (*node)->data) {
        node=&(*node)->right;
      } else {
        node=&(*node)->left;
      }
    }

    *node=createnode(value);
  }

Edit: not using double pointers

  void insert(const std::string& value) {

    if (root == NULL) {
      root = createnode(value);
      return;
    }

    binarynode *node = root;
    binarynode *parent = NULL;

    while (node) {
      parent = node; // we should store the parent node                                                                                                        
      node = value >= parent->data ? parent->right : parent->left;
    }

    if (value >= parent->data) {
      parent->right = createnode(value);
    } else {
      parent->left = createnode(value);
    }

  }

edited Jun 22 '15 at 08:17

answered Jun 21 '15 at 16:14

ssemilla

3,900
12
28

so how should I edit this if I don't want any double pointers? – MAD CODER Jun 21 '15 at 16:38
This will give you a hint: ` binarynode **node = &root; while (*node) { if (value >= (*node)->data) { node=&(*node)->right; } else { node=&(*node)->left; } } *node=createnode(value); ` – ssemilla Jun 21 '15 at 16:52
@weavr Please, edit your answer and place the code there. It will help other people who meets this problem. – Yeldar Kurmangaliyev Jun 22 '15 at 04:16
Actually you can, but the code will be not be as terse. – ssemilla Jun 22 '15 at 08:05
As you can see from the sample code above, we need to store the parent node before the actual node pointer becomes NULL. – ssemilla Jun 22 '15 at 08:19
Thank you for the edits. However, I am confused between when to use single pointer, pointer to pointer and reference to pointer. Please help me in understanding that. – MAD CODER Jun 23 '15 at 11:00
The way I look at pointers is that they are values like an int or a char. Let's say you have two integers `int x = 2; int y = 3;` a pointer `int *a = &x;` and another pointer `int *b = a;`. Now if I change `b = &y;` the value of `a` is still `&x`. In the original code you sent, `node` is `NULL` at the end of the loop. Now if you say `node = someValue;`, you are not changing anything else other than the value of `node`. You can look at [here](http://stackoverflow.com/a/5580790/5033611) for a better explanation – ssemilla Jun 23 '15 at 14:53

Troubled with this binary tree code (in c++)?

2 Answers2