tree - 如何表示二叉树？

Question

用列表表示的序列自然地概括为表示序列 元素本身可能是序列。例如，我们可以把对象((1 2) 3 4)看成是由(cons (list 1 2) (list 3 4))构造的。序列的元素是树的分支，本身是序列的元素是子树。

我不明白。我想看到 ((1 2) (3 4)) 和二叉树，但这是三叉树(不是二叉树)。

列表结构被视为一棵树。

 /\\
/\ 3 4 
1 2

为什么不是下面的？

  / \
 /\ /\
1 2 3 4

Answer 1

使用源自原始 Lisp 的语言，例如您没有的 Scheme 列表或树作为原始数据结构，但只有cons cells， 可以用不同的方式来表示更复杂的数据 结构。

例如，没有什么能阻止您将数字序列表示为 不正确的列表，即将序列 1 2 3 4 表示为:

(cons 1 (cons 2 (cons 3 4)))  ;  => '(1 2 3 . 4)

[*|*]--->[*|*]--->[*|*]--->4
 |        |        |
 v        v        v
 1        2        3

这比通常的正确列表表示更有效:

(cons 1 (cons 2 (cons 3 (cons 4 '())))) = (list 1 2 3 4)  ;  => '(1 2 3 4)

[*|*]--->[*|*]--->[*|*]--->[*|*]--->()
 |        |        |        |
 v        v        v        v
 1        2        3        4

(例如，考虑一个应用程序，您必须在其中管理数百万 小列表)。

通常使用适当的列表，因为绝大多数原始 函数仅为它们定义(例如，如果您尝试 反转'(1 2 3 . 4))，所以使用起来更方便。

另一方面，对于树来说，情况就更复杂了，因为你 可以有不同种类的树，例如:

1. 信息仅存在于叶子中的二叉树(如您的示例)，

2. 信息存在于每个节点的二叉树，

3. n-ary 树，其中的信息存在于每个节点或 在树叶中，

4. 信息为列表或更复杂结构(例如另一棵树)的二叉树或 n 叉树，

等等

您可以为手头的问题选择正确的表示形式。 例如，在上面的情况 (2) 中，它比情况 (1) 更常见，您可以将树表示为三个元素(信息、左子树、右子树)的列表(并且在这个如果您可以选择合适的列表或不合适的列表)，或者您可以使用具有三个字段的结构，甚至可以使用具有三个元素的数组。

总而言之，重要的是以如下方式定义一棵树 最适合您的需要(也许看看是否有预定义的功能或可用的库 已经提供了你需要的运算符)，然后定义基本运算符来处理它，就像在 answer of Sylwester 中一样，运算符来构建树并使用其组件，并且始终使用它们来编写您的程序。通过这种方式，您可以获得 Abstract Data Type 的所有常见好处。方法，例如，您可以在不修改程序的情况下更改树的表示。