Ошибка генераторного кода генерации

Question

Мой код, кажется, делает бесконечную рекурсию, когда я вызываю ее с деревьями большей глубины. Я пытался сделать это без рекурсии, и это очень сложно сделать, так как мне нужно манипулировать самим деревом, так или иначе, вот m-код. Благодаря

Проблема с методом printPostOrder, он попадает в узел листьев и идет вперед и назад печать этого узла листа и его родителей, пока стек не переполняется

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

вставки узла, как это

import java.util.*; 

public class IPG { 

    class Node { 

     private int arity; 
     private String label; 
     private int value; 
     private Node[] children; 
     protected int visit = 0; 
     protected boolean isVisited = false; 

     public Node(int arity, String label) { 
      this.arity = arity; 
      this.label = label; 
      this.children = new Node[3]; 
     } 

     public Node(Node another) { 
      this.label = another.label; 
      this.arity = another.arity; 
     } 

     @Override 
     public String toString() { 
      return label; 
     } 

     String getLabel() { 
      return label; 
     } 

     void insertChild(int pos, Node n) { 
      if (pos < arity) { 
       children[pos] = n; 
      } 
     } 

     Node getChildAt(int i) { 
      return children[i]; 
     } 

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

     int getArity() { 
      return arity; 
     } 

     void replace(Node another) { 
      this.arity = another.arity; 
      this.children = another.children; 
      this.label = another.label; 
     } 

    } 

    private Node[] functions = { new Node(2, "AND"), new Node(2, "OR"), 
      new Node(1, "NOT"), new Node(3, "IF") }; 

    private Node[] terminals = { new Node(0, "A0"), new Node(0, "D1"), 
      new Node(0, "D0"), new Node(0, "A1"), new Node(0, "D2"), 
      new Node(0, "D3"), new Node(0, "A2"), new Node(0, "D4"), 
      new Node(0, "D5"), new Node(0, "D6"), new Node(0, "D7") }; 

    private Random random = new Random(); 

    private int multiplexerType = 3; 

    public Node getTerminal() { 
     return terminals[random.nextInt(multiplexerType)]; 
    } 

    public Node getFunction() { 

     return functions[random.nextInt(3)]; 
    } 

    public Node getAnyNode() { 
     return random.nextInt(2) == 1 ? getFunction() : getTerminal(); 
    } 

    public Node generateGrow(int depth) { 
     Node root; 

     if (depth > 1) 
      root = getAnyNode(); 

     else 
      root = getTerminal(); 

     for (int i = 0; i < root.getArity(); i++) 
      root.insertChild(i, generateGrow(depth - 1)); 

     return root; 
    } 

    public Node generateFull(int depth) { 
     Node root; 

     if (depth > 1) 
      root = getFunction(); 

     else 
      root = getTerminal(); 

     for (int i = 0; i < root.getArity(); i++) 
      root.insertChild(i, generateFull(depth - 1)); 

     return root; 
    } 

    public void printPostOrder() { 
     Node root = generateFull(3); 
     printPostOrder(root); 
    } 

    private void printPostOrder(Node n) { 
     if (n == null) { 
      return; 
     } else { 
      System.out.println(n + " "); 

      printPostOrder(n.children[0]); 
      printPostOrder(n.children[1]); 
      printPostOrder(n.children[2]); 
     } 
    } 

    public static void main(String[] args) { 
     new IPG().printPostOrder(); 
    } 
} 

Answer 1

Проблема заключается в том, что при создании массива functions вы создаете только один узел каждого типа, а затем getFunction() повторно использует эти же узлы. Случается, что, если, например, вы вставляете узел «И», а его дочерний узел также является «И», создается цикл, потому что они фактически являются одним и тем же объектом.

Это легко исправить, вам просто необходимо убедиться, чтобы создать новый узел с каждым вызовом getFunction(), например так:

private String [] functionNames = {"AND", "OR", "NOT", "IF"}; 
private int [] functionArities = {2,2,1,3}; 

public Node getFunction() { 
    int index = random.nextInt(3); // If you want to use "IF" nodes too this 
            // needs to be nextInt(4) 
    return new Node(functionArities[index],functionNodes[index]); 
} 

Answer 2

Существует вероятность того, что граф является циклической. Просто потому, что вы используете предварительно созданные узлы и произвольно выбираете их. Чем глубже узел, тем выше вероятность того, что один узел вставлен более одного раза. И в этом случае у вас есть свой цикл, и JVM жалуется на SSO.

Корень вашей проблемы - это массив functions (terminals в порядке, потому что терминальный узел не имеет детей).

Удалите этот массив и создайте объект функции для каждого узла.