java - 回溯没有可变成员的树

Question

我正在尝试创建一个递归树，以便 parent 引用 child 并且 child 引用 parent.我想做的事情是从不带可变成员的 child 回溯树。这很困难，因为在构造函数中为子级提供对 parent 的引用需要已经创建 parent 实例。

我只能想到两种方法，但都不太好。第一种方式如下

1. 使用函数“setParent()”创建子实例，该函数在私有(private) boolean 变量的帮助下只能运行一次。
2. 创建父实例并传递子实例。
3. 父级会将自身传递给“setParent()”。

此后，child 会引用parent，并且无法使用 setParent()。

第二种方法是完全独立地创建parent和child，但将它们保存在某种数据结构中，该数据结构可以搜索parent一些 child 和其他 child 周围。

如果有更好的方法请教我。我主要用java工作，但问题很普遍。

Answer 1

有多种方法可以做到这一点，但我可能会给父级一个 createChild 方法，该方法创建一个新节点，将自身作为父级传递，并在返回之前将此子级添加到自身。你在问题中暗示，由于某种原因，拥有一个预先存在的 parent 是很困难的，但如果你要造一棵树，你应该知道谁的 parent 是谁。如果不这样做，树可能不是您正在寻找的数据结构。

我可能会对其进行构造，以便您的 Element 构造函数可以采用另一个 Element。如果是这样，它会为其他 Element 设置一个私有(private)变量 (parent)。如果它是在没有传入父元素的情况下创建的，那么它永远不会有父元素。所以这个类可能看起来像这样(显然省略了访问器和任何其他东西):

public class Element {

    private Element parent;
    private ArrayList<Element> children;

    // Constructor for a node with NO parent
    public Element() {
        this(null);
    }

    // Constructor for a node WITH a parent
    public Element(Element parent) {
        this.parent = parent;
        this.children = new ArrayList<Element>();
    }

    // Method to create a child element.
    public Element createChild() {
        Element ch = new Element(this);
        this.children.add(ch);
        return ch;
    }
}

<小时/>

如果您的问题是您试图通过从子级追溯到某个祖先来构建一棵“树”，那么我鼓励您注意这实际上是一个列表，而不是一棵树。您可以从下到上创建列表，然后从列表末尾开始从上到下构建树。