ハフマンノードの深さ

Question

私はJavaで新しいです。私は平均深さツリーの深さを取得しようとしています。私はすでにノードの数を持っています。私はちょうど各ノードの深さが必要です。私は木の高さを取得する方法があります。私はこのメソッドを使用して、すべてのノードの深さを取得するためにそれを逆にすることができたら、私は考えています。しかし、私は方法でノードを指定する方法を知らない。 あなたは、方法でノードを1つずつ指定するためのアドバイスはありますか？ 今は自分のメソッドがパラメータとしてツリータイプを取る PS：英語は母国語ではありません。私が持っている任意の混乱

import java.util.*; 

public class HuffmanCode { 
    int numberOfNode = 1; 
    int height; 
    String fullcode = ""; 
    String realcode = ""; 

    // input is an array of frequencies, indexed by character code 
    public HuffmanTree createTree(int[] charFreqs) { 
     PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>(); 
     // initially, we have a forest of leaves 
     // one for each non-empty character 
     for (int x = 0; x < charFreqs.length; x++) { 
      if (charFreqs[x] > 0) 
       trees.offer(new HuffmanLeaf(charFreqs[x], (char) x)); 
     } 
     /* 
     * Step 2 in Huffman coding While loop to remove 2 nodes with the 
     * highest priority(lowest probability) 
     */ 
     while (trees.size() > 1) { 
      // Poll the two nodes with least frequency 
      HuffmanTree a = trees.poll(); 
      HuffmanTree b = trees.poll(); 

      // put into new node and re-insert into queue 
      trees.offer(new HuffmanNode(a, b)); 
      numberOfNode++; 
     } 
     return trees.poll(); 

    } 

    public void printResults(HuffmanTree tree, StringBuffer prefix) { 
     if (tree instanceof HuffmanLeaf) { 
      HuffmanLeaf leaf = (HuffmanLeaf) tree; 

      // print out character, frequency, and code for this leaf (which is 
      // just the prefix) 
      System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix); 
      encodedInput(prefix); 
      for (int x = 0; x < leaf.frequency; x++) { 
       realcode = realcode + prefix; 
      } 

     } else if (tree instanceof HuffmanNode) { 
      HuffmanNode node = (HuffmanNode) tree; 
      numberOfNode++; 

      // move left 
      prefix.append('0'); 
      printResults(node.left, prefix); 
      prefix.deleteCharAt(prefix.length() - 1); 

      // move right 
      prefix.append('1'); 
      printResults(node.right, prefix); 
      prefix.deleteCharAt(prefix.length() - 1); 
      height = findHeight(node); 

     } 

    } 

    public void encodedInput(StringBuffer prefix) { 
     fullcode = fullcode + " , " + prefix; 

    } 

    public int findHeight(HuffmanTree tree) { 
     if (tree == null) { 
      return -1; 
     } 

     if (tree instanceof HuffmanLeaf) { 
      return 0; 
     } else if (tree instanceof HuffmanNode) { 
      int left = findHeight(((HuffmanNode) tree).left); 
      int right = findHeight(((HuffmanNode) tree).right); 

      if (left > right) { 
       return left + 1; 
      } else { 
       return right + 1; 
      } 
     } else { 
      return -1; // does not happen, you might want to raise exception. 
     } 
    } 

    public void printQueue(PriorityQueue<HuffmanTree> pq) { 
     while (pq.size() > 0) { 
      System.out.println(pq.poll()); 
     } 
    } 
} 

他のクラスのために申し訳ありません：

class HuffmanNode extends HuffmanTree { 
    public HuffmanTree left; 
    public HuffmanTree right; 

    public HuffmanNode(HuffmanTree left, HuffmanTree right) { 
     super(left.frequency + right.frequency); 
     this.left = left; 
     this.right = right; 
    } 
} 

class HuffmanLeaf extends HuffmanTree { 
    public char value; // the character this leaf represents 
    public HuffmanLeaf(int frequency, char value) { 
     super(frequency); 
     this.value = value; 
    } 
} 

public class HuffmanTree implements Comparable<HuffmanTree> { 
    public int frequency; // the frequency of this tree 

    public HuffmanTree(int frequency) { 
     this.frequency = frequency; 
    } 
    public int compareTo(HuffmanTree tree) { 
     return frequency - tree.frequency; 
    } 
} 

Answer 1

このコード多分あなたを助けます。ルートからトラバースして深さの合計を計算できます。

public int sum(HuffmanTree tree,int currentDepth) { 
    if (tree == null) { 
     return -1; 
    } 

    if (tree instanceof HuffmanLeaf) { 
     return currentDepth; 
    } else if (tree instanceof HuffmanNode) { 
     int left = sum(((HuffmanNode) tree).left , currentDepth+1); 
     int right = sum(((HuffmanNode) tree).right, currentDepth+1); 
     return left+right; 
    } else { 
     return -1; // does not happen, you might want to raise exception. 
    } 
}