バランスの取れたツリー[宿題]

Question

宿題で最大周波数を見つける：両方どのように多くのユニークワードファイル 内を知ることができるようにするために

だけでなく、単語の出現回数は、あなたが特別な を開発しますツリーデータ構造。 TreeSetCounterクラスを呼び出します。このようなツリー内のノードは、単語とカウンタで構成される です。手順 が実装されました。

addWord-単語が存在しない場合、単語を追加します。単語 が既にカウンタインクリメント

なる場合は（空ください） - 回数の最も多いが発生している木も、

getMaxFrek（）-return単語になります。 どのようにして最も効果的に行うことができますか？

iterator（） - イテレータをツリーに返します。これは、アルファベット順に のツリーを印刷するために使用されます。

バランスツリーの実装を出発点として使用します。 ファイルを読み込んで、各単語の単語と出現回数の両方を で表示するプログラムを作成します。

私はどのように私はこれを実装する必要がありますアイデアを与えることができますどのような方法は、最速の木全体をトラバースし、最大見つける？

ツリー追加コード：

/** 
* Insert into the tree. 
* @param word the item to insert. 
* @freq increment if word is already present. 
*/ 
public void addWord(String name) { 
    root = addWord(name,root); 
} 
/** 
* Internal method to insert into a subtree. 
* @param word the item to insert. 
* @param t the node that roots the tree. 
* @return the new root. 
* @freq increment if word is already present. 
*/ 
protected Node addWord(String word, Node t) 
{ 
    if(t == null) 
     t = new Node(word); 
    else if(word.compareTo(t.word) < 0) 
     t.left = addWord(word, t.left); 
    else if(word.compareTo(t.word) > 0) 
     t.right = addWord(word, t.right); 
    else 
     t.freq++; 
    return t; 
} 

仕事をdoesntのgetMaxFreq ...私は事前にNullPointerExceptionがに

private Node getMaxFreq(Node node){ 
    Node temp = null; 
    if(node.left != null){ 
     if(node.compareTo(getMaxFreq(node.left)) > 0){ 
      temp = node; 
     } 
     else{ 
      temp = node.left; 
     } 
    } 
    if(node.right != null){ 
     if(node.compareTo(getMaxFreq(node.right)) > 0){ 
      temp = node; 
     } 
     else{ 
      temp = node.right; 
     } 
    } 
    return temp; 

} 

感謝を入手します！

Answer 1

"getMaxFreq"の実装でこの欠陥を見つけるのは簡単ですが、1つのノードを持つツリーのシナリオを考えてみると、正しい答えが唯一のノードである必要があります。

ツリーのイテレータをアルファベット順に返すことが要件の1つです。直感的な解決策の1つは、バイナリ検索ツリーのイテレータ実装のために、ツリーノードキーとして単語を含むバイナリ検索ツリーを実装することです。hereは良いガイドラインです。

頻度が最も高い単語を見つけるには、バイナリツリーの最大要素を見つけるために再帰的に使うのが良い例です。この場合、最大要素は最も頻度の高い単語です。