Array list based binary trees

[xThrash]

Hello everyone,

Im working on a task where I have to implement an array list based complete binary tree but im not too sure how to do so. My java knowledge is very basic, whilst I could implement a normal binary tree, when its array list based im clueless. I dont know enough about java to convert pseudo code and things like that.

If someone could post some advice on doing this id appreciate it, maybe some websites or something. I cant explain exactly what I would like to know but im hoping someone might be able to help me.

Thanks

[Taywin]

The implementation is tricky depending on how you want it to be. Do you have to implement the tree using only one ArrayList? Are you allowed to implement your own class to act as a tree node/leaf? Is there any constraints to the ArrayList you can make (i.e. limitation of tree height)? Do you need to create only basic binary tree?

One sure thing, you need to study how ArrayList class works. You can check its API doc here.

[xThrash]

The question was quite broad so I guess I can change any of those factors. (The question is literally implement an array list based representation of a complete binary tree) its the first part of a three part question so im assuming it will be quite basic. From what I understand:
One arraylist is all I need.
You can create as many classes as possible, im assuming I will need at least two anyway.
Theres no limitation to the arraylist
And yes the binary tree should be very basic, i.e. I dont think it needs to include any errors or anything like that.

Thanks for taking the time to reply.

[xThrash]

Can nobody else help? I dont like to annoy people but ive left this quite late and some help is urgent right now.

Thanks

[Taywin]

OK, I came up with an idea of how to implement a binary tree using one ArrayList. You need to do some math here. The concept is based on an algorithm for creating a hash table liked using a fixed array.

The concept is to create a new whole set of nodes of a height if the supposed index is out of bound (out of the size of current tree). All nodes that are not assigned value will have its value as Integer.MIN_VALUE.

Your Node class is going to contain node value. In this case, let say it holds an integer value. You need 2 constructor - one is for assigned value and the other is an empty node. You also need to be able to assign a value to the node. A sample code for the Node class is below.

class MyTreeNode {
  int nodeValue;

  // constructor 1
  public MyTreeNode() {
    nodeValue = Integer.MIN_VALUE;
  }

  // constructor 2
  public MyTreeNode(int val) {
    nodeValue = val;
  }

  // must make sure that the node is empty before calling this!
  public void setValue(int val) {
    nodeValue = val;
  }

  // must make sure that you want to kill the node!
  public boolean isEmpty() {
    return (nodeValue>Integer.MIN_VALUE);
  }
}

Now you implement binary tree class and have one ArrayList as its variable. The only hard part is the insertNode() method. In the insertNode(), you need to compare the incoming value and the current checking node. If the value is less than, then you must go to the left child which is the odd index from its parent; otherwise, go to the right child which is the even index from its parent. I will try to explain it using an array representation.

/*
 Assume that you have an array list called a
 ArrayList<MyTreeNode> a = new ArrayList<MyTreeNode>();
 -> a => []

 Now you add '3' to a
 Because a size is 0, '3' is added to a automatically
 -> a => [3]

 Now you add '7' to a
 Parent index is 0 (from '3')
 '7' is the right child of '3'
 Compute the index for '7' which would be 2 (2*parent_index + 2)
 Add 2 nodes to a but assign value '7' to the index 2 (height of tree becomes 2)
 -> a => [3, Integer.MIN_VALUE, 7]

 Now you add '5' to a
 Parent index is 0 (from '3')
 Parent index is 2 (from '7')
 '5' is the left child of '7'
 Compute the index for '5' which is 5 (2*parent_index + 1)
 Add 4 elements to a and assign '5' to index 5 (height of tree becomes 3)
 -> a => [3, Integer.MIN_VALUE, 7, Integer.MIN_VALUE, Integer.MIN_VALUE, 5, Integer.MIN_VALUE]

 Now you add '1' to a
 Parent index is 0 (from '3')
 '1' is the left child of '3'
 Compute the index for '1' which is 1 (2*parent_index + 1)
 No need to add any new element but rather set the value of the node
 -> a => [3, 1, 7, Integer.MIN_VALUE, Integer.MIN_VALUE, 5, Integer.MIN_VALUE]
 */

As you see that the Integer.MIN_VALUE represents 'null' value of the child (leaf) node. The tricky part is that you must create the all leaves of each height once you know that the new insert node falls outside of bound, and then assign only the value to the computed index you need. If the node exists already but no value in it (Integer.MIN_VALUE), then you don't need to create a new now but assign the value to the node directly. When you print out the tree, use the same index computation. I have implemented a test and it works.

Hope this help...

[xThrash]

Hello again, thanks for your reply and the help youve provided.
Unfortunately im getting quite desperate now, this problem should not be as complicated as its appearing, im a first year UG at uni and this is the first part of an assignment, according to my lecturer it shouldnt take very long to do at all.
Would it be possible for you to supply some more code please? Im not sure on how to get the binary tree started using indexes and things like that.
Thanks

[Taywin]

Right now, I am not at the computer which has the code for this problem. I will give it to you when I can (in about 8 hours from now).

[Taywin]

OK, here is the skeleton of the code. Most of the part are done, but the insertNode() is left blank for you. If you still have a problem with implementation, please let me know.

// Node class
class MyTreeNode {
  int nodeValue;

  // constructor
  public MyTreeNode() {
    nodeValue = Integer.MIN_VALUE;
  }
  // constructor
  public MyTreeNode(int val) {
    nodeValue = val;
  }

  // Return true if the node value has not been assigned
  // (value is equal to Integer.MIN_VALUE).
  // The node value used in this code must not ever be equal to Integer.MIN_VALUE.
  public boolean isEmpty() {
    return (nodeValue==Integer.MIN_VALUE);
  }
}  // class MyTreeNode


// The binary tree
import java.util.ArrayList;

class MyBinaryTree {
  ArrayList<MyTreeNode> tree;

  // Constructor
  public MyBinaryTree() {
    tree = new ArrayList<MyTreeNode>();
  }
  // Constructor
  public MyBinaryTree(MyTreeNode n) {
    tree = new ArrayList<MyTreeNode>();
    tree.add(n);
  }

  // Polymophic, insert a node from an integer
  public void insertNode(int n) {
    MyTreeNode node = new MyTreeNode(n);
    insertNode(node);
  }

  // Polymophic, insert a node from a MyTreeNode class instance
  public void insertNode(MyTreeNode n) {
    if (tree.isEmpty()) {  // empty head, just add it
      tree.add(n);
    }
    else {  // not empty, search for the correct position to add
      // you need to implement this part using the approach I told you above.
    }
  }  // insertNode(MyTreeNode)


  // Print out the tree using the format below.
  // Node Value: x (node_index)
  //   Left:  L
  //   Right: R
  // If the leaf node is empty, display '-' instead.
  public void printTree() {
    int idx=0;
    int max = tree.size();
    int lIdx, rIdx;
    MyTreeNode node;
    String lVal, rVal;
    while (idx<max) {
      node = tree.get(idx);
      if (!node.isEmpty()) {
        lIdx = (idx*2)+1;
        rIdx = (idx*2)+2;
        lVal = (lIdx<max && !tree.get(lIdx).isEmpty()) ? (tree.get(lIdx).nodeValue+"") : "-";
        rVal = (rIdx<max && !tree.get(rIdx).isEmpty()) ? (tree.get(rIdx).nodeValue+"") : "-";
        System.out.println("Node value: "+node.nodeValue+" ("+idx+")");
        System.out.println("  Left:  "+lVal);
        System.out.println("  Right: "+rVal);
      }
      idx++;
    }
  }  // printTree()


  /*
   main for testing
   The result should be as folow.
   Node value: 3 (0)              3             height->0 1 total (2^0)
     Left:  0                    /  \
     Right: 5                   /    \
   Node value: 0 (1)           0      5         height->1 3 total (2^1)+h0
     Left:  -                 / \    / \
     Right: -                E   E  E  17       height->2 7 total (2^2)+h1+h0
   Node value: 5 (2)                  /  \
     Left:  -                        /    \
     Right: 17                      13    23    height->3 15 total (2^3)+h2+h1+h0
   Node value: 17 (6)              / \    / \
     Left:  13                    6   E  E   E  height->4
     Right: 23                   / \
   Node value: 13 (13)          E   9           height->5
     Left:  6                      / \
     Right: -                     E   E         height->6
   Node value: 23 (14)
     Left:  -                 E -> empty node
     Right: -
   Node value: 6 (27)
     Left:  -
     Right: 9
   Node value: 9 (56)
     Left:  -
     Right: -
  */
  public static void main (String[] args) {
    MyBinaryTree bt = new MyBinaryTree();
    bt.insertNode(3);
    bt.insertNode(5);
    bt.insertNode(0);
    bt.insertNode(17);
    bt.insertNode(13);
    bt.insertNode(23);
    bt.insertNode(6);
    bt.insertNode(9);
    bt.printTree();
  }
}

However, the print out doesn't show the unused ArrayList elements which would suppose to be in the ArrayList but not in the tree.

[xThrash]

Thanks a lot, I really appreciate your help!
If I wanted to make it a complete binary tree (which im assuming it isnt because not all children are as leftmost as possible) how could I go about doing this?

Thanks once again.

[Taywin]

A complete binary tree? I am not sure now that this is really a topic for a freshman in uni... What is your lecturer thinking? Is he/she expecting everyone to learn that fast or wants to fail most of the class? A complete binary tree is a tree which all but its leaf level are filled completely. One complete binary tree I used to implement in school is AVL tree. You need to add another part of code to keep the tree balance whenever a node is inserted. To balance the tree, you will have to perform rotate-left and rotate-right. You may read the link I gave you to get some ideas, and then try to implement from it. However, you can actually use other type of balanced trees as well. I just think that AVL is the easy.

[xThrash]

Well its the first part of the assignment, the other two parts are to do with heaps and the heap sort algorithm, so I assume it needs to be complete to do the next parts.

[Taywin]

That will require you to understand the implementation deeper. What course is this? Is it just the first computer science class? Not sure if the first course would really go that deep in implementation. It will not be an easy task to learn everything from scratch in a semester.

Well, you will need the balance tree for that heap. Though, it is somewhat half way through the 2nd part for your assignment already.

[agieli]

hi guys.i'm working on wireless sensor network which would detect and track bluetooth device(mobile phone).

i would like to ask which equipments would i need(type of nodes,gateway)

thanx