CODEWITHSUNDEEP
javaalgorithm
wwww
wwww

Reputation: 822

building tree from input data

Suppose you have 0001[C]1[T]1[G]1[A] or 01[A]01[G]01[C]1[T] etc. , when 0-node, 1-leaf and you set character into it. You build your tree starting from the left branch.

Tree generated for 01[A]01[G]01[C]1[T]

Tree generated for 01[A]01[G]01[C]1[T]

I tried to write it like that but It cant be solved that way

  public Node getHuffmanTree(String treeCode){
      treeCode=  treeCode.replaceAll("[\\[\\]]","");
        Node root=new Node();
        int i=0;
        while (!treeCode.isEmpty()){
            if(treeCode.charAt(i)=='1'){
                generateHuffmanSubTree(treeCode.substring(0,i+2),root);
                treeCode=treeCode.substring(i+2);
                i=0;
                break;

            }else ++i;
        }


        while (!treeCode.isEmpty()){
            if(treeCode.charAt(i)=='1'){
                Node subTree=new Node();
                generateHuffmanSubTree(treeCode.substring(0,i+2),subTree);
                treeCode=treeCode.substring(i+2);
                i=0;
                //tree merge
                huffmanTreeMerge(root,subTree);
                traversePreOrder2(root);
            }else ++i;
        } 
        return root;
    }

 private void huffmanTreeMerge(Node root,Node node){
        if(root.getLeft()!=null && root.getRight()==null){
            root.setRight(node);
            return;
        }else if(root.getLeft()==null && root.getRight()==null){
            return;
        }
        huffmanTreeMerge(root.getLeft(),node);
        huffmanTreeMerge(root.getRight(),node);


    }

    private void generateHuffmanSubTree(String treeCode,Node node){
        if(!treeCode.isEmpty()) {
            if (node == null) {
                node = new Node();
            }
            if (treeCode.charAt(0) == '1') {

                Sign sign = new Sign();
                sign.setCharacter(treeCode.charAt(1));
                //    System.out.println(treeCode.charAt(1));
                node.setSign(sign);
                return;
            }else if(treeCode.charAt(0) == '0'){
                node.setLeft(new Node());
                generateHuffmanSubTree(treeCode.substring(1),node.getLeft());
            }
        }
    }

Upvotes: 1

Views: 85

Answers (1)

trincot
trincot

Reputation: 350272

Some remarks about your code:

  • It has a lot of code duplication.
  • Instead of passing a node around, return the root of a subtree, and leave it to the caller to attach that node to the left/right child of a parent node.
  • I would use a StringCharacterIterator instead of creating new (shorter) string as you go. With its current and next methods you can easily process each character, and the caller of a recursive call, will continue at the position where the recursion ended up.

Here is how it could be done. Note that I did not add error handling, like when the input string is incomplete:

import java.text.*;

/* ... */

Node generateHuffmanSubTree(CharacterIterator iterChar) {
    char ch = iterChar.current(); 
    iterChar.next();
    Node node = new Node();
    if (ch == '1') { // a leaf
        Sign sign = new Sign();
        sign.setCharacter(iterChar.next()); // skip "[" and get char
        iterChar.next();
        iterChar.next(); // skip "]"
        node.setSign(sign);
    } else { // can only be "0", so no IF is needed here
        node.setLeft(generateHuffmanSubTree(iterChar));
        node.setRight(generateHuffmanSubTree(iterChar));
    }
    return node;
}

Node getHuffmanTree(String treeCode) {
    return generateHuffmanSubTree(new StringCharacterIterator(treeCode));
}

Upvotes: 1

Related Questions