具有循环检查的非二叉树实现

Question

我一直在寻找一个符合我需求的好的非二叉树实现，但没有找到。

我需要一个非二叉树，其中子树的数量是任意的，并且可以遍历。此树是由用户输入构建的，因此我需要进行循环检查。其他功能包括删除节点（及其子节点）、遍历以获取节点的子节点（以及子节点的子级）和添加子节点（和其他树）。

我在网上找到的实现示例包括使用firstchild-nextsibling方法和到节点的父子链接。firstchild nextsibling方法的问题是向树中添加树和节点。父子方法看起来很合理，但我还没有发现任何将整个树添加为子树并进行循环检查的实现。

这种实现的一个例子：

     A
   /   \
  U     W

然后，用户选择创建另一棵树：

  B
 /  \
X    R

然后将 B 添加为 W 的子项。完整的树将是：

    A
  /   \
 U      W
         \
           B
          /  \
         X     R

如果有更好的方法来实现这种数据结构，那么我会很高兴听到它，因为我想不出别的。任何帮助将不胜感激。谢谢！

编辑：我写的一些代码。

public class TreeNode<T> {

private T data;
private TreeNode<T> firstChild;
private TreeNode<T> nextSibling;
private TreeNode<T> parent;
public TreeNode(T data) {
    this.data = data;
}

public boolean isRoot() {
    return this.parent == null;
}
public boolean isaLeaf() {
    return this.firstChild == null;
}

public TreeNode<T> getFirstChild(){
    return firstChild;
}
public void addChild(TreeNode<T> child) {
    child.parent = this;
    if (this.firstChild == null) {
        this.firstChild = child;
    } else {
        child.nextSibling = firstChild;
        firstChild = child;
    }
}

public TreeNode<T> getParent(){
    return parent;
}

public TreeNode<T> getNextSibling() {
    return nextSibling;
}

public T getData() {
    return data;
}

}

编辑2：我的树允许添加类似的节点，但它不允许创建一个无限循环。这种循环的一个例子是添加W作为R的子节点。我在考虑将每个级别作为链表以便于排序，但我不确定这是否有任何意义。有什么想法吗？

Answer 1

我假设你的意图是让数据结构成为一棵树，而不是一个DAG（有向无环图）。下面是一些将树与图形区分开来的属性。

> < li>

在树上:

< li >没有一个节点有多个父节点， < li >(恰好)一个节点是树的根:根节点没有父节点，并且 < li >对于节点n的每个子c，n == c.parent()

在图或DAG中，某些节点可能有多个父节点，并且可能有多个根节点，或者没有根节点。

显然，在纯数据结构术语中，相同的表示类型可以表示树、图或DAG，具体取决于如何将它们组合在一起。因此，为了确保数据结构是一棵树，您需要维护上面的属性。这可以通过限制可以执行的转换并对其设置一些先决条件来实现。以下内容应足够：

> < li>

将节点n1添加为节点n2的子节点:

< li>pre: n1必须是根节点；即n1.parent == null < li>pre: n2必须是n1的不同树的一部分；即root(n2)！= n1 < li >操作:设置n1.parent = n2 < li >操作:将n1添加到n2.children中 < li>post: parent(n1) = n2，这意味着root(n1) == root(n2)

从父节点n2中删除节点n1：

• pre:n1.parent==n2；i、 e.n1不是根
• 上一篇：n2.children包含n1
• 操作：将n1.parent设置为空
• 操作：从p2中删除n1。儿童
• post:n1是根节点

如您所见，您需要做的唯一稍微有点棘手的事情是在将一个添加到另一个之前检查n1和n2是否（已经）具有相同的根；这可以使用一个简单的递归帮助函数来完成：

  TreeNode root(TreeNode n) {
      return (n.parent == null) ? n : root(n.parent);
  }

然后

  void add(TreeNode n1, Tree node n2) {
      if (root(n1) != n1 || n1 == root(n2)) {
          throw new BadTreeTransformation(...);
      }

如果限制用户界面，以便所有树转换都由上述插入和删除操作组成，则将保留 T 恤不变量。

Answer 2

您可以将循环检查添加到 addChild 方法中：

public void addChild(TreeNode<T> child) {
    if (!child.isRoot()) {
        throw new IllagalArgumentException();
    }
    TreeNode myRoot = this;
    while (!myRoot.isRoot()) {
        myRoot = myRoot.parent();
    }
    if (child == myRoot) {
        throw new IllagalArgumentException();
    }
    // now we can safely set parent
    child.parent = this;