Как построить бинарное дерево из просто обхода строки заказа уровня

Question

Рассмотрим бинарное дерево со следующими свойствами:

1. Внутренний узел (не листовой узел) имеет значение 1, если у него есть двое детей.
2. У листового узла есть значение 0, так как у него нет детей.

Обход уровня на дереве будет генерировать строку из 1 и 0 (путем печати странного значения на каждом узле по мере их посещения). Теперь данная строка построит двоичное дерево и выполнит обход по порядку на дереве. Строка после заказа должна быть выходом программы.

Например: Input String is 111001000. Создайте из этого двоичное дерево. Затем выполнить обход после заказа на дереве, которое привело бы к выходу: 001001011

«Суть» проблема заключается в том, чтобы создать бинарное дерево из только строк заказа уровня. Как мне это сделать?

Answer 1

Концептуально более простым я считаю.

import java.util.LinkedList; 
import java.util.Queue; 

class WeirdBinaryTree 
{ 
static class Node 
{ 
    private Node right; 
    private Node left; 
    private int weirdValue; 

    public void setWeirdValue(int value) 
    { 
     weirdValue=value; 
    } 
} 

private static Node makeTree(String str)throws Exception 
{ 
    char[] array=str.toCharArray(); 
    Node root=new Node(); 
    Queue<Node> list=new LinkedList(); 
    list.add(root); 
    int i=0; 
    Queue<Node> nextList=new LinkedList<Node>(); 
    while(!list.isEmpty()) 
    { 
     if(array[i++]=='1') 
     {     
       Node temp=list.poll(); 
       temp.left=new Node(); 
       temp.right=new Node(); 
       temp.setWeirdValue(1); 
       nextList.add(temp.left); 
       nextList.add(temp.right);  
     } 
     else 
     { 
      list.poll(); 
     } 
     if(list.isEmpty()) 
     { 
      list=nextList; 
      nextList=new LinkedList<Node>(); 
     } 
    } 
    return root; 
} 

private static void postTraversal(Node localRoot) 
{ 
    if(localRoot!=null) 
    { 
     postTraversal(localRoot.left); 
     postTraversal(localRoot.right); 
     System.out.print(localRoot.weirdValue); 
    } 
} 

public static void main(String[] args)throws Exception 
{ 
    postTraversal(makeTree("111001000")); 
} 
} 

Answer 2

Во-первых, я предполагаю, что ваш level order traversal в основном является BFS.

Теперь давайте посмотрим на строку. Выполняя BFS, мы печатаем «1», если текущий узел имеет двух сыновей. В противном случае это лист, и мы печатаем 0, завершая обработку текущей ветви.

Следовательно, во время обратной задачи мы можем вспомнить список последних узлов открытых ветвей и добавить туда входящие узлы.

Продемонстрируем этот подход на примере:

Level 1: 

Tree : 
     1 - id 0 
Open branches : 0 0 (left and right son) 
Remaining string : 11001000 

********* 

Level 2: 

Tree : 
     1 
     1 1 
Open branches : 1 1 2 2 
Remaining string : 001000 

********* 

Level 3: 

Tree : 
     1 
    1  1 
    0 0 1 0 

Open branches : 5 5 

Remaining string : 00 


Level 4: 

Tree : 
     1 
    1  1 
    0 0 1 0 
     0 0 

No more input, we're done. 

Имея дерево, обход после того, тривиальна.

И код (предполагается, что дерево довольно плотное, в противном случае это не очень эффективные памяти):

import java.util.ArrayDeque; 
import java.util.Queue; 

public class Main { 
static final int MAX_CONST = 50; 

public static void main(String[] args) { 
    String evilString = "111001000"; // Assuming this string is a correct input 

    char[] treeRepr = new char[MAX_CONST]; 
    Queue<Integer> q = new ArrayDeque<Integer>(); 
    q.add(0);  
    for (int i = 0; i < evilString.length(); ++i) { 
     int index = q.remove(); 
     char ch = evilString.charAt(i); 
     if (ch == '1') { 
      q.add(2*(index+1)-1); 
      q.add(2*(index+1)); 
     } 
     treeRepr[index] = ch; 
     // System.out.println(q.size()); 
    } 
    System.out.println(arrToString(treeRepr, 0, new StringBuilder())); 
} 

public static StringBuilder arrToString(char[] array, int index, StringBuilder sb) { 
    if (array[index] == '1') 
    { 
     arrToString(array, 2*(index+1)-1, sb); 
     arrToString(array, 2*(index+1), sb); 
    } 
    sb.append(array[index]); 
    return sb; 
} 
} 

Answer 3

Если это было разрешено, я хотел бы использовать двоичную кучу в качестве помощника здесь. В двоичной куче, реализованной с использованием стандартной таблицы, с учетом индекса элемента мы можем легко вычислить индекс его родителя: int parent = (index-1)/2;. Зная это, нам нужно будет начать с начала нашего стола и сделать следующее:

1. Установить бинарное значение [0] на первое число из входного потока;

2. для всех остальных элементов во входном потоке:

   do{ 
       binaryHeap[heapIndex] = -1; 
       if (parent(heapIndex) = 1) 
         binaryHeap[heapIndex] = nextElementFromTheInputStream; 
       heapIndex++; 
       } 
       while(binaryHeap[heapIndex - 1] == 0); 
   

Так в основном, мы двигаемся через нашу таблицу. Мы инициализируем каждое поле (кроме root в 0) равным -1, что означает, что там нет узла. Затем мы проверяем, был ли родитель этого поля равным 1. Если бы это было так, то мы поместили следующий элемент из входного потока в наш текущий индекс в куче (heapIndex). Если родительский элемент текущего поля равен 0, мы просто идем дальше, потому что это означает, что наш родитель является листом и не должен иметь никаких детей.

Затем мы можем запустить алгоритм пост-заказа в куче (возможно, стоит реализовать некоторый код безопасности, так что в выходной поток не будет помещен элемент с «-1». Просто интерпретируйте leftChild (heapIndex) = = -1 или rightChild (heapIndex) == -1, для NULL).

Этот алгоритм, вероятно, довольно неэффективен с точки зрения памяти, но я надеюсь, что это очень легко понять.

Answer 4

Берем пример заказа уровня обходе - 111001000 дерево будет выглядеть следующим образом

 A 
    / \ 
    B  C 
    /\  /\ 
D E F G 
     /\ 
     H I 

Логика заключается в следующем.

1) Возьмите первый бит, если его 1 (корень) - затем следующий 2^1 - значения детей этого родителя. Таким образом, 2-й и 3-й бит являются childern из A (root).

2) Переход к следующему бит (1 для B), поскольку его значение равно 1, оно также имеет 2 детей, а затем следующий бит (1 для C), который также имеет 2 детей. Второй уровень завершен, и поскольку у нас есть 2 1, поэтому 2^2 следующие разряды для уровня 3.

3) 001000 так что мы прошли, а следующие 4 бит - дети третьего уровня. 4-й и 5-й бит равны 0 (D и E - листовые узлы и не имеют детей). Это будут дети из B), а затем F имеет значение бит 1, поэтому 1110010 (жирные цифры) будут дочерними элементами F. 7-й бит 0, и поэтому G также будет листовым узлом.

4) Снова перебрать или попробовать recusion - С 4-го, 5-й и 6-й и 7-й бит только один бит равен 1, так следующие 2^1 бит будет в следующем уровне, и те будут дети F.

После создания дерева преобразование в PostFix легко.

Answer 5

Одно из возможных решений (менее чем за час):

import java.util.ArrayList; 
import java.util.List; 

public class Main { 

    private static class Node { 
     private Node left; 
     private Node right; 
    } 

    private static Node buildTree(String input) { 
     char chars[] = input.toCharArray(); 
     if (chars.length == 0) { 
      return null; 
     } else { 
      Node root = new Node(); 
      List<Node> nodeList = new ArrayList<Node>(); 
      nodeList.add(root); 
      int pos = 0; 
      while (!nodeList.isEmpty()) { 
       List<Node> nextList = new ArrayList<Node>(); 
       for (Node n: nodeList) { 
        if (pos >= chars.length) { 
         throw new RuntimeException("Invalid input string"); 
        } 
        char c = chars[pos++]; 
        if (c == '1') { 
         n.left = new Node(); 
         n.right = new Node(); 
         nextList.add(n.left); 
         nextList.add(n.right); 
        } else if (c != '0') { 
         throw new RuntimeException("Invalid input string"); 
        } 
       } 
       nodeList = nextList; 
      } 
      return root; 
     } 
    } 

    private static String postTraverse(Node n) { 
     if (n == null) { 
      return ""; 
     } else if (n.left == null && n.right == null) { 
      return "0"; 
     } else { 
      return postTraverse(n.left) + postTraverse(n.right) + "1"; 
     } 
    } 

    public static void main(String[] args) { 
     Node tree = buildTree(args[0]); 
     System.out.println(postTraverse(tree)); 
    } 
} 

Answer 6

Вот довольно простое решение. Не совсем оптимально с
уважение к памяти, хотя я создаю полное/полное дерево сначала
, а затем я отмечаю, какие узлы фактически существуют в нашем дереве. Значит, это
может быть оптимизировано.

import java.util.HashMap; 
    import java.util.LinkedList; 
    import java.util.Queue; 

    class Node { 
     public Node left; 
     public Node right; 
     public Integer id; 
     public boolean exists; 
    } 

    public class Test32 { 

     public static void main(String[] args) { 
      HashMap<Integer, Node> mp = new HashMap<Integer, Node>(); 

      String str = "110101000"; 
      int sz = (int)Math.pow(2, str.length() + 1); 

      for (int i=0; i<sz; i++){ 
       Node nd = new Node(); 
       nd.id = i; 
       mp.put(nd.id, nd); 
      } 

      for (int i=0; i<sz; i++){ 
       Node nd = mp.get(i); 
       if (2*i < sz) nd.left = mp.get(2*i + 1); 
       if (2*i + 1 < sz) nd.right = mp.get(2*i + 2); 
      } 

      Queue<Integer> visit = new LinkedList<Integer>(); 
      visit.add(0); // id = 0; 

      int j = 0; 
      int id = -1; 
      while (!visit.isEmpty()){ 
       id = visit.poll(); 
       if (str.charAt(j) == '1'){ 
        mp.get(id).exists = true; 
        visit.add(2*id + 1); 
        visit.add(2*id + 2); 
       }else{ 
        mp.get(id).exists = true; 
       } 
       j++; 
      } 

      System.out.println("NODES:"); 
      for (int i=0; i<sz; i++){ 
       if (mp.get(i).exists){ 
        System.out.println(i); 
       } 
      } 

      System.out.println(); 
      System.out.println("EDGES:"); 
      for (int i=0; i<sz; i++){ 
       if (mp.get(i).exists){ 
        if (mp.get(2 * i + 1).exists){ 
         System.out.println(i + " --> " + (2*i+1)); 
        } 
        if (mp.get(2 * i + 2).exists){ 
         System.out.println(i + " --> " + (2*i+2)); 
        } 
       } 
      } 

     } 

    } 

И вот то же решение упрощенного издания.
Нет деревьев или карт, всего лишь булевский массив. Если какой-то узел
k имеет детей, то эти дети 2 * k + 1 и 2 * k + 2.
В последнем цикле при печати краев также можно построить
фактическое двоичное дерево.

import java.util.LinkedList; 
    import java.util.Queue; 

    public class Test32 { 

     public static void main(String[] args) { 

      String str = "110101000"; 
      int sz = (int)Math.pow(2, str.length() + 1); 
      boolean exists[] = new boolean[sz]; 

      Queue<Integer> visit = new LinkedList<Integer>(); 
      visit.add(0); // id = 0; 
      if (str.charAt(0) == '1'){ 
       exists[0] = true; 
      } 

      int j = 0; 
      int id = -1; 
      while (!visit.isEmpty()){ 
       id = visit.poll(); 
       if (str.charAt(j) == '1'){ 
        exists[id] = true; 
        visit.add(2*id + 1); 
        visit.add(2*id + 2); 
       }else{ 
        exists[id] = true; 
       } 
       j++; 
      } 

      // System.out.println(""); 
      System.out.println("NODES:"); 
      for (int i=0; i<sz; i++){ 
       if (exists[i]){ 
        System.out.println(i); 
       } 
      } 

      System.out.println(""); 
      System.out.println("EDGES:"); 
      for (int i=0; i<sz; i++){ 
       if (exists[i]){ 
        if (exists[2*i+1]){ 
         System.out.println(i + " --> " + (2*i+1)); 
        } 
        if (exists[2*i+2]){ 
         System.out.println(i + " --> " + (2*i+2)); 
        } 
       } 
      } 

     } 

    }