1

I am trying to create a complete binary tree using a linked list, instead of arraylist, without comparing node values. What I mean is on inserting a new value, I do not wish to compare if the value is less, greater or equal than the root's value, so as to add it either to the left link or to the right link, but still be able to create a complete binary tree.

Do you think it's possible? If yes, do you have any idea or can you point me to something I can use/read to do it?

EDIT:

Here's an example to make my question more clear:
I am adding the numbers in the order presented through the insert method: 1 2 3 4 5 6
the insert method takes care of the structure of the tree.
1 becomes the root since it's the first value added.
2 is the left child of 1
3 the right child of 1
4 the left child of 2
5 the right child of 2
6 the left child of 3

SOLUTION:

public void insert(Comparable item) {
    total++;
    if (root == null) {
        root = new TreeNode(item);
    } else {
        int quotient=total;
        Stack path = new Stack();
        TreeNode p = root;  // helper node to follow path
        quotient /= 2;  // skip last step
        while (quotient>1) {    // build path to follow
            path.push(quotient%2);
            quotient /= 2;
        }
        while (!path.isEmpty()) {
            Object q = path.pop();
            if (q.equals(0))
                p = p.getLeft();
            else
                p = p.getRight();
        }
        if (total%2==0) // check last step
            p.setLeft(new TreeNode(item));
        else
            p.setRight(new TreeNode(item));
    }
}
Kara
  • 6,115
  • 16
  • 50
  • 57
dom
  • 106
  • 1
  • 9
  • Can you post the code implemented with an ArrayList? What is it that makes this possible with an ArrayList object that makes it unknown-possible with a LinkedList. – Christopher Neylan Dec 11 '11 at 00:20
  • I know. I'm sorry. It's because I'm aware of what kinds of people exist online and I really hate it when reading long posts full of nonsense without an actual answer to what the author asked. It's a waste of time and bandwidth. – dom Dec 11 '11 at 00:23
  • 2
    SO organizes things nicely so that those "trolling" parts of the thread are pushed to the bottom, no worries here. – Jon Egeland Dec 11 '11 at 00:27
  • @user112358132134 I would rather not as my code is really long to break down for the post. With an arraylist you can set/get the data for the parent at location [(i-1)/2], left child at [2i+1] and right child [2i+2]. with a linked list you have to set/get the actual object. I hope it makes sense. if not I'll write a smaller sample of my code. – dom Dec 11 '11 at 00:28
  • 1
    @dom Agreed; reading a bunch of stuff where only a third of the text is relevant is irritating. – Dave Newton Dec 11 '11 at 00:29
  • So then you're not actually creating a real binary tree---you're building the binary tree structure, but it is not properly ordered? – Christopher Neylan Dec 11 '11 at 00:31
  • What exactly is your goal? It would be helpful to know what you intend to do with the list, as the answers depend on it. – Pubby Dec 11 '11 at 00:32
  • @user112358132134 yes, that is correct. I don't need any sorting or proper structure other than being a complete tree. I suppose I should have said that earlier. Sorry. I'll edit my post. – dom Dec 11 '11 at 00:41
  • @Pubby my goal is to create a tree where I'll add the numbers 1 2 3. 1 will be the root, 2 the left child and 3 the right child an so on. – dom Dec 11 '11 at 00:42
  • Generally you can use LinkedList just like ArrayList. Post the fragment that's causing trouble. – Piotr Praszmo Dec 11 '11 at 00:54

3 Answers3

11

Keep a count of how many items you have in the tree.

Then, to add the nth item follow the path created by dividing n repeatedly by two and keeping track of the remainder. Follow the "route" created by the remainder in reverse: where 1 means right and 0 means left.

For example, to add the 11th item: 

11/2 = 5 (1)
5/2 = 2 (1)
2/2 = 1 (0)

That means from the root, you'd go left, right, right.

Whymarrh
  • 13,139
  • 14
  • 57
  • 108
yurib
  • 8,043
  • 3
  • 30
  • 55
1

It seems your question is unrelated to LinkedList. It was a little confusing.

If you know how many elements are in tree already, you can calculate the position from that number. It's binary representation is the path you have to take. See here.

If you don't know anything about current state of the tree, you need to do a Breadth-first search to find the first empty spot.

Piotr Praszmo
  • 17,928
  • 1
  • 57
  • 65
  • Excellent! Thank you, all I could think of was just plain recursive insertion. I will give it a go and post back my results. – dom Dec 11 '11 at 01:49
0

The entire basis of a binary tree is on comparing values and sending them left or right down the tree.

Therefore, it is impossible to create a binary tree without comparisons.

But you did say upon insertion, so you could add the item to the end of the list, and then sort it when you call for the tree. Like this:

list.add(value); //Just add the item to the end

call(); //This method would sort the list into a tree appropriately.

This option also allows you to change the type of tree dynamically, since you could add a parameter to call() that specifies a tree type.

Jon Egeland
  • 12,470
  • 8
  • 47
  • 62