二叉树的枚举

二叉树的枚举可以定义为从给定的节点数或二叉树创建的不同二叉树的数量。这些不同的二叉树可以根据二叉树节点的标记而有所不同。取决于二叉树中存在的节点的标记，二叉树有两种类型：

1. 标记二叉树：标记二叉树中的所有节点都带有正确的标记。这意味着标记二叉树中的所有节点都按特定顺序或序列排列。
2. 未标记二叉树：在未标记二叉树中，节点没有特定的标记。二叉树中节点的顺序或序列无关紧要，因为没有特定参数可以区分二叉树的各个节点。

这两种不同的类型具有不同类型的二叉树枚举。

标记二叉树的枚举

标记二叉树的枚举可以定义为从给定的标记二叉树或一组标记节点形成的无标记二叉树的数量。

标记二叉树枚举与无标记二叉树枚举的主要区别在于，对于给定的节点数，无标记树中创建的新树只有一个结构，但在标记树中，具有相同节点数的树会有两个不同，因为节点在树中的位置可以与所有节点不同，而不是相同的。

让我们通过一个例子来理解无标记二叉树的枚举。

假设我们有一组包含三个节点的节点，分别命名为节点 1、节点 2 和节点 3。

第一轮，我们考虑 N=1，其中 n 表示创建一棵具有一个节点的二叉树的节点数。树将如下所示：

现在我们考虑 N=2，这意味着我们有节点 1 和节点 2 来形成二叉树。因此，使用两个节点，我们可以创建四种不同的二叉树。

对于 N=2，形成了两种不同的二叉树。这两棵树看起来像：

在上面的树中，我们有四棵树，具体取决于节点在树中的位置。有两种左倾斜树和两种右倾斜树。

• 在第一棵左倾斜树中，节点 1 是根节点，节点 2 是左子节点。而在第二棵左倾斜树中，节点 2 是左倾斜二叉树的根节点，节点 1 是其左子节点。
• 同时，两棵右倾斜二叉树具有相同数量的节点，只是它们在树中的位置不同。在第一棵右倾斜二叉树中，节点 1 是二叉树的根节点，节点 2 是树的子节点。而在第二棵右倾斜二叉树中，节点 2 是二叉树的根节点，节点 1 是树的子节点。

因此，对于两个标记节点，创建了四棵不同的树。同样，对于三个标记节点，可以创建三十种不同的（不同的）二叉树。

因此，要计算三个节点的枚举：

对于 N=1，不同标记树的数量 = 1

对于 N=2，不同标记树的数量 = 4

对于 N=3，不同标记树的数量 = 30

以下是根据节点数对所有这些不同二叉树数量求和的公式。

其中 N 是节点数。

让我们计算 N=3 的情况：

因此，对于三个标记节点，我们可以创建三十种不同的树。

C++ 代码

让我们编写一个 C++ 代码来查找从给定一组标记节点创建的不同标记二叉树的数量。

输出

上述代码的输出是

The number of Distinct labelled Binary Tree is 30

Java 代码

让我们编写一个 Java 代码来查找从给定一组标记节点创建的不同标记二叉树的数量。

无标记二叉树的枚举

无标记二叉树的枚举可以定义为从给定的无标记二叉树或一组无标记节点形成的无标记二叉树的数量。

让我们通过一个例子来理解无标记二叉树的枚举。

假设我们有一组包含三个节点的节点。

第一轮，考虑 N=1，其中 n 表示节点数，以便我们可以创建一棵具有一个节点的二叉树。树将如下所示：

现在考虑 N=2，这意味着我们有两个节点来形成二叉树。因此，使用两个节点，我们可以创建两种不同的二叉树。

对于 N=2，形成了两种不同的二叉树，这两棵树看起来像：

在其中一棵树中，根节点只有一个左子节点；而在另一棵树中，根节点只有一个右子节点。

现在考虑 N=3。有三个节点可用于创建不同的二叉树。对于 N=3，可以创建五种不同的无标记二叉树。这五种不同的无标记二叉树是：

如上所示，创建了这五种不同的无标记树。

• 在无标记二叉树 1 中，根节点只有一个左子节点，而该左子节点只有一个左子节点。在无标记二叉树 1 中显示的树也称为左倾斜二叉树。
• 在无标记二叉树 2 中，根节点有一个左子节点，而该左子节点有一个右子节点。
• 在无标记二叉树 3 中，根节点有一个右子节点和一个左子节点。这是一棵二叉树。
• 在无标记二叉树 4 中，根节点有一个右子节点和一个左子节点。
• 在无标记二叉树 5 中，根节点只有一个右子节点，而该右子节点只有一个右子节点。在无标记二叉树 5 中显示的树也称为右倾斜二叉树。

因此，要计算三个节点的枚举：

对于 N=1，不同无标记树的数量 = 1

对于 N=2，不同无标记树的数量 = 2

对于 N=3，不同无标记树的数量 = 5

以下是根据节点数对所有这些不同二叉树数量求和的公式。

其中 N 是节点数。

让我们计算 N=3 的情况：

因此，对于三个节点，可以创建五种不同的无标记二叉树。

C++ 代码

让我们编写一个 C++ 代码来查找从给定一组无标记节点创建的不同无标记二叉树的数量。

输出：上述 C++ 代码的输出是

The number of distinct unlabeled binary trees is 5

Java 代码

让我们编写一个 Java 代码来查找从给定一组无标记节点创建的不同无标记二叉树的数量。

输出：上述 Java 代码的输出是

The number of distinct unlabeled binary trees is 5