Поскольку гарантируется, что каждый внутренний узел имеет ровно 2 дочерних элемента, мы можем просто рекурсивно построить дерево, используя это.
Мы вызываем нашу функцию с предоставленным вводом, и она проверяет первый полученный символ. Если это листовой узел, он просто возвращает лист. Если это внутренний узел, он просто вызывает себя для левого и правого поддеревьев и возвращает дерево, сформированное с использованием узла в качестве корня, а левое и правое поддеревья - в качестве его левого и правого потомков.
Код следует (на Python). Обратите внимание, я использую tuple s для представления узла, поэтому дерево имеет значение tuple из tuples.
#! /usr/bin/env python
from collections import deque
def build_tree(pre_order):
root=pre_order.popleft()
if root=='L':
return root
else:
return (root,build_tree(pre_order),build_tree(pre_order))
if __name__=='__main__':
print build_tree(deque("NNLLL"))
Редактировать: код в Java
import java.util.*;
class Preorder{
public static Node buildTree(List<Character> preorder){
char token=preorder.remove(0);
if (token=='L'){
return new Node(token,null,null);
}
else{
return new Node(token,buildTree(preorder),buildTree(preorder));
}
}
public static void main(String args[]){
List<Character> tokens=new LinkedList<Character>();
String input="NNLLL";
for(int i=0;i<input.length();i++) tokens.add(input.charAt(i));
System.out.println(buildTree(tokens));
}
}
class Node{
char value;
Node left,right;
public Node(char value, Node left, Node right){
this.value=value;
this.left=left;
this.right=right;
}
public String toString(){
if (left==null && right==null){
return "("+value+")";
}
else{
return "("+value+", "+left+", "+right+")";
}
}
}