0

我一直在观看优秀的Richard Buckland的一些讲座并尝试使用二叉树，但我并不完全了解如何实现它。下面是我已经走了多远。 

class Tree(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

t = Tree(4, Tree(2, Tree(1), Tree(3)), Tree(6, Tree(5), Tree(7)))

有人可以向我推荐一个可以使用二叉树解决的简单示例问题。我真的不明白创建树将提供哪些数据或如何实际使用它。我害怕谷歌搜索一些例子，因为我不想要别人的源代码。我想自己制定实施。但在我能做到这一点之前，我觉得我需要解决一个问题。理想情况下，我想要几个相当琐碎的示例问题，然后是一些中间问题。

4

2 回答 2

1

您上面的代码是二叉树的“有效”实现......它已经完成了。您有节点（称为Trees），每个节点可以有 0、1 或 2 个子节点。编辑实际上我刚刚意识到你不能使用你的实现来实现一个空树，但这是一个小问题。

这是语义上的事情，但它“有点重要”。二叉树本身并没有真正用于解决问题。一棵标准的二叉树并不是很有用——它只是一棵树，其中每个节点最多有两个孩子。此链接应该澄清我在说什么（并且可能包含对您问题的充分答案）：https ://stackoverflow.com/a/2159506 。

我认为您真正感兴趣的是具有额外属性的“平衡二叉搜索树”。特别是，它是从左到右“排序”的（这是一个模糊的描述，但我不想挥手说“左孩子小于父母及其兄弟姐妹”实际上可能是在某些实现中相等）。它也有一个O(log(n))有限的深度（你不会有高度的树和n其中的n对象......这只是一个链表）。

无论如何，回答你的问题：这有点无聊，但一个常见的建议是实现一个抽象数据结构，如堆或字典。注意术语：堆可以使用二叉搜索树来实现。根据定义，堆与任何实现无关。它只要求可以对其执行某些操作（例如peek(), min(), add()，等）。选择像二叉树这样的原始数据结构是生成堆所必需的（否则它只是浮在脑海中的这个抽象事物）。选择平衡二叉搜索树也会给这些操作带来时间复杂性（例如，使用平衡二叉搜索树实现的堆具有O(log(n)) peek(). 更多详细信息，请参见 wiki 链接：http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants )。

一旦你写了一个堆，你就可以查看任何算法使用堆的问题......有很多。假设您想k在线性时间内找到最大的元素。堆（虽然证明这有点棘手）。如果你想实现 Prim 的算法呢？堆。如果您想对最坏情况下的任意对象进行排序O(n log(n))怎么办？堆排序（请注意，通常人们不使用堆排序，因为它实际上并不快）。

于 2013-05-12T11:56:09.380 回答
0

好吧，试试这个：http ://www.spoj.com/problems/TREE/

或者这个：http ://www.spoj.com/problems/THREECOL/

http://www.spoj.com/problems/NWERC11B/

这些问题都不是小事，会问时间，但你一定会从中吸取教训。

基本上，有大量的问题本质上需要以某种方式使用二叉树。例如，在命题逻辑中构建推理算法。

是的，如果你能掌握 Sedgewick 的算法，那么有一些关于二叉搜索树的章节，例如，非常有用。

于 2013-05-12T10:26:50.100 回答