[IceHot]

Hello world! I am planning on updating my program that renames files named like : homework+essay.docx to homework essay.docx. (My code already works if the file is directly in Downloads, Desktop, or Documents folders.) In order for this program to be of full use, it needs to search the subdirectories. To do that, I am going to have to make a (non-binary) tree. To do that, I need to understand implementation of trees in general, so I am having myself make, and print, a binary search tree; I have not taken a course in data structures. I have my tree made, but I cannot seem to print any of it. Here is my full code:

#include <iostream>
#include <typeinfo>
#include <math.h>

using namespace std;

struct node
{
    int element;
    node * leftnode;
    node * rightnode;
};   //end struct

void createtree(int n, node * a, int max)
{
    if (n < max)
    {
        if (n == 0)
        {
            a->element = pow(2,max-1);
            //cout << "parent node's element == "<<a->element<<endl;
            createtree(1,a,max);
        }   //end if
        else
        {
            a->leftnode = new(nothrow) node;
            a->rightnode = new(nothrow) node;
            node * l = a->leftnode;
            node * r = a->rightnode;
            l->element = a->element-pow(2,max-(n+1));
            r->element = a->element+pow(2,max-(n+1));
            //cout << "the element for the leftnode of level "<<n<<" is "<<l->element<<endl;
            //cout << "the element for the rightnode of level "<<n<<" is "<<r->element<<endl;
            if (n < max-1)
            {
                createtree(n+1,l,max);
                createtree(n+1,r,max);
            }   //end inner if
        }   //end else
    }   //end if
}   //end createtree

void inorder(node * a)
{
    //Remember, this should print the first child, then the parent, and then the other child.
    //To do this, it must go to the lowest level first.
    //After that, access the parent node
    //Finally, go to the childnode.

    //First, make the necessary declarations...
    node * templeft = a->leftnode;
    node * tempright = a->rightnode;
    //if the pointer is not null
    if (a != 0)
    {
        inorder(templeft);
        //inorder(a->leftnode);
        cout << a->element << endl;
        //inorder(a->rightnode);
        inorder(tempright);
    }   //end if
}   //end inorder

int main()
{
    int x;
    cout << "Enter the number of levels of nodes (include parent node): ";
    cin >> x;
    node * t;
    t = new(nothrow)node;
    createtree(0,t,x);
    inorder(t);
    //This is test code; I did this to test my idea out before the implementation took place.
    node b;
    b.element = 32;
    b.leftnode = new(nothrow) node;
    b.rightnode = new(nothrow) node;
    node * l = b.leftnode;
    node * r = b.rightnode;
    l->element = 16;
    r->element = 48;
    cout << "l->element == " << l->element << endl;
    cout << "r->element == " << r->element << endl;
    return 0;
}

(Sorry for all the comments.)
It is throwing a segmentation fault on the

node * templeft = a->leftnode;

statement. Even if I forgo the use of temporary pointers (and just use a->leftnode, a->rightnode directly), it throws a segmentation fault on the

inorder(a->leftnode);

statement. I have no idea why this is; I would think that it would be because the compiler doesn't know what a->leftnode, a->rightnode are, but I might be wrong. Remember that inorder(tree * a) is supposed to be PRINTING THE BINARY TREE via in-order traversal. I couldn't just use leftnode,rightnode = new(nothrow)node tree. I am out of ideas; can anyone help?

This post has been edited by IceHot: 26 December 2012 - 09:15 AM

[vividexstance]

Using your inorder(node *a) function as an example:

void inorder(node * a)
{
    //Remember, this should print the first child, then the parent, and then the other child.
    //To do this, it must go to the lowest level first.
    //After that, access the parent node
    //Finally, go to the childnode.

    //First, make the necessary declarations...
    node * templeft = a->leftnode;
    node * tempright = a->rightnode;
    //if the pointer is not null
    if (a != 0)
    {
        inorder(templeft);
        //inorder(a->leftnode);
        cout << a->element << endl;
        //inorder(a->rightnode);
        inorder(tempright);
    }   //end if
}   //end inorder

What happens when the function is passed a NULL value? Without checking for NULL (0) first, you attempt to access the left and right child nodes.

This post has been edited by vividexstance: 26 December 2012 - 10:11 AM

[IceHot]

vividexstance, on 26 December 2012 - 10:11 AM, said:

Using your inorder(node *a) function as an example:

void inorder(node * a)
{
    //Remember, this should print the first child, then the parent, and then the other child.
    //To do this, it must go to the lowest level first.
    //After that, access the parent node
    //Finally, go to the childnode.

    //First, make the necessary declarations...
    node * templeft = a->leftnode;
    node * tempright = a->rightnode;
    //if the pointer is not null
    if (a != 0)
    {
        inorder(templeft);
        //inorder(a->leftnode);
        cout << a->element << endl;
        //inorder(a->rightnode);
        inorder(tempright);
    }   //end if
}   //end inorder

What happens when the function is passed a NULL value? Without checking for NULL (0) first, you attempt to access the left and right child nodes.

So the

if (a != 0)

doesn't cut it? From what I understand, a is a pointer. Maybe what you are saying is that I should use the macro NULL instead of 0?

This post has been edited by IceHot: 26 December 2012 - 11:04 AM

[mojo666]

The statement that is throwing the exception is before the

if(a!=0)

The "if" needs to be the first thing you do.
Basically, if a pointer is NULL, it is not pointing to anything. The segfault is the compiler's way of saying "I can't go to a's leftnode because there is nothing at a".

This post has been edited by mojo666: 26 December 2012 - 11:15 AM

[vividexstance]

IceHot, on 26 December 2012 - 01:02 PM, said:

So the

if (a != 0)

doesn't cut it? From what I understand, a is a pointer. Maybe what you are saying is that I should use the macro NULL instead of 0?

No, that's not at all what I said. I was saying that the check to see if a is 0 (NULL is basically 0, so either one is fine) should be the first thing you do in the function. Do you really need those extra node pointers? That's where the problem is, there could be more elsewhere in the program, this was just the first problem I saw. The code could be simplified:

if(a != NULL)
{
    inorder(a->leftNode);
    cout << a->element;
    inorder(a->rightNode);
}

Do you see how you were using 'a' before you checked if it was 0 when you initialized those two extra node pointers (that you really don't need)?

This post has been edited by vividexstance: 26 December 2012 - 11:20 AM

[IceHot]

It still crashes.
Here is optimized code (as per your suggestion):

void inorder(node * a)
{
    //Remember, this should print the first child, then the parent, and then the other child.
    //To do this, it must go to the lowest level first.
    //After that, access the parent node
    //Finally, go to the childnode.
    //if the pointer is not null
    if (a != 0)
    {
        inorder(a->leftnode);
        cout << a->element << endl;
        inorder(a->rightnode);
    }   //end if
}   //end inorder

Could the heap be causing the problem? The compiler still points to

inorder(a->leftnode);

as the problem.

This post has been edited by IceHot: 26 December 2012 - 01:50 PM

[vividexstance]

Can you post a small working program with your code because I just took your original code and then made the change I suggested and it doesn't segfault for me.

This post has been edited by vividexstance: 26 December 2012 - 01:57 PM

[IceHot]

#include <iostream>
#include <typeinfo>
#include <math.h>

using namespace std;

struct node
{
    int element;
    node * leftnode;
    node * rightnode;
};   //end struct

void createtree(int n, node * a, int max)
{
    if (n < max)
    {
        if (n == 0)
        {
            a->element = pow(2,max-1);
            //cout << "parent node's element == "<<a->element<<endl;
            createtree(1,a,max);
        }   //end if
        else
        {
            a->leftnode = new(nothrow) node;
            a->rightnode = new(nothrow) node;
            node * l = a->leftnode;
            node * r = a->rightnode;
            l->element = a->element-pow(2,max-(n+1));
            r->element = a->element+pow(2,max-(n+1));
            //cout << "the element for the leftnode of level "<<n<<" is "<<l->element<<endl;
            //cout << "the element for the rightnode of level "<<n<<" is "<<r->element<<endl;
            if (n < max-1)
            {
                createtree(n+1,l,max);
                createtree(n+1,r,max);
            }   //end inner if
        }   //end else
    }   //end if
}   //end createtree

int main()
{
    int x;
    cout << "Enter the number of levels of nodes (include parent node): ";
    cin >> x;
    node * t;
    t = new(nothrow)node;
    createtree(0,t,x);
    return 0;
}

The same one, without the cout statements, the test code, or the inorder().

[IceHot]

Is there any chance you could screencap the output of my program (the original one with the modifications to inorder())?

EDIT: The program only seems to crash when it is trying to access the leftnode's

This post has been edited by IceHot: 27 December 2012 - 05:27 AM

[vividexstance]

Post your inorder function as well please. Here is the output I got:

Quote

Enter the number of levels of nodes (include parent node): 5
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
l->element == 16
r->element == 48

[IceHot]

void inorder(node * a)
{
    //Remember, this should print the first child, then the parent, and then the other child.
    //To do this, it must go to the lowest level first.
    //After that, access the parent node
    //Finally, go to the childnode.
    //if the pointer is not null
    if (a != 0)
    {
        inorder(a->leftnode);
        cout << a->element << endl;
        inorder(a->rightnode);
    }   //end if
}   //end inorder

[mojo666]

I think this is a compiler issue. It is not guaranteed that the nodes in the structure default to null, so you may have to do it manually. Try setting the nodes to 0 whenever you make a new node. For example

a->leftnode = new(nothrow) node;  
a->rightnode = new(nothrow) node;  
node * l = a->leftnode;  
node * r = a->rightnode;  
l->element = a->element-pow(2,max-(n+1));  
r->element = a->element+pow(2,max-(n+1));  

//default pointers to null
l->leftnode=0;
l->rightnode=0;
r->leftnode=0;
r->rightnode=0;

You could also look into using constructors.

[vividexstance]

Or since you're using C++ you could just write a default constructor for the node struct that set's the left/right pointers to NULL.

struct node
{
    int element;
    node * leftnode;
    node * rightnode;
    
    node(int i, node* l = NULL, node* r = NULL)
        : element(i), leftnode(l), rightnode(r) {}
};   //end struct

[IceHot]

It worked! Thanks, mojo666! That means that whenever it comes time for the non-binary tree, I might have to make its own class and use inheritance. That or do what you told me. Oh, and vividexstance, I didn't know that structs could have constructors.

This post has been edited by IceHot: 27 December 2012 - 11:35 AM

[vividexstance]

IceHot, on 27 December 2012 - 01:27 PM, said:

Oh, and vividexstance, I didn't know that structs could have constructors.

The only difference between a struct and class in C++ is the default access level. For structs, the default access level is public, for classes it is private. That is why in classes you have to put the public: line in the class' definition so you can make some of the member functions (especially the constructors/destructor) accessible to the user of the struct or class. Basically:

struct s
{
    // ...
};

is the same as:

class c
{
public:
    // ...
};

*EDIT*: One could also say that this:

struct s
{
private:
    // ...
};

is equivalent to:

class c
{
    // ...
};

This post has been edited by vividexstance: 27 December 2012 - 12:16 PM