Структурные Разные деревья Ява

Question

Я работаю над этим уже пару недель и не знаю, где вообще. Я пытаюсь сделать приложение, которое принимает в качестве входных данных 2 целых числа n и k . Приложение должно сгенерировать и вывести количество всех деревьев с i узлами, которые являются структурно различными. В конце он должен вывести k-е дерево с n узлами.

У меня есть пример:

В терминологии введено следующее:

java differentTrees 5 31

и результат:

The number of structural different trees with 0 nodes is 0
The number of structural different trees with 1 nodes is 1
The number of structural different trees with 2 nodes is 2
The number of structural different trees with 3 nodes is 5
The number of structural different trees with 4 nodes is 14
The number of structural different trees with 5 nodes is 42
<BinaryTreeNode 5 <BinaryTreeNode 1 --> <BinaryTreeNode 3 <BinaryTreeNode 2 <BinaryTreeNode 1 -->->->>

Я должен использовать код из класса BinaryTreeNode:

import java.lang.Math;

public class BinaryTreeNode
{
protected Object val; // value associated with node
protected BinaryTreeNode parent; // parent of node
protected BinaryTreeNode left; // left child of node
protected BinaryTreeNode right; // right child of node

public BinaryTreeNode(Object value)
// post: returns a tree referencing value with two null subtrees
{
    val = value;
    parent = left = right = null;
}

public BinaryTreeNode(Object value,
                      BinaryTreeNode left,
                      BinaryTreeNode right) 
// post: returns a node referencing value & subtrees
{
    this(value);
    setLeft(left);
    setRight(right);
}

public BinaryTreeNode left()
// post: returns reference to left subtree, or null
{
    return left;
}

public BinaryTreeNode right()
// post: returns reference to right subtree, or null
{
    return right;
}

public BinaryTreeNode parent()
// post: returns reference to parent node, or null
{
    return parent;
}

public void setLeft(BinaryTreeNode newLeft)
// post: sets left subtree to newLeft
//       re-parents newLeft if not null
{
    if (left != null &&
        (left.parent() == this)) left.setParent(null);
    left = newLeft;
    if (left != null) left.setParent(this);
}

public void setRight(BinaryTreeNode newRight)
// post: sets left subtree to newRight
//       re-parents newRight if not null
{
    if (right != null &&
        (right.parent() == this)) right.setParent(null);
    right = newRight;
    if (right != null) right.setParent(this);
}

protected void setParent(BinaryTreeNode newParent)
// post: re-parents this node to parent reference, or null
{
    parent = newParent;
}

public static int size(BinaryTreeNode n)
// post: returns the size of the subtree rooted at n
{
    if (n == null) return 0;
    return size(n.left()) + size(n.right()) + 1;
}

public static BinaryTreeNode root(BinaryTreeNode n)
// post: returns the root of the tree node n
{
    if ((n == null) || (n.parent() == null)) return n;
    else return root(n.parent());
}

public static int height(BinaryTreeNode n)
// post: returns the height of a node n in its tree
{
    if (n == null) return -1;
    return 1 + Math.max(height(n.left()),height(n.right()));
}

public static int depth(BinaryTreeNode n)
// post: returns the depth of a node in the tree
{
    if (n == null) return -1;
    return 1 + depth(n.parent());
}

public static boolean isFull(BinaryTreeNode n)
// post: returns true iff the tree rooted at n is full.
{
    if (n == null) return true;
    if (height(n.left()) != height(n.right())) return false;
    return isFull(n.left()) && isFull(n.right());
}

public static boolean isComplete(BinaryTreeNode n)
// post: returns true iff the tree rooted at n is complete
{
    int leftHeight, rightHeight;
    boolean leftIsFull, rightIsFull;
    boolean leftIsComplete, rightIsComplete;
    if (n == null) return true;
    leftHeight = height(n.left());
    rightHeight = height(n.right());
    leftIsFull = isFull(n.left());
    rightIsFull = isFull(n.right());
    leftIsComplete = isComplete(n.left());
    rightIsComplete = isComplete(n.right());

    // case 1: left is full, right is complete, heights same
    if (leftIsFull && rightIsComplete &&
        (leftHeight == rightHeight)) return true;
    // case 2: left is complete, right is full, heights differ
    if (leftIsComplete && rightIsFull &&
        (leftHeight == (rightHeight + 1))) return true;
    return false;
}

public static boolean isBalanced(BinaryTreeNode n)
// post: returns true iff the tree rooted at n is balanced
{
    if (n == null) return true;
    return (Math.abs(height(n.left())-height(n.right())) <= 1) &&
           isBalanced(n.left()) && isBalanced(n.right());
}

public boolean isLeftChild()
// post: returns true if this is a left child of parent.
{
    if (parent() == null) return false;
    return this == parent().left();
}

public boolean isRightChild()
// post: returns true if this is a right child of parent.
{
    if (parent() == null) return false;
    return this == parent().right();
}

public Object value()
// post: returns value associated with this node.
{
    return val;
}

public void setValue(Object value)
// post: sets the value associated with this node
{
    val = value;
}

public String toString()
// post: returns string representation
{
    StringBuffer s = new StringBuffer();
    s.append("<BinaryTreeNode "+value());
    if (left != null) s.append(" "+left());
    else s.append(" -");
    if (right != null) s.append(" "+right());
    else s.append(" -");
    s.append('>');
    return s.toString();
}
}

Я узнал, что числа растут как каталонские, но не могу понять, как получить результат

Заранее спасибо за помощь.

Answer 1

Прежде всего, есть пара дополнительных сведений, которые могут понадобиться.А именно:

• Какая разрешенная форма дерева?Судя по данному классу, это двоичное дерево, в котором каждому узлу разрешено иметь 0, 1 или 2 дочерних узла, поэтому я пойду с этим предположением.
• Что представляет собой «структурно отличающееся дерево»?Являются ли два дерева, которые являются зеркальным отражением друг друга, структурно различными?Я предполагаю, что два дерева структурно различны, если они не полностью идентичны.

С учетом этого наилучшим подходом было бы построить каждое дерево размером i узлов с использованием некоторой глубины.-первый или широкий-первый алгоритм.Возьмем, к примеру, все формы дерева, которое имеет 4 узла.Если вы идете вглубь, это означает, что вы сначала исследуете все формы, в которых корневой узел имеет только левого потомка.Затем вы будете продолжать в том же духе, пока не дойдете до трех узлов.Я собираюсь показать это в простом ASCII, так как мне лень запускать графическую программу.Изображение каждого слэша соединяет два невидимых узла:

1:  /
   /
  /

Таким образом, у нас слева направо.Следующий вариант получается путем изменения этого последнего решения, приводя к лево-лево-правому:

2:  /
   /
   \

Следующим вариантом будет иметь как левый, так и правый дочерний узел в конце, но так как это будетдайте нам дерево размером 5, мы не можем этого сделать.Мы исчерпали наши возможности, поэтому вернемся на один шаг к предпоследнему узлу.Изначально мы выбрали левую для этого, так что теперь мы идем с правой и продолжим алгоритм оттуда:

3:  /   4:  /
    \       \
    /        \

Видите, что мы сделали?Мы сделали другой выбор для второго узла, а затем исследовали все остальные варианты оттуда.Как и в 1 и 2.

Хорошо, варианты снова исчерпаны, поэтому мы должны вернуться на шаг назад.Мы исследовали влево и вправо для второго узла.На этот раз остался еще один вариант: два дочерних узла на втором уровне:

5:  /
   /\

Прежде чем продолжить чтение, попробуйте следовать этой логике и нарисуйте следующие шаги, поскольку вы считаете, что они развернутся.Запомните логику: создайте левый узел и создайте все поддеревья, сделайте правый узел и создайте все поддеревья, создайте оба (если это не превышает предел) и создайте все поддеревья.Как только все опции исчерпаны, вернитесь на шаг и измените их.

Вот остаток:

6:  \   7:  \   8: \   9: \   10: \   11: /\   12: /\   13: /\   14: /\
    /       /       \      \      /\     /         \         /         \
   /        \       /       \

14 форм.Слава Богу, все получилось.

Имейте в виду, что это алгоритм первой глубины.Мы углубляемся, пока не достигнем предела нашего узла, затем вернемся на один шаг назад и сделаем другой выбор, и так далее, пока эти опции не будут исчерпаны.Тогда мы вернемся еще на один шаг.Если бы вы использовали ширину в первую очередь, вы всегда возвращались бы как можно дальше назад и выбирали другой вариант.Я покажу вам первые три шага в ширину:

1:  /   2:  \   3:  /\
   /        /      /
  /        /

Просто рассмотрите образец в ширину как информационный.Также обратите внимание, что мой первый порядок глубины «влево, вправо, оба» несколько произвольный.С таким же успехом вы могли бы использовать «правый, левый, оба».

Итак, как вы на самом деле превращаете это в код?Что ж, понаблюдайте, как после того, как вы приняли решение (слева, справа, оба), оттуда расширяются остальные формы дерева.Можно сказать, что вы снова столкнулись с той же проблемой, но теперь для дерева меньшего размера.

Вернитесь к первому шагу глубины 1. Подумайте, как оно было построено.У нас есть корневой узел.Это один из способов, так что 3 узла еще предстоит выделить.Оттуда мы должны сделать выбор.Наш первоначальный выбор был сделать только левым ребенком.Это означает, что мы можем на данный момент игнорировать правильное поддерево.Начиная с этого дочернего элемента, теперь у нас есть проблема построения всех деревьев с 3 узлами, корневым узлом которых является этот дочерний элемент.Еще раз, мы выбираем вариант добавления только левого потомка.И это подводит нас к проблеме построения всех деревьев размера 2.

Это известно как рекурсивная проблема.Чтобы найти решение для i, мы должны знать решение для i-1.Чтобы остановить рекурсию, должна быть какая-то основа, которая не опирается на более ранние результаты.В нашем случае это i=1, что является тривиальным решением: только один узел.

Таким образом, это означает, что вы можете написать фрагмент кода, который найдет все формы дерева размером i, используя себя с параметромi-1.Чтобы избежать бесконечного цикла, остановите рекурсию на i=1.Чтобы проверить размер вашего текущего дерева, чтобы не нарушить ограничение узла, вы можете использовать тот метод size(), который у вас есть.Обратите внимание, что сам по себе это рекурсивный метод: он использует себя для вычисления результата.Другие методы также могут быть полезны, но я не думаю, что вам понадобятся все из них.

Независимо от того, выберете ли вы глубину или ширину, решать вам.Попробуйте подумать о том, как они будут выражаться в виде алгоритмов и требований к процессу программирования.Проще ли реализовать в глубину, чем в ширину?

Надеюсь, моя чепуха в ASCII была несколько понятной, и я не выгляжу слишком снисходительно.Я не знаю, как далеко вы продвинулись с этой проблемой или какие уроки вы изучаете.Деревья - это общая структура данных, а ходьба деревьев по глубине или ширине (например, в алгоритме поиска) является распространенным алгоритмом, поэтому ожидайте увидеть больше из этого, если ИТ - ваша основная задача.Видя, как закончилось задание, но вы все еще хотите найти решение, я уверен, что вы хорошо усвоите.

Дайте нам знать, узнаете ли вы, как это сделать в коде.Если у вас все еще есть проблемы, я постараюсь опубликовать (возможно частичное) решение через некоторое время.