Binary tree(level by level insert)
Hello,
I already posted this artivle in the Forum "Java Programming" because I'm new to the Forum and didn't see the Algorithms part.. Sorry for the double posting.
I'm trying to program a binary tree. It's totally clear for me to insert new (Integer) Values in an ordinary binary tree.
I simply have to check if the root is equal (--> ready) smaller or larger than the value. I repeat this until I reached a leaf and then I insert a new node.
BUT:
My teacher gave me following problem: Inserting values level by level. The first element is the root, the leftson of the root is nuber2 the rightson of the root is number3
The leftson of root's leftson is number4, the rightson of root's leftson is number 5, the leftson of root's rightson is number 6 and so on.
I have NO idea how to program that.
For example: the 23rd element is in the tree: left, right, right, right, whilst the 24th element is right, left, left, left.
I cannot find a recursive structure, that solves the problem.
Perhaps YOU can save me from gettin' mad ;o)
I really hope so.
This is homework, so I'm just giving you a little hint. If the nodes of the binary tree are numbered from 1 (the root), from left to right, from one level to the next, the following relations hold:
1) for a node n, its parent has node n>>1;
2) if n == 2*(n>>1), node n is a left child of its parent,
otherwise its a right child of its parent.
Your example (node 23) can be located in the tree as follows:
23 --> parent = 23>>1 == 11, 23 is a right child;
11 --> parent = 11>>1 == 5, 11 is a right child;
5 --> parent = 5>>1 == 2, 5 is a right child;
2 --> parent = 2>>1 == 1, 2 is a left child of the root.
Reading upwards, moving downwards in the tree, node 23 can be reached by going left, right, right, right as you already noticed.
kind regards,
Jos
Hello,
That's the solution that came to my mind yesterday.
I make an elementcount and when i have to insert the 57th element,
i make the following:
57 odd -->rightson
57/2 = 28even-->leftson
28/2 = 14even-->leftson
14/2 = 7odd -->rightson
7/2 = 3odd -->rightson
then I read the last one first
--> right, right, left, left, right
I wanted to save the left's and right's in a BitSet (0,1)
and so I can clearly identify every node.
But can you think of a recursive code to solve the problem?
> But can you think of a recursive code to solve the problem?
Ok, here's another hint -- take that node 23 again as an example. If you write out this number in binary (10111) and skip the leftmost 1 in this pattern (x0111), start reading from left to right, starting at the right of th 'x'. 0 denotes left, 1 denotes right. Does that ring a bell?
Something like the following (pseudo code) should come up --
insert(Node node, int val, int pattern, int bitmask) {
if (bitmask == 1)// we have to insert now
if ((pattern & bitmask) == 1)// insert right
node.right= new Node(val);
else// insert left
node.left= new Node(val);
else if ((pattern & bitmask) == 1) // move right
insert(Node.right, val, pattern, bitmask >> 1);
else// move left
insert(Node.left, val, pattern, bitmask >> 1);
}
Some bits and pieces are left as an exercise ;-)
kind regards,
Jos
> But can you think of a recursive code to solve the problem?
Ok, here's another hint -- take that node 23 again as an example. If you write out this number in binary (10111) and skip the leftmost 1 in this pattern (x0111), start reading from left to right, starting at the right of th 'x'. 0 denotes left, 1 denotes right. Does that ring a bell?
Something like the following (pseudo code) should come up --
insert(Node node, int val, int pattern, int bitmask) {
if (bitmask == 1)// we have to insert now
if ((pattern & bitmask) == 1)// insert right
node.right= new Node(val);
else// insert left
node.left= new Node(val);
else if ((pattern & bitmask) == 1) // move right
insert(Node.right, val, pattern, bitmask >> 1);
else// move left
insert(Node.left, val, pattern, bitmask >> 1);
}
Some bits and pieces are left as an exercise ;-)
kind regards,
Jos
