Реализация недвоичного дерева с циклическими проверками

Question

Я искал хорошую реализацию недвоичного дерева, которая бы соответствовала моим потребностям, но я не нашел ее.

Мне нужно недвоичное дерево, в котором число дочерних элементов является произвольным, и это может быть пройдено.Это дерево построено на основе пользовательского ввода, поэтому мне нужно провести циклическую проверку.Другие функции включают в себя удаление узлов (и их дочерних элементов), обход для получения дочерних узлов (и дочерних элементов дочерних элементов) и добавление дочерних элементов (и других деревьев).

Примеры реализаций, которые я нашел в Интернете, включают использование метода firstchild-nextsibling и родительско-дочерних ссылок на узел.Проблема с методом firstchild-nextsibling заключается в добавлении деревьев и узлов в дерево.Метод parent-child кажется разумным, но я не нашел ни одной реализации, которая бы добавляла целые деревья в качестве дочерних и имела бы циклические проверки.

Пример такой реализации:

     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 (ориентированный ациклический граф).Вот некоторые свойства, которые отличают деревья от графов.

• В дереве:

  • ни один узел не имеет более одного родителя,
  • (точно) один узел является корнем дерева: у корневого узла нет родителя, и
  • для каждого дочернего элемента c узла n, n == c.parent ()

• В графе или группе обеспечения доступности баз данных некоторые узлы могут иметь более одного родителя и могут иметь несколько корневых узлов или не иметь корневых узлов.

Ясно в чистых данныхВ структурных терминах одни и те же репрезентативные типы могут представлять дерево, граф или группу обеспечения доступности баз данных, в зависимости от того, как вы их объединяете.Поэтому, чтобы убедиться, что ваша структура данных является деревом, вам необходимо поддерживать свойства, указанные выше.Это можно сделать, ограничив преобразование, которое вы можете выполнить, и наложив на них некоторые предварительные условия.Следующего должно быть достаточно:

• Добавить узел n1 как дочерний узел узла n2:

  • pre: n1 должен быть корневым узлом;т.е. n1.parent == null
  • pre: n2 должен быть частью дерева, отличного от n1;т.е. root (n2)! = n1
  • действие: установить n1.parent = n2
  • действие: добавить n1 к n2.children
  • post: parent (n1) = n2это означает, что root (n1) == root (n2)

• Удалить узел n1 из родительского узла n2:

  • pre: n1.parent== n2;то есть n1 не является корнем
  • post: n1 является корневым узлом.

Как видите, единственное, что вам нужно сделать, это проверить, что n1 и n2 не 't (уже) имеют одинаковый корень перед добавлением одного к другому;это можно сделать с помощью простой рекурсивной вспомогательной функции:

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

Если пользовательский интерфейс ограничен так, что все преобразования дерева состоят из операций вставки и удаления, как указано вышетогда инварианты тройника будут сохранены.

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;