0

次のようにファイルから入力しているJavaクラスBinaryTree<t>があります。

E .
T -
I ..
N -.
M --
A .-
W .--
R .-.
S ...
etc (to end of alphabit)

BinaryTreeには次のものがあります。

setRight(BinaryTree) -sets the right element
setLeft(BinaryTree) -sets the left element   
setRootElement(t) -sets the root element
getRight() -gets the right element
getLeft()  -gets the left element 
getRootElement() -gets the root element of the node IE/ a Character
size() -returns the size of the tree

これらは私が与えられたBinaryTreeクラスで利用可能な唯一のメソッドです

だから私がやりたいのは、ファイルの各行を1つずつ読み、文字と「モールス信号」の文字列を取得することです。注：ファイルの読み取りにはScannerクラスしか使用できません！

次に、ファイルの内容といくつかのルールからこのツリーを再帰的に埋めたいと思います。

「。」左へのタックを意味するため、ファイルの最初の部分は、ルートの左側に「E」文字が付いたタックノードを意味します。

「-」は右へのタックを意味するため、ファイルの2行目は、ルートの右側に「T」文字が付いたタックノードを意味します。

したがって、「W .--」は、ルートから「W」のノードをタックすることを意味します。1つのノードを左に、次に1つのノードを右に、次にそのノードの右側にタックします。

最終的に、ツリーは次のようになります。

ツリーhttp://i56.tinypic.com/339tuys.png

Recursionを初めて使用するため、スキャナーを使用してファイルから読み取るときに、ツリーが再帰的に満たされる方法を視覚化するのに多くの問題があります。

他の場所でファイルを読み取り、その情報を再帰メソッドに渡す必要がありますか？

または、再帰的な方法でファイルを正しく読み取ることができますか？それは不可能のようです。

また、ベースケースとして何を使用しますか。これは、最終的なツリーのサイズであるため、t.size（）==27を使用したいと思います。

何か提案やコメントをいただければ幸いです!!

ありがとうございました！

4

1 に答える 1

1 
Scanner sc = new Scanner(new File(...));
while (sc.hasNext()) {
  String letter = sc.next();
  String morse = sc.next();
  BinaryTree forPosition = theBinaryTree;
  for(int i = 0; i < morse.length(); i++) {
    if (morse.charAt(i) == '.') {
      if(forPosition.getLeft() == NULL) {
        forPosition.setLeft() = new BinaryTree();
      }
      forPosition = forPosition.getLeft();
    }
    else {
      // similar
    }
  }
  forPostion.setRootElement(letter);
}

奇妙な再帰バージョン：

Scanner sc = new Scanner(new File(...));
while (sc.hasNext()) {
  String letter = sc.next();
  String morse = sc.next();
  findTheNode (theBinaryTree, letter, morse);
  }
  forPostion.setRootElement(letter);
}

findTheNode (BinaryTree node, String letter, String morse) {
  if (morse.length() == 0) {
    node.setRootElement(letter);
    return;
  } // found

  if (morse.charAt(0) == '.') {
    if (node.getLeft() == NULL) {
      node.setLeft() = new BinaryTree();
    }
    findTheNode (node.getLeft(), letter, morse.substring(1));
  }
  else {
    // similar
  }   
}

上記の両方が機能することを願っています。

結果は次のようになります。

再帰は通常、トラバーサルおよびバイナリ検索ツリーに使用されますが、このツリーはTrieに似ており、アルファベットが2文字（つまり.および-）しかないためです。ツリーの構築の規則（.左と-右）により、再帰を使用する必要がなくなります。

于 2011-03-18T02:33:36.843 に答える