Creating a binary tree based on binary code

Question

I have been stuck for this problem for almost a day now. Basically, I am given a 10000 lines of binary codes. For simplicity, I will show the first 10 lines.

1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 
0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 
0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 1 0 1 
1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 
0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 
0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 
0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 
1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 1

Each line corresponds to the path starting from the root to the leave of a binary tree. There is a leave for each line (you can have node "A" for line 1, "B" for line 2...anything you want to name the nodes) and each lines contains exactly 24 binary codes. For example, 101 corresponds to the following picture , where 0 and 1 corresponds to left and right respectively.

    (root)           
        \   1
         \
      (sentinel node)
          /
       0 /
      (sentinel code)
                 \     1
                  \
                (leave)

Problem is : I kept failing to code up the treeInsert method. (I will later use DFS to traverse the tree but this is not the main concern now.) The main concern is that I cannot code up the treeInsert and this means I cannot build a proper binary tree for the first 10 lines.

In addition, this is also a design problem for me,as I am not sure whether I should have values of 0 and 1 for the sentinel nodes, because it doesn't seem to make sense to create an Edge object in this case.

I have the following code, I don't think it works or does what I want:

class Node{

public enum Color{
    WHITE, BLACK, GRAY
}

Integer node;
Node left, right, p;
Color color;
int N;
int prefix_code;
public Node(){
    this.node = null;
    this.prefix_code = -1;
    N = 0;
}

public Node(int node, int prefix_code){
    this.node = node;
    this.prefix_code = prefix_code;
    N = 1;
}

public String toString(){
    if(node != null){
        return node + "";
    } else{
        return "nil";
    }
}

public int hashCode(){
    return (int)(node * 31);
}

public boolean equals(Object o){
    if(o == this){
        return true;
    }
    if(o == null || getClass() != o.getClass() ){
        return false;
    }
    Node other = (Node) o;
    return node == other.node;
}

public Node[] adj(){
    Node[] adjacent_v = new Node[]{left, right};
    return adjacent_v;
}

public boolean isNull(){
    return node == null;
}

}

class BinaryTree{
Node root;
Node nil;
public BinaryTree(){
    root = new Node(-1,-1);     // make sure Tree is not empty
    nil = new Node();
}

public int size(){
    return size(root);
}

public int size(Node x){
    if(x == null){
        return 0;
    } else{
        return x.N;
    }
}

/*
 *  Insertion begins at the root of the tree
 *  and the pointer x traces a simple path downward
 *  looking for a nil to replace with the input item z.
 *
 *  The method also maintains a trailing pointer y as
 *  the parent of x.
 *
 *  Within the while loop,these two pointers will
 *  move down the tree, going left or right depending on
 *  the comparison of z.key with x.key, until x becomes nil.
 *
 *  This nil occupies the position where we wish to place the
 *  input item z.
 *
 *  The trailing pointer is needed because by the time we find
 *  the NIL where z belongs, the search has proceeded one step
 *  beyond the node that needs to be changed.
 *
 */
public void treeInsert(Integer[] bits, int node){
    Node y = nil;
    Node x = root;
    for(int i = 0; i < bits.length; i++){
        Node z;
        if(i == 23){
            z = new Node(node, bits[i]);
        } else{
            z = new Node(-1, bits[i]);
        }

        y = x;
        if(bits[i] == 0){
            x = x.left;
        } else{
            x = x.right;
        }
        z.p = y;
        if(y.equals(nil)){
            root = z;
        } else if(bits[i] == 0){
            y.left = z;
        } else{
            y.right = z;
        }

        z.left = nil;
        z.right = nil;
        x = z;
    }
}

Perhaps it would help if you had more descriptive variable names than x, y, and z. — Sizik
– Sizik, Commented Jan 15, 2015 at 19:24
looking at your profile it seems you've already asked this question — ControlAltDel
– ControlAltDel, Commented Jan 15, 2015 at 19:34

Jean Logeart · Accepted Answer · 2015-01-15 19:52:27Z

I really do not understand what you are doing in the for-loop. For instance, I do not get why root is assigned in the loop.

Using recursion might help making things clearer:

public void treeInsert(Integer[] bits, int value) {
    treeInsertAux(bits, 0, root, value);
}

private void treeInsertAux(Integer[] bits, int index, Node node, int value) {
    if(index == bits.length) {
        return;
    }
    Node child;
    if(bits[index] == 0){
        child = node.left;
        if(child == null) { // first time we pass by this node
            child = index == bits.length - 1 ? new Node(value) : new Node();
            node.left = child;
            // + set parent of child
        }
    } else {
        child = node.right;
        if(child == null) { // first time we pass by this node
            child = index == bits.length - 1 ? new Node(value) : new Node();
            node.right = child;
            // + set parent of child
        }
    }
    treeInsertAux(bits, index + 1, child, value)
}

Collectives™ on Stack Overflow

Creating a binary tree based on binary code

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related