问题标签 [tree]

出于某种原因，我很难想出一种重写此函数的好方法，以便它使用恒定的堆栈空间。大多数关于树递归的在线讨论都是通过使用斐波那契函数并利用该特定问题的属性来作弊的。有没有人对递归的这种“真实世界”（嗯，比斐波那契数列更真实）使用有任何想法？

Clojure是一个有趣的案例，因为它没有尾调用优化，而只有通过“recur”特殊形式的尾递归。它还强烈反对使用可变状态。它确实有许多惰性结构，包括tree-seq，但我看不到它们如何帮助我解决这种情况。谁能分享他们从 C、Scheme、Haskell 或其他编程语言中学到的一些技术？

编辑：根据评论中的要求...

用一般术语重述并使用 Scheme——如何重写以下递归模式，使其不消耗堆栈空间或需要对非自调用进行尾调用优化？

我选择了烦人的名字来说明我正在寻找不依赖于 x、浸渍、frobnicate、f、g 或 h 的代数属性的答案。我只想重写递归。

更新：

Rich Hickey为 Clojure添加了一个显式的蹦床函数。

简而言之，我想学习/开发一种优雅的方法来将二叉树保存到磁盘（一般树，不一定是 BST）。这是我的问题的描述：

我正在实施一个“20 个问题”的游戏。我写了一棵二叉树，其内部节点是问题，叶子是答案。如果有人对您当前的问题回答“是”，则节点的左孩子是您要遵循的路径，而右孩子是“否”的答案。请注意，这不是二叉搜索树，只是左孩子为“是”而右孩子为“否”的二叉树。

如果程序遇到一个为空的叶子，程序会通过要求用户将她的答案与计算机正在考虑的答案区分开来，将一个节点添加到树中。

这很简洁，因为树会在用户播放时自行构建。不整洁的是我没有将树保存到磁盘的好方法。

我考虑过将树保存为数组表示形式（对于节点 i，左子节点为 2i+1，右节点为 2i+2，父节点为 (i-1)/2），但它并不干净，我最终得到大量浪费空间。

关于将稀疏二叉树保存到磁盘的优雅解决方案的任何想法？

我目前正在重写一个应用程序，教师可以在线计划课程。

该应用程序指导教师完成为学生创建工作单元的过程。该工具目前在三个州使用，但我们计划扩大规模。

该应用程序的主要抽奖卡之一是所有学生的成绩都预加载到系统中。这允许教师搜索或浏览并选择每个工作单元将要达到的结果。

当我最初设计系统时，我假设所有学生的成绩都遵循类似的层次结构。也就是说，有命名的嵌套容器，然后是结果。

我输入的原始结果集是三层的。因此，我的数据库具有以下结构：

==========================

粗体表

h1

身份证，姓名

h2

id，父母___id（h1_id），姓名

h3

id, 父母___id (h2_id), 姓名

结果

id，父母___id（h3_id），姓名

==========================

除了明显无法添加 n/ 层次结构之外，这种方法还使得在不递归查询数据库的情况下难以显示所有标准的列表。

一旦添加了学生成绩（及其父类别），就几乎没有理由以任何方式对其进行修改。主要要求是它们易于阅读且高效。

到目前为止，来自不同学校/州/国家的所有学生成绩都大致遵循我的假设。情况可能并非总是如此。

当然，所有现有数据都必须从当前数据库传输过来。

鉴于上述情况，我存储所有不同的学生结果集的最佳方式是什么？下面列出了我的一些想法。

• 在使用数据库中使用4个表继续使用回收或大量连接时

• 使用嵌套集

• XML（所有不同集合的全局 XML 文件或每个集合的 XML 文件）

I'm trying to make an XML questions editor in flash. Basically I load in the XML into a Tree component - XML like so:

So that goes into the tree. On change I get a list of the options for the selected question (item..option) - and that XMLList is passed into a (custom) component. That component (not sure if this is the best way to go about it but still...) - has a couple of Repeater controls - one which is bound to the XMLList for a radio question, the other bound to the XMLList of a cheque box question. Each repeater loops the number of options, placing a TextInput in (to edit the option text) and either a radio or cheque box (depending on the question type)

So - what I am after is when the text is edited for an option, the XML in that TextInput is bound to the XML which is the dataProvider for the tree. So for example if "This is option 1" is changed to "This is option Foo" - the Tree updates with that.

So far my repeater (eg. for the radios) is like this

No binding works - all I get here is warnings like:

I sort of get why this is the case, but am at a loss how to go about binding the data the user can edit back to the source xml. I know I can make the tree itself editable but that's not really an option here.

So any pointers or ideas would be very appreciated!

我正在尝试通过从头开始实现树来了解树。在这种情况下，我想用 C# Java 或 C++ 来做。（不使用内置方法）

所以每个节点都会存储一个字符，每个节点最多有 26 个节点。

我将使用什么数据结构来包含指向每个节点的指针？

基本上我正在尝试从头开始实现基数树。

谢谢，

基本上，我有我的霍夫曼表

其中 string 是位模式，char 是所述模式表示的值。问题是如何将其存储为压缩文件的标题，以便在我想解码时可以再次构建相同的地图？

尝试将其存储为二进制：

后来建立：

不起作用，我得到字符串初始化错误......与NULL有关。有什么建议么？如果您有更好的方法来存储我想听的位和值。

对于我的应用程序，我想要一个组合框，它在作为Tree下拉时显示其元素。问题是，我对 Swing 不够精通，不知道如何去做。至少不会最终从头开始编写新的小部件，或者类似的东西。

如果不从头开始创建一个，我将如何做这样的事情？

我还有另一个序列化问题，但这次是关于序列化为二进制时 Java 的本机序列化导入。我必须序列化在另一个 java 文件中生成的随机树。我知道序列化和反序列化是如何工作的，但是我在使用带有 java.io.Serializable 的二进制序列化时遵循的示例与使用简单对象时的方式不同。这是我的代码段：

我相信问题出在我使用 writeObject(randomTree) 时。发生这种情况时，我会遇到一些终端异常……它们如下：

java.io.NotSerializableException：GeneralTree 在 java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1081) 在 java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:302) 在 BinaryS.main(BinaryS.java:24)

编辑：我知道它说的是 GeneralTree，但在课程开始时我把它放在了

然后，在它下面找到GeneralTree

");

更新：嘿，伙计们，我发现了自己的问题，结果我是个白痴，没有意识到我必须下载一个额外的 .java 文件，现在很容易解决！谢谢你的帮助！

我正在寻找在树结构中指定文件的示例，例如，用于指定要在 grep 工具中搜索的文件集。我希望能够通过名称匹配来包含和排除文件和目录。我敢肯定那里有例子，但我很难找到它们。

下面是一个可能的语法示例：

（这意味着包含扩展名为 .py .html .txt .js 的文件，排除 .pyc 文件，.svn 目录下的任何内容，以及任何匹配combo_ .js 的文件）

我知道我以前在其他工具中看到过这类规范。这是否为任何人敲响了警钟？

我的数学课远远落后，我目前正在努力为我遇到的问题找到一个体面的解决方案：我有一棵树，其中的节点是动作，并且根据多个标准“加权”：所说的行动，它将花费的时间，必要的资源，干扰等......

我想在这棵树中找到最小化成本和时间的路径，或者干扰和成本和时间等。我的问题是我不知道该怎么做，除非上来使用全局成本函数 F(cost, time, resources,...)，并使用 F(...) 的结果作为我唯一的权重应用常规树遍历算法。但是，我该如何想出 F ？像“F(cost, time, resources) = a * cost + b * time + c * resources”这样的东西感觉很“不专业”......

编辑：

我想避免使用“求和”这个词，因为我不确定这是否真的是要走的路，但本质上，这就是我正在做的事情：计算来自的每个“路径”或“分支”的总成本该顶部节点，到其中一个叶子，并选择最小化成本的“路径”或“分支”。问题是每个节点都有一个基于所需时间、财务成本、资源使用等的权重。

因此，正如斯蒂芬所说，似乎不可避免地必须提出一个公式，将所有这些参数减少到每个节点的一个全局成本，然后我可以在沿树向下移动时跨节点求和，并选择路径最小化总成本。

所以我想我的问题真的是，是否有选择该功能的方法？

感谢您的回答和评论，现在我的头脑开始变得更加清晰了。