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

问题描述

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

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

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

这种实现的一个例子：

     A
   /   \
  U     W

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

  B
 /  \
X    R

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

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

编辑：我写的一些代码。

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 的子级。我正在考虑将每个级别作为链接列表以便于排序，但我不确定这是否有意义。有什么想法吗？

标签： javadata-structurestree

解决方案

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

在树中：
- 没有节点有多个父节点，
- （确切地说）一个节点是树的根：根节点没有父节点，并且
- 对于节点 n 的每个子 c，n == c.parent()
在图或 DAG 中，某些节点可能有多个父节点，并且可能有多个根节点，或者没有根节点。

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

添加节点 n1 作为节点 n2 的子节点：
- pre: n1 必须是根节点；即 n1.parent == null
- pre：n2 必须是与 n1 不同的树的一部分；即根（n2）！= n1
- 动作：设置 n1.parent = n2
- 行动：将 n1 添加到 n2.children
- post: parent(n1) = n2 这意味着 root(n1) == root(n2)
从父节点 n2 中删除节点 n1：
- 前：n1.parent == n2；即 n1 不是根
- pre: n2.children 包含 n1
- 行动：将 n1.parent 设置为 null
- 行动：从 p2.children 中删除 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(...);
      }

如果您限制用户界面以使所有树转换都由上述插入和删除操作组成，那么将保持 tee 不变量。

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

问题描述

解决方案

推荐阅读