0

I am trying to finish a C++ project where I have to insert an array of integers into a binary search tree. I have to use a particular insertion algorithm:

insert(T, z)
1  y = NIL
2  x = T.root
3  while x != NIL
4      y = x
5      if z.key < x.key
6          x = x.left
7      else x = x.right
8  z.p = y
9  if y == NIL
10     T.root = z
11 else if z.key < y.key
12     y.left = z
13 else y.right = z

Here is my code so far:

main.cpp

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

using namespace std;

int main()
{
    BinaryTree tree;
    int array [10] = {30, 10, 45, 38, 20, 50, 25, 33, 8, 12};

    for (int i = 0; i < 10; i++)
    {
        tree.add(array[i]);
    }

    tree.inordertreewalk();
    return 0;
}

void BinaryTree::insert(node *&T, node *&z)
{

    node *y = nullptr;
    y = new node;
    y->key = 0;
    y->left = y->right = y->parent = nullptr;

    node *x = T;
    while (x != nullptr)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if (y == nullptr)
        T = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
}

void BinaryTree::add(int num)
{
    node *newNode = nullptr;
    newNode = new node;
    newNode->left = newNode->right = newNode->parent = nullptr;
    newNode->key=num;
    insert(root, newNode);
}

void BinaryTree::inordertreewalk(node *x) const
{
    if (x)
    {
        inordertreewalk(x->left);
        cout << x->key << endl;
        inordertreewalk(x->right);
    }
}

void BinaryTree::destroysubtree(node *newNode)
{
    if (newNode)
    {
        if (newNode->left)
            destroysubtree(newNode->left);
        if (newNode->right)
            destroysubtree(newNode->right);
        delete newNode;
    }
}


binarytree.h

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include <iostream>
using namespace std;

class BinaryTree
{

    private:
        struct node
        {
            int key;
            node* left;
            node* right;
            node* parent;
        };

        node *root;

        void insert(node *&, node *&);
        void inordertreewalk(node *) const;
        void destroysubtree(node *);

    public:
        BinaryTree()
            { root = nullptr; }
        ~BinaryTree()
            { destroysubtree(root); }
        void add(int);
        void inordertreewalk() const
            { inordertreewalk(root); }
};

#endif

This program compiles, however it is not displaying the tree. I know that the problem is with my implementation of the insertion algorithm because I used a different algorithm I found in a textbook and kept the rest of the code the same and the tree was displayed in order. I know that T is a pointer to the root, but I'm not sure if the numbers are being correctly stored in the tree. Thanks for your help.

tfreiner
  • 209
  • 2
  • 13
  • So did you step through the code with a debugger? Better yet, instead of taking an algorithm and immediately attempt to rewrite it in C++, did you step through the algorithm by hand, using pencil and paper to see what is being done? And if you did, when you rewrote the steps in C++, did you (again asking) step through the code using the debugger to see where the program goes against what you did by hand? – PaulMcKenzie Apr 22 '16 at 00:18
  • 1
    Also, why you are creating (`new`-ing) two nodes when you want to insert a single node? In your `add` function you create a node, which calls `insert` which creates another node. That right there is an indication that something is amiss. I don't think you're building the tree correctly, let alone not be able to print. – PaulMcKenzie Apr 22 '16 at 00:22
  • Yes I've been using the debugger, one thing I tested was adding the line 'inordertreewalk(z)' at the end of the insert function which displays each number of the array in the original order as expected. I'm creating a new node in my add function so that I can store the number in the key field and that node is being passed as z in the insert function. – tfreiner Apr 22 '16 at 00:29
  • 2
    Your `insert` function fails the first time it is called. That should be enough of a clue; if we give you a more detailed explanation, you will not learn to look at your own code. – Beta Apr 22 '16 at 00:29
  • 1
    Look closely at what Paul has told you, and you'll fix your program. – Millie Smith Apr 22 '16 at 00:31
  • Ah got it. I removed the 2nd, 3rd, and 4th lines in the insert function and now its flawless. Thanks guys! – tfreiner Apr 22 '16 at 00:39
  • another comment `int *&x` is meaningless. you might as well say `int x` but the code will work anyway. If you meant to send the value by reference then `int *x` is what you are looking for and you put `&` next to the parameter when calling the function unless it is already a pointer. – Tarek Apr 22 '16 at 00:44
  • @Tarek `int *&x` is a reference to a pointer, it's not meaningless. – ffao Apr 22 '16 at 02:08
  • A reference to a pointer is the value itself with or without it the code will do exactly the same thing (with proper changes of `->` to `.`where necessary). the OP is using pointers where it is not necessary to do so. Please look at the example here: `char *str1 = "Hello "; char *str2 = "World!"; char *ptr = str1; char *&rptr = str1; rptr = str2; cout << ptr << str1 << endl;` will print "Hello World!" `rptr=str2` did exactly the same effect as saying `str1=str2` you are just accessing it differently http://stackoverflow.com/questions/3128662/reference-to-a-pointer – Tarek Apr 22 '16 at 03:20
  • just to note, I am not advocating to use int x instead cuz obviously that wont work, i am suggesting that a simple pointer is enough as per my original comment, a pointer to a reference is just not worth it. – Tarek Apr 22 '16 at 03:30

0 Answers0