java - 结构不同的树java

我已经为此工作了几个星期，却一无所获。我正在尝试制作一个将2个整数n和k作为输入的应用程序。
应用程序应生成并输出具有i个在结构上不同的节点的所有树的数量。最后，它应输出具有n个节点的第k个树。

我有一个例子：

在终端中输入以下内容：

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

我发现数字像加泰罗尼亚语数字一样在增加，但无法弄清楚如何获得输出

我在这里先向您的帮助表示感谢。

最佳答案

首先，还需要一些其他信息。即：


允许的树形式是什么？从给定的类来看，它是一棵二叉树，其中每个节点被允许具有0、1或2个子节点，因此我将遵循这一假设。
什么构成“结构上不同的树”？彼此镜像相同的两棵树在结构上是否不同？如果两棵树不完全相同，我将假设它们在结构上是不同的。


考虑到这一点，最好的方法是使用某种深度优先或宽度优先的算法构造每个i个节点的树。以具有4个节点的树的所有形式为例。如果要深度优先，这意味着您将首先研究根节点仅具有左子节点的所有形式。然后，您将以这种方式继续操作，直到到达三个节点。由于我懒于启动图形程序，因此我将以纯ASCII格式显示。图像每个斜杠连接两个不可见节点：

1:  /
   /
  /

所以我们有left-left-left。下一个变化是通过更改最后一个决定而得到的，从而导致left-left-right：

2:  /
   /
   \

下一个变化是在末尾同时具有左右两个子节点，但是由于那样会给我们提供大小为5的树，因此我们无法这样做。现在，我们已经用尽了所有选项，因此我们将返回到倒数第二个节点。我们最初是为此选择left的，所以现在我们选择right并从那里继续算法：

3:  /   4:  /
    \       \
    /        \

看看我们做了什么？我们为第二个节点做出了不同的选择，然后从那里研究了所有剩余的变化。就像在1和2中一样。

好了，选项再一次用尽了，所以我们必须退后一步。我们已经研究了第二个节点的左右方向。这次还有另一个选择：第二级的两个子节点：

5:  /
   /\

在继续阅读之前，请尝试遵循此逻辑，并按照您认为会逐步展开的步骤进行操作。记住逻辑：制作一个左节点并构造所有子树，制作一个右节点并构造所有子树，同时制作两个（如果不超过限制）并构造所有子树。一旦所有选项都用尽，请返回一个步骤并从那里更改。

这是其余的：

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

14种表格。谢天谢地，它签出了。

请记住，这是深度优先算法。我们会更深入，直到达到节点限制，然后再退一步并做出另一选择，依此类推，直到这些选项用尽。然后，我们再退一步。如果您要使用广度优先，则始终应尽可能返回并选择其他选项。我将向您展示广度优先的前三个步骤：

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

只需将广度优先的样本作为参考即可。还要注意，我的深度优先顺序“左，右，两者”有些武断。您最好也选择“右，左，两者”。

那么，如何实际将其转换为代码呢？好吧，观察一下做出决定（左，右，两者）之后，树形结构的其余部分如何从那里延伸。您可能会说您再次遇到相同的问题，但是现在是一棵较小的树。

回到深度第一步。考虑一下它是如何构造的。我们有一个根节点。这是一回事，所以剩下3个节点要分配。从那里，我们必须做出选择。我们最初的选择是只生一个左孩子。这意味着我们现在可以忽略正确的子树。从那个孩子开始，我们现在遇到了构造具有3个节点的所有树的问题，其中根节点就是那个孩子。再次，我们选择仅添加一个左孩子的选项。这就带来了构造所有大小为2的树的问题。

这被称为递归问题。为了找到i的解决方案，我们必须知道i-1的解决方案。为了停止递归，必须有一些不依赖早期结果的基础。在我们的例子中，i=1是一个简单的解决方案：只有一个节点。

因此，这意味着您可以编写一段代码，通过将自身与参数i一起使用来找到所有大小为i-1的树形式。为避免无限循环，请在i=1处停止递归。为了检查当前树的大小以避免破坏节点限制，您可以使用那里的size()方法。请注意，这本身是一种递归方法：它利用自身来计算结果。其他方法也可能有用，但是我认为您不需要所有这些方法。

选择深度优先还是宽度优先由您决定。尝试考虑如何将两者都表示为算法以及编程流程的要求。深度优先比广度优先容易实现吗？

我希望我的ASCII废话是可以理解的，并且我不会太谦虚。我不知道您对这个问题有多远，也没有关注什么。树是一种常见的数据结构，而走树的深度或广度优先（例如在搜索算法中）是常见的算法，因此，如果IT是您的主要职业，那么希望看到更多的树。看到分配如何结束，但您仍然想找出解决方案，我相信您会学得很好。

让我们知道您是否已找到如何在代码中进行操作。如果您仍然遇到问题，我会尽力记得稍后再发布（可能是部分的）解决方案。

关于java - 结构不同的树java，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7802517/