问题标签 [binary-tree]

如果只给出后序列表，我如何找到树的预订列表，反之亦然。此外，在树中，每个非叶节点都有两个子节点（即每个节点有两个或零个子节点。）

编辑：另一个给定的假设是每个节点的标签是唯一的，并且有一个字段将其标识为内部节点或叶子。我认为这应该消除单个预购或后购能够唯一识别一棵树的歧义。

可以使用两个函数 l 和 r 对二叉树进行编码，使得对于节点 n，l(n) 给出 n 的左孩子，r(n) 给出 n 的右孩子。

树的分支是从根到叶子的路径，分支到特定叶子的长度是从根到该叶子的路径上的弧数。

令 MinBranch(l,r,x) 是一个简单的递归算法，用于获取由 l 和 r 函数编码的二叉树以及二叉树的根节点 x，并返回二叉树的最短分支。

请提供此算法的伪代码。

假设我有一个具有以下节点定义的二叉树。

二叉搜索树是在key1的基础上创建的。现在可以根据 O(1) 空间中的 key2 重新排列二叉搜索树。尽管我可以使用指向节点的指针数组在变量空间中执行此操作。

我需要这个的实际问题是“计算文件中唯一单词的出现次数并以频率降序显示结果”。这里，一个 BST 节点是

我在选择数据结构（即 BST）时错了吗？

在不使用递归的情况下对二叉树进行后序遍历的算法是什么？

作为我最初关于一小段代码的问题的后续行动，我决定要求跟进，看看你是否可以做得比我们迄今为止提出的更好。

下面的代码遍历二叉树（left/right = child/next）。我确实相信这里有一个不那么有条件的空间（down布尔值）。最快的答案获胜！

1. 该cnt语句可以是多个语句，因此请确保它只出现一次
2. child()和成员函数的next()速度大约是 hasChild() 和 hasNext() 操作的 30 倍。
3. 保持迭代<--放弃了这个要求，因为提出的递归解决方案更快。
4. 这是 C++ 代码
5. 节点的访问顺序必须保持在下面的示例中。（先打父母，然后打孩子，然后打“下一个”节点）。
6. BaseNodePtr 是 boost::shared_ptr ，因此分配速度很慢，请避免使用任何临时 BaseNodePtr 变量。

目前这段代码访问一个测试树中的62200000个节点需要5897ms，调用这个函数200000次。

这是节点定义：

我要做的是列出所有指向祖先节点的节点。在发布错误的解决方案并从答案中获取建议后，我的新解决方案是：

递归遍历二叉树。将当前节点添加到节点数组中，然后检查当前节点的子节点是否指向任何先前的祖先节点。

默认情况是节点为 NULL。如果发生这种情况，函数将返回。

它应该如何工作：

将节点添加到数组

检查左孩子是否为 NULL。

如果不是，它将子节点与之前的每个节点进行比较。

如果它发现故障，它会报告它。

如果不是，它以子作为参数调用该函数。

重复直到完成。（对于二叉树的 rhs 也一样）

问题：

• 数组是存储节点的最佳方式吗？
• 这行得通吗？for (i = 0; i < sizeof(arrOfNodes) / sizeof(node); i++)
• 因为函数是递归的，所以数组和数组索引不能在函数内部初始化（或者它们可以是？）所以它们应该是全局的吗？
• 有两个数组会更好吗？（LHS 一个，RHS 一个）

编码：

可以使用两个函数对二叉树进行编码l，r 对于 a node n，l(n)给出 的左孩子n，r(n) 给出 的右孩子n。

树的分支是从根到叶子的路径，分支到特定叶子的长度是从根到该叶子的路径上的弧数。

让MinBranch(l,r,x)是一个简单的递归算法，用于获取由 l 和 r 函数编码的二叉树以及二叉树的根节点 x，并返回二叉树最短分支的长度。

给出这个算法的伪代码。

好的，所以基本上这就是我到目前为止想出的：

显然这不是很好或完美的。如果人们能帮助我完成这个完美的工作，我会很感激 - 任何帮助都将不胜感激。

这一直困扰着我一段时间。我知道给定 N 个键以二叉搜索树的形式排列，可以创建的树的可能数量对应于Catalan 序列中的第 N 个数。

我一直在试图确定这是为什么；找不到任何甚至可能试图直观地解释它的东西，我求助于 SO 的集体知识。我找到了其他方法来计算可能的树的数量，但它们似乎不太直观，除了如何使用它之外没有提供任何解释。再加上 wiki 页面（上面的链接）甚至显示了带有 3 个键的可能的树形结构的图像，这让我认为有一个很好的和简洁的解释可以听到（不用说，不包括在文章中）。

提前致谢！

我正在为二叉搜索树编写类似 STL 的容器。我有 Tree 本身的模板类和嵌套类 TreeNode。
我的问题是我应该将比较键的二进制谓词函数放在哪里 - 放入树类或节点类？如果我决定把它放在 Tree 类中，我的所有节点都不知道如何比较它们的键:(
如果在 Node 类中，我应该让这个函数静态还是不？

如何从给定的遍历方法（中序、后序或前序）中找到二叉树？