Как восстановить двоичное дерево из кодировки пути?

Question

Предположим, у меня есть данные, содержащие следующую информацию:

(11, LL) (7, LLL) (8, R) (5,) (4, L) (13, RL) (2, LLR) (1, RRR) (4, RR)()

, в результате чего второе поле указывает путь от корневого узла, а пустое поле указывает корневой узел и() указывает конец данных.

Выходной сигнал будет levelorder: 5 4 8 11 13 4 7 2 1

Как можно реконструировать бинарное дерево? Обратите внимание, что существует вероятность того, что узел может отсутствовать. Например, LLL и L присутствуют, но ни один узел не соединяет их. В таком случае для их соединения должен быть создан узел с номером -1.

Что я до сих пор понял, это создать класс NodePath, который хранит данные и путь, например. NodePath (11, LL) как из строкового значения. Затем я повторяю каждый токен строки. Во время итерации я сравниваю длины пути и сохраняю их в LinkedList. . 11, LL -> 7, LLL и когда 8 приходит, тогда оно становится 8, R -> 11, LL -> 7, LLL

Теперь вот где я застреваю, потому что не знаю как дифференцировать LLL и LLR и как построить двоичное дерево соответственно. Боюсь, я бы поставил LLL и LLR на противоположные позиции.

Answer 1

Вы можете построить Map с парами ключ-значение - ключи - это ваши пути («LLL») и значения чисел («7»).

На втором этапе перейдите по ссылке Map и создайте каждый путь сверху вниз, создав новые узлы со значением по умолчанию «-1», где их нет, и, если возможно, используйте существующий узел.

Answer 2

Это интересная проблема. Я хотел бы предложить предоставить узлам дерева возможность следовать за конструированием узлов по ходу пути. Я игнорировать весь код для декодирования строки и переход к сердцу строительства:

class Node { 
    public enum Direction { 
     L, R; 
    } 

    private int value = -1; 
    private EnumMap<Direction, Node> children = new EnumMap<>(Direction.class); 

    public Node nodeWithPath(List<Direction> path) { 
     if (path.isEmpty()) { 
      return this; 
     } else { 
      Direction direction = path.remove(0); 
      if (!children.containsKey(direction)) 
       children.put(direction, new Node()); 
      return children.get(direction).nodeWithPath(path); 
     } 
    } 
} 

Тогда это простой вопрос, когда вы декодируете инструкцию:

root.nodeWithPath(path).setValue(value); 

---

В качестве дополнительный бит (возможной) помощи, используя «L» и «R» в качестве констант перечисления, вы можете создать тривиальные пути в Java 8 из вашей строки:

public void addValue(Node root, String pathString, int value) { 
    List<Direction> path = Arrays.stream(pathString.toCharArray()) 
     .map(Character::toString) 
     .map(Node.Direction::valueOf) 
     .collect(Collectors.toList()); 
    root.nodeWithPath(path).setValue(value); 
} 

Однако, если вы на раннем этапе обучения Java, то код, который я только что написал, может быть более запутанным, чем полезным, поэтому не стесняйтесь игнорировать его и использовать традиционную итерацию или синтаксический анализ через токенизацию :-)

Answer 3

является решением, основанным на grappa.

Во-первых, базовый класс для узла:

public final class BinaryTreeNode 
{ 
    private int value = -1; 
    private BinaryTreeNode left = null; 
    private BinaryTreeNode right = null; 

    public int getValue() 
    { 
     return value; 
    } 

    public BinaryTreeNode getLeft() 
    { 
     return left; 
    } 

    public BinaryTreeNode getRight() 
    { 
     return right; 
    } 

    public void setValue(final int value) 
    { 
     this.value = value; 
    } 

    public void setLeft(final BinaryTreeNode left) 
    { 
     this.left = left; 
    } 

    public void setRight(final BinaryTreeNode right) 
    { 
     this.right = right; 
    } 
} 

Теперь класс строитель:

public final class BinaryTreeBuilder 
{ 
    private final BinaryTreeNode root = new BinaryTreeNode(); 

    private BinaryTreeNode current = root; 

    private int nodeValue; 

    public BinaryTreeNode getRoot() 
    { 
     return root; 
    } 

    public boolean setValue(final String match) 
    { 
     nodeValue = Integer.parseInt(match); 
     return true; 
    } 

    public boolean moveLeft() 
    { 
     BinaryTreeNode node = current.getLeft(); 
     if (left == null) { 
      node = new BinaryTreeNode(); 
      current.setLeft(node); 
     } 
     current = node; 
     return true; 
    } 

    public boolean moveRight() 
    { 
     BinaryTreeNode node = current.getRight(); 
     if (right == null) { 
      node = new BinaryTreeNode(); 
      current.setRight(node); 
     } 
     current = node; 
     return true; 
    } 

    public boolean commitNode() 
    { 
     current.setValue(nodeValue); 
     current = root; 
     return true; 
    } 
} 

Наконец анализатор:

public class BinaryTreeParser 
    extends BaseParser<BinaryTreeNode> 
{ 
    protected final BinaryTreeBuilder = new BinaryTreeBuilder(); 

    Rule endOfData() 
    { 
     return sequence("()", EOI); 
    } 

    Rule moves() 
    { 
     return firstOf(
      sequence('L', builder.moveLeft()), 
      sequence('R', builder.moveRight()) 
     ); 
    } 

    Rule oneNode() 
    { 
     return sequence(
      '(', 
      sequence(oneOrMore(digit()), builder.setValue(match())), 
      ',', 
      zeroOrMore(moves()), 
      ')', builder.commitNode(); 
     ); 
    } 

    Rule allNodes() 
    { 
     return join(sequence(testNot(endOfData()), oneNode()) 
      .using(' ') 
      .min(0); 
    } 

    public Rule fullTree() 
    { 
     return sequence(allNodes(), endOfData(), push(builder.getRoot()); 
    } 
} 

Теперь вы просто должны запустить парсер и получить результат:

final BinaryTreeParser parser = Parboiled.createParser(BinaryTreeParser.class); 

final ParseRunner<BinaryTreeNode> runner = new BasicParseRunner<>(parser.fullTree()); 

final ParsingResult<BinaryTreeNode> result = runner.run(yourInput); 

if (result.isSuccess()) 
    tree = result.getTopStackValue(); 

Поскольку граппа зависит от Гуавы, а Guave предоставляет BinaryTreeTraverser, вы использовали бы это для отображения результата.

Конечно, этот подход довольно «искушен»; здесь является более простым:

• создать Comparator<String>, который сравнивает следующим образом: строка больше, чем другой, если она больше; и если они имеют одинаковую длину, то применяется каноническое упорядочение;
• создать TreeMap<String, Integer> с путями в качестве ключей, значениями узлов в качестве значений и вашим компаратором выше как ключевым компаратором;
• проанализируйте свои узлы на карте;
• Показать записи в порядке.

Обратите внимание, что перед отображением вам нужно будет проверить, что у вас есть запись для корня, то есть пустая строка.