реализация Дерево бросает StackOverflowError

Question

У меня есть дерево:

public class Node<T> { 
    private T data; 
    private Node<T> parent; 
    private Map<T, Node<T>> children; 

    public Node(T data, Node<T> parent) { 
     this.data = data; 
     this.parent = parent; 
    } 

    public Node(T data) { 
     this.data = data; 
    } 

    public boolean hasChildren() { 
     if (this.children != null) { 
      return this.children.size() > 0; 
     } 
     return false; 
    } 

    public void setParent(Node<T> parent) { 
     parent.addChild(this); 
     this.parent = parent; 
    } 

    public void addChild(T data) { 
     Node<T> child = new Node<T>(data); 
     child.setParent(this); 
     this.children.put(child.data, child); 
    } 

    public void addChild(Node<T> child) { 
     child.setParent(this); 
     this.children.put(child.data, child); 
    } 
} 

Затем я пытаюсь заполнить это следующим образом:

Node<String> parentNode = new Node<String>("Parent"); 
Node<String> childNode = new Node<String>("Child"); 
childNode.setParent(parentNode); 

Это бросает StackOverflowError, потому что мы застряли в SetParent петли - addChild.

Я попробовал другой путь:

Node<String> parentNode = new Node<String>("Parent"); 
Node<String> childNode = new Node<String>("Child", parentNode); 

Однако childNode.parent.children имеет нулевое значение, и я хотел бы, чтобы иметь childNode в нем.

Как я могу это достичь?

Answer 1

Я думаю, вы должны принять рекурсии из картины и обрабатывать последовательность parent-child в прикладном уровне (т.е. используйте childNode.setParent(parentNode); и parentNode.addChild(parentNode); вместе). Вы можете использовать код ниже, он будет работать в обоих направлениях.

public class Node<T> { 
private T data; 
private Node<T> parent; 
private Map<T, Node<T>> children; 

public Node(T data, Node<T> parent) { 
    this.data = data; 
    this.parent = parent; 
    parent.addChild(this); 
} 

public Node(T data) { 
    this.data = data; 
} 

public boolean hasChildren() { 
    if (this.children != null) { 
     return this.children.size() > 0; 
    } 
    return false; 
} 

public void setParent(Node<T> parent) { 
    this.parent = parent; 
} 

public void addChild(T data) { 
    Node<T> child = new Node<T>(data); 
    this.children.put(child.data, child); 
} 

public void addChild(Node<T> child) { 
    this.children.put(child.data, child); 
} 

}

Answer 2

У вас есть исключение StackOverflow, потому что ваш метод «AddChild» называют свой метод «SetParent» и ваш «SetParent» вызов метода «AddChild»

Answer 3

setParent и addChild призывают друг друга. Для того, чтобы оба вызова addChild или setParent были действительными, необходимо было бы создать частный метод setParentInternal, вызываемый addChild, а не общественностью setParent.

Обратите внимание, что я также реорганизовал addChild, чтобы уменьшить reduncuncy и инициализировать список детей.

public class Node<T> { 
    private T data; 
    private Node<T> parent; 
    private Map<T, Node<T>> children= new HashMap<T, Node<T>>(); 

    public Node(T data, Node<T> parent) { 
     this.data = data; 
     this.parent = parent; 
    } 

    public Node(T data) { 
     this.data = data; 
    } 

    public boolean hasChildren() { 
     if (this.children != null) { 
      return this.children.size() > 0; 
     } 
     return false; 
    } 

    private void setParentInternal(Node<T> parent) { 
     this.parent = parent; 
    } 

    public void setParent(Node<T> parent) { 
     parent.addChild(this); 
     setParentInternal(parent); 
    } 

    public void addChild(T data) { 
     addChild(new Node<T>(data)); 
    } 

    public void addChild(Node<T> child) { 
     child.setParentInternal(this); 
     this.children.put(child.data, child); 
    } 
}