1

这个Wolfram链接谈到了一些关于“标记”二叉树的内容。那么是否也有所谓的“未标记”二叉树？对两者的简明解释会非常好。

我为什么要找这个？
我试图回答这个问题：

我们得到一组 n 个不同元素和一棵具有 n 个节点的未标记二叉树。我们可以通过多少种方式用给定的集合填充树，使其成为二叉搜索树？

现在，我知道给定 n 个节点的二叉树的数量是第 n 个加泰罗尼亚数，但现在我很困惑：这个公式适用于上述两种类型中的哪一种？

PS：对引号中的问题的一些帮助也会非常好:)

4

2 回答 2

2

二叉树可以为每个节点分配标签，也可以不分配标签。对于具有 n 个节点的给定未标记二叉树，我们有 n! 分配标签的方法。（考虑节点的有序遍历，我们希望将其映射到标签 1..n 的排列）

从上面我们可以看到第 n 个加泰罗尼亚数给出了未标记二叉树的数量。

以 n = 3 为例。我们有以下树 5 棵树：

1. o      2. o       3.  o      4.  o   5. o 
    \         \         / \        /      / 
     o         o       o   o      o      o  
    /           \                /        \
   o             o              o          o

一般来说，这个数字是由第N 个加泰罗尼亚数的公式给出的。

要获得标记树的数量，您必须乘以 n！所以对于 n = 3，我们总共有 30 棵树。基本上，对于上面五个未标记的 BST，我们创建了 !3 = 6 个带标签的标记 BST：

1: 1, 2, 3
2: 1, 3, 2
3: 2, 1, 3
4: 2, 3, 1
5: 3, 1, 2
6: 3, 2, 1

希望这有助于理解差异。

于 2015-04-16T08:32:00.160 回答
0

好吧，据我了解，“未标记”意味着我们不知道这棵树的节点。然后问题询问我们有多少种不同的方式将元素分配给节点，因此树将是二叉搜索树。

更新：这意味着我们要从这些N元素中为每个节点设置值，所以我们不会破坏主要的二叉搜索树条件。这意味着在所有节点都有值之后，我们仍然有二叉树 - 任何节点中的键都大于该节点左子树中所有节点中的键并且小于该节点右子树中所有节点中的键 -树。

维基百科上的二叉搜索树

于 2015-04-16T08:10:46.837 回答