构造唯一二叉搜索树
我正在研究一个算法问题。给定n，生成存储值1的所有结构唯一的二进制搜索树。。。n、 解决方案是枚举序列中的每个数字i，并使用该数字作为根，其左侧的子序列1…（i-1）将位于根的左分支上，类似地，右侧的子序列（i 1）…n位于根的右分支上。然后从子序列递归地构造子树。这种方法确保构建的BST都是唯一的，因为它们有唯一的根。
现在我的问题是：如果树不限于二叉搜索树，如果它可以是任何二叉树，该怎么办。解决方案是什么？我仍然想用根I检查所有情况，其中I=1。。。n、 左子树不必在1的范围内。。。（i-1），右子树不必在（i-1）。。。n、 那怎么安排呢？创建（i-1）元素的任意子集并应用？？
共有2个答案
对BST使用您的算法。这将生成树的唯一形状。形状是唯一的，因为对于每个根n，左边子树中有n-1个元素，其余的在右边。
然后，对于每个形状，有n！元素的顺序。这给出了任意树的结果。
假设你有一个问题：给定n个磁盘，将它们排列成独特的二叉树形状。然后，按照你在问题中的正确推理，你可以说：我将为磁盘编号1,2,3，...，n；然后我将（递归地）构建根位于磁盘#1，然后是磁盘#2的树，等等。
因此，您（正确地）发现的树根有向图实际上与节点中的内容无关，更不用说内容是否满足BST不变量的问题了。考虑到你的问题，
>
如果是这种情况，你不需要枚举，而是近似地计算这样的树的数量，那么请注意这是n！乘以加泰罗尼亚数字。
-
我们可以使用前序遍历输出构造唯一的二叉查找树，如下所示： 第一个元素将是根。 左子元素=小于根的最近元素。 右子元素=最近的元素大于根。 这些事实很容易转换成代码。然而，我正在努力获得如此严格的事实/步骤，以将级别顺序遍历输出转换为唯一的二叉查找树。 例如，如果我有以下级别顺序遍历输出，我可以形成BST如下： 级别顺序遍历中的第一个元素始终是根（级别0）。然后是级别1的元素。4小于5，所以我将把它
-
二叉树 ： 闲话少说，直接上代码： <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>BST</title> </head> <body> <script> //结点 function Node(data,left,right){ this.data=data; t
-
我很难按我教授想要的格式打印出一个二叉搜索树。 他的格式是这样的： 我的代码：
-
编写一个函数，如果给定的二叉搜索树包含给定的值，则返回1，否则返回0。 例如,对于以下树： N1（值：1,左：null,右：null) n2（值：2,左:n1,右:n3) N3（值：3,左：null,右：null) 对contains(&n2,3）的调用应返回1，因为根位于n2的树包含编号3。 函数应该返回1，然而，它返回0或者根本不返回。
-
假设你有一棵完美的二叉树，就像这样 给定其深度和作为深度优先搜索数组的节点值输出，例如。 深度：[4] Dfs数组：[0,1,3,7,8,4,9,10,2,5,11,6,13,14] 编写将其作为二叉树返回的代码。你会怎么做（递归/非递归）？ 我不确定是否有可能递归地解决这个问题，因为我不知道哪些节点是叶子而不是叶子。有了这些信息，人们就可以递归地构建树。在没有递归的情况下，我试图做一些类似的事情
-
下面是将二叉查找树的前序遍历转换为原始树的代码。 下面的代码采用整数数组，表示二进制搜索树的预序遍历。返回构造树的根。 来源:http://www . geeks forgeeks . org/construct-BST-from-given-preorder-traversal-set-2/ 我无法理解此代码。有人能帮我理解以下内容吗 > 在任何给定的迭代中，堆栈中存储的值与指出的当前值相关 从