Binary search tree

Before I head into one-upping my program that renames .docx files that have a '+' in the name (it works in three directories), I figured that the right approach would be tree-implementation. However, I have never taken the class that was recommended to be taken along with second semester computing class, data structures. As a consequence, I have to teach myself the stuff that I would need to know. To do this, I am trying to implement a binary search tree (a project that is ubiquitous amongst novice programmers, I know). I have decided that it should take user input about how many levels there should be total, and then create a binary search tree with that many levels starting with 1 being the leftmost leaf node. (That means that for a tree of x levels, you are looking at a parent node of 2^(x-1), a rightmost leaf node of 2^(x+1)-1 == 2^x+1, and the change j units from the top to be 2^(x-(j+1)). Here is my code so far: its complaints are based on me trying to either declare or directly call the struct's lefttree and righttree)
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
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

struct tree
{
    int element;
    tree * lefttree;
    tree * righttree;
};   //end struct
tree a;
lefttree b;
righttree c;

void createtree(int max)
{
    for (int n = 0; n < max; n++)
    {
        if (n == 0)
        {
            a.element = 2^(n-1);
        }   //end if
        else
        {
            b.element = (&b).element - 2^(max - (n+1));
            c.element = (&c).element + 2^(max - (n+1));
        }   //end else if
    }   //end for
}   //end createtree

int main()
{
    int x;
    cout << "Enter the number of levels of nodes (include parent node): " << endl;
    cin >> x;
    createtree(x);
    return 0;
}
lefttree is not a type, it's a variable member of tree. So far, you've created one tree (a), so you have to refer to the members of a

1
2
a.lefttree = ... 
...
So,
1
2
b = a.lefttree;
c = a.righttree;

, but then b and c would have to be of type tree?
EDIT: This doesn't solve anything right now, but I forgot to put a.element = 2^(max-1) instead of a.element = 2^(n-1) in the if-statement
Last edited on
sorry to say that: you are completely on the wrong track.

take a look at this:

http://en.wikipedia.org/wiki/Binary_search_tree

the symbol ^ isn't power it's exclusive or

See

http://en.wikipedia.org/wiki/C_operators
http://en.wikipedia.org/wiki/Bitwise_operation#XOR
if you create the structure of node
you should have something like this

1
2
3
4
5
6
7
8
9
10
11
struct Node{
     int info;
     Node* left;
     Node* right;
};

class TreeNode{
private:
     Node* Tree;
  //...Other member function
};


and for your maths formula are totally wrong as coder777 said.
you should use
 
pow(a,b)

did you learn before?

read some ebooks =)
Yes, I know that the value of a left node of a parent is less than that of the parent and the right node of the parent is greater in value to that of the parent. I thought I have stated as much. (I guess I didn't.) I thought it would be easier to do it with integers between 1 and pow(2,n)+1. And yes, I knew that the ^ was the exclusive OR; it has been a while since I did any serious mathematical manipulation in C++, but thanks for the refresher. I also see you hinting at me needing to use OOP. Probably the best habit. I can also see that you are using a declaration of Node* instead of Node. I should take note and try it again; this way, I can just refer to &Tree to touch the parent object. But, does Tree correspond to left or right? Or is the entire tree either going to be addressed by Tree? If so, how do I address the cases where n < max && n != 0? Clearly, the left and right nodes have to be set, and I can't just use
1
2
a->lefttree.element = a.element - pow (2,(max-(n+1)))
a->righttree.element = a.element + pow (2,(max-(n+1)))

because that would only refer to the first subnodes!
I could, however, use this with a recursive function that takes tree * a as parameter. My question is this: what would a be? Would it be leftnode, rightnode, or simply a struct pointed to by an instance of tree? This would answer the question as to what the meaning of a->lefttree.element means. (I think it means the element of the lefttree pointed to by a.)
Last edited on
Here is what I have so far; it keeps thinking a.element means a::element:
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
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <typeinfo>
#include <math.h>

using namespace std;

struct tree
{
    int element;
    tree * lefttree;
    tree * righttree;
};   //end struct

void createtree(int n, tree * a, int max)
{
    if (n < max)
    {
        if (n == 0)
        {
            a.element = pow(2,max-1);
        }   //end if
        else
        {
            a->lefttree.element = a.element - pow(2,max - (n+1));
            a->righttree.element = a.element + pow(2,max - (n+1));
        }   //end else if
        createtree(n+1, a.lefttree,max);
        createtree(n+1, a.righttree,max);
    }   //end if
    else cout << "And we're done here!"<<endl;
}   //end createtree

int main()
{
    int x;
    cout << "Enter the number of levels of nodes (include parent node): " << endl;
    cin >> x;
    tree * b;
    createtree(0,b,x);
    return 0;
}
Last edited on
I think I resolved my error. It all stemmed from the question stated above, and the fact that I, for some reason, solely rely on this website for help. A good friend of mine spent the better part of the night trying to strengthen my understanding of pointers (I have spent too much time in the magical forest of JavaScript) The other source of my error was being lazy by relying on the text editor of Code::Blocks; it knew what I meant, but of course, it is just a text editor. I will try again, and probably post back here if I have further problem. Mentally, I know what I have to do. Let's see if I can get it into code.

EDIT: Problem solved. Thanks to everyone who posted here and got me started!
Last edited on
Topic archived. No new replies allowed.