问题标签 [binary-tree]

今天早上，我在阅读Steve Yegge 的《当多态性失败时》时，遇到了一个问题，他的一位同事曾经在潜在员工来亚马逊面试时问他们这个问题。

作为多态性的一个例子，让我们看一下经典的“eval”面试问题，（据我所知）是由 Ron Braunstein 带到亚马逊的。这个问题非常丰富，因为它设法探讨了各种各样的重要技能：OOP 设计、递归、二叉树、多态性和运行时类型、一般编码技能，以及（如果你想让它更难的话）解析理论.

在某些时候，候选人希望意识到您可以将算术表达式表示为二叉树，假设您只使用诸如“+”、“-”、“*”、“/”之类的二元运算符。叶节点都是数字，内部节点都是算子。评估表达式意味着遍历树。如果应聘者没有意识到这一点，你可以温和地引导他们，或者如果有必要，直接告诉他们。

即使你告诉他们，这仍然是一个有趣的问题。

问题的前半部分，有些人（我将保护他们的名字直到我垂死的呼吸，但他们的名字首字母是威利刘易斯）觉得如果你想称自己为开发人员并在亚马逊工作，这是一个工作要求，实际上有点难. 问题是：如何从诸如“2 + (2)”之类的算术表达式（例如在字符串中）到表达式树。在某个时候，我们可能会在这个问题上遇到 ADJ 挑战。

后半部分是：假设这是一个 2 人项目，你的搭档，我们称之为“Willie”，负责将字符串表达式转换为树。你得到了简单的部分：你需要决定 Willie 用什么类来构造树。你可以用任何一种语言来做，但一定要选择一种，否则威利会把汇编语言交给你。如果他感到不耐烦，那将是针对不再生产的处理器。

你会惊讶于有多少候选人喜欢这个。

我不会给出答案，但标准错误解决方案涉及使用 switch 或 case 语句（或只是好的老式级联 ifs）。稍微好一点的解决方案涉及使用函数指针表，而可能最好的解决方案涉及使用多态性。我鼓励你在某个时候完成它。好玩的东西！

所以，让我们尝试通过三种方式来解决这个问题。如何使用级联-if、函数指针表和/或多态性从算术表达式（例如在字符串中）如“2 + (2)”到表达式树？

随意解决一个，两个或所有三个。

[更新：修改标题以更好地匹配大多数答案。]

我在最近读过的几本书中看到了二叉树和二叉搜索，但由于我仍处于计算机科学学习的初期，我还没有上过真正涉及算法和数据的课程结构严重。

我已经检查了典型的来源（维基百科、谷歌），并且大多数关于（特别是）红黑树的有用性和实现的描述都变得密集且难以理解。我敢肯定，对于有必要背景的人来说，这很有意义，但目前它读起来几乎就像一门外语。

那么，是什么让二叉树在您发现自己在编程时执行的一些常见任务中有用呢？除此之外，您更喜欢使用哪些树（请提供示例实现）以及为什么？

我需要一个纯 .Net 持久哈希表/二进制树，功能类似于 berkeley-db Java 版本。

从功能上讲，它应该以与 DHT 类似的方式运行，例如 memcached 和速度等，但它不必分发。本质上，我正在寻找一个持久的哈希表。

有没有人有任何想法或建议？

这里也有一个类似的问题：在 C# 中寻找一个简单的独立持久字典实现

保罗

什么是最简单的方法，最好使用递归，在 BST（二叉搜索树）中找到最短的根到叶路径。首选Java，伪代码还可以。

谢谢！

好的，对于周围的 CS 家伙来说，这是另一个理论领域。

在 90 年代，我在实施 BST 方面做得相当好。唯一让我无法理解的是平衡二叉树 (AVL) 的算法的复杂性。

你们能帮我解决这个问题吗？

使用递归为二叉搜索树创建遍历。

这是功能。现在这显然是错误的。这个函数是这样调用的：

首先是对象，而 print vals 只是一个打印对象中数据的函数。每个对象都有三个值，数据、左和右。我如何使用该功能实际访问这些项目？

好的，我正在尝试通过递归创建此遍历。我实际上之前发布了这个问题，但由于我必须使用函数指针，所以我做错了。我不明白我应该做什么。我有调用私有包装的公共包装器......但是公共包装器是带有传入函数的包装器，所以我该怎么办？我觉得自己很迟钝，所以即使有人给我一个小小的暗示，我也相信我会明白的。我只是不知道从这里去哪里。

调用它的代码示例如下：

所以我的代码如下。我没有收到任何错误，它将所有内容都放在节点中就好了。但是根据我的调试语句，每次插入任何东西时，它都会找到根。我不确定这是否正确。但是根据作业的输出文件，当涉及到树的高度、遍历时，我的答案是不同的，而且我的叶子计数功能仍然存在问题。另一个故事。

根据调试语句，看起来一切都在他们应该的地方进行。但我想我可能需要新鲜的眼睛。我根本看不到我的遍历会如何改变，因为这实际上只是我在哪里处理应该影响中序、前序和后序的节点的问题。

我的高度函数如下，以防我的插入实际上很好。

上图来自“维基百科关于 AVL 树的条目”，维基百科指出它是不平衡的。这棵树怎么还不平衡？这是文章的引述：

节点的平衡因子是其右子树的高度减去其左子树的高度，平衡因子为 1、0 或 -1 的节点被认为是平衡的。具有任何其他平衡因子的节点被认为是不平衡的，需要重新平衡树。平衡因子要么直接存储在每个节点上，要么根据子树的高度计算。

左子树和右子树的高度均为 4。左树的右子树的高度为 3，但仍然比 4 小 1。有人可以解释我缺少什么吗？

我想知道这里是否有人曾经使用过跳过列表。它看起来与平衡二叉树具有大致相同的优势，但实现起来更简单。如果有，您是自己编写的，还是使用预先编写的库（如果有，它的名称是什么）？