树实现抛出 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);

这会抛出一个 WhosebugError，因为我们陷入了循环 setParent - addChild.

我尝试了另一种方式：

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

但是，childNode.parent.children 为空，我希望其中包含 childNode。

我怎样才能做到这一点？

Answer 1

您有一个 Whosebug 异常，因为您的 "addChild" 方法调用了您的 "setParent" 方法，而您的 "setParent" 方法调用了 "addChild"

Answer 2

我认为你应该把递归排除在外，并在应用层处理父子关系的一致性（即一起使用 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 3

setParent 和 addChild 正在互相呼叫。为了保持对 addChild 或 setParent 的调用都有效，一个选项是创建一个 setParentInternal 私有方法，由 addChild 调用而不是 public setParent.

请注意，我还重构了 addChild 以减少冗余并初始化了子列表。

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);
    }
}

树实现抛出 StackOverflowError

Tree implementation throwing a StackOverflowError

java

tree