Рекурсия Заполнение Дерева - PullRequest
Новая
       30

Рекурсия Заполнение Дерева

0 голосов
/ 18 марта 2011

У меня есть класс Java: BinaryTree , который я заполняю из файла следующим образом: 

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 мне дали

Так что я хочу сделать, я хочу прочитать каждую строку файла одну за другой, получая букву и строку "кода Морзе".ПРИМЕЧАНИЕ: я могу использовать только класс Scanner для чтения файла!

Тогда я хочу рекурсивно заполнить это дерево из содержимого файла и нескольких правил:

A "«.означает галочку влево, поэтому первая часть файла будет означать узел галочки с символом «E» слева от корня

A «-» означает галочку вправо, поэтому вторая строка в файле будет означать галкуузел с символом 'T' справа от корня.

Таким образом, "W .--" будет означать узел галочки с буквой "W" от корня Один узел слева, затем один узел справа, затем галссправа от этого узла.

В конце концов дерево будет выглядеть так:

tree http://i56.tinypic.com/339tuys.png

Поскольку я новичок в рекурсии IУ меня много проблем с визуализацией того, как дерево может быть заполнено рекурсивно при чтении из файла с помощью сканера.

Должен ли я прочитать файл в другом месте и передать информацию в рекурсивный метод ???

Или я мог бы прочитать файл прямо в рекурсивном методе?Что не представляется возможным.

Кроме того, что бы вы использовали в качестве базового варианта, я испытываю желание использовать t.size () == 27, потому что это размер конечного дерева.

Любые предложения или комментарии будут с благодарностью !!

Спасибо!

1 Ответ

1 голос
/ 18 марта 2011 
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
  }   
}

Надеюсь, что оба из вышеперечисленных работ.

Результат может выглядеть следующим образом: this .

Рекурсивный обычно используется для обхода и двоичного дерева поиска , но это дерево больше похоже до Три , всего 2 символа в алфавите (то есть . и -). Правило построения дерева (. для левого и - для правого) делает ненужным использование рекурсии.

...