如何表示二叉树？

Question

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

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

列表结构被视为一棵树。

 /\
/\ 3 4 
1 2

为什么不是下面的？

  / \
 /\ /\
1 2 3 4

Answer 1

为了更好地理解将列表转换为点对：

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

     /\
    /  \
   /\   \
  /  \  /\ 
1   /\  3/\
   2  ()4 ()

您正在绘制的树将是：

((1 . 2) . (3 . 4)) ; but the general way of displaying it would be
((1 . 2) 3 . 4)

那我假设pair是一个car在右边，cdr在左边的节点。基本上：

(define make-tree cons)
(define tree-right car)
(define tree-left cdr)
(define tree? pair?)
(define *tree-null* '())

现在您可以像这样为树建模：

(define make-tree list)
(define tree-right car)
(define tree-left cadr)
(define tree? list?)
(define *tree-null* '())

那么同一棵树看起来像这样：

((1 2) (3 4))

这真的没关系，但第一个例子是常用的方法，因为它使用较少 space。不管怎样，它们的工作原理都是一样的：

(define (accumulate-tree tree term combiner null-value)
  (let rec ((tree tree))
    (cond ((eq? *tree-null* tree) null-value)
          ((not (tree? tree)) (term tree))
          (else (combiner (rec (tree-left tree)) 
                          (rec (tree-right tree)))))))

(define (copy-tree tree)
  (accumulate-tree tree values make-tree *tree-null*))

(define (aritmetric-sum-tree tree)
  (accumulate-tree tree values + 0))

(define (reverse-tree tree)
  (accumulate-tree tree 
                   values
                   (lambda (left right) (make-tree right left))
                   *tree-null*))

编辑

SICP 只提供了一种不同的方式来看待相同的结构，这不是二叉树。有一个节点是一个子列表，一个子列表是一个新节点。更重要的是你要了解方框，并且链式缺点有一种奇怪的显示方式。请注意这些盒子与我的树有何相似之处。

重要的是要了解，使用 cons 您可以对任何抽象数据结构建模，并且在创建您自己的数据结构时，您正在改变如何将元素映射到 cons。因此，相同的列表结构可能代表其他内容，具体取决于您如何使用它们。例如。如果你有一个 LZW 树，你在查找中迭代树，你通常只需要一个父节点。因此。一对可能是父节点和此节点值。

Answer 2

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

例如，没有什么能阻止您将数字序列表示为不正确的列表，即将序列 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))，所以使用起来更方便。

另一方面，对于树木，情况更复杂，因为你可以有不同种类的树，例如：

信息仅存在于叶子中的二叉树（如您的示例），
信息存在于每个节点的二叉树，
n-ary 树，其中信息存在于每个节点或在树叶中，
二进制或n-ary树，其中信息是列表，或更复杂的结构（例如另一棵树），

等等

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

总而言之，重要的是以如下方式定义一棵树最适合您的需要（也许看看是否有预定义的功能或可用的库已经提供了你需要的运算符），然后定义基本运算符来处理它，就像在 , operators to build the tree and to use its components, and use always them to write your program. In this way you have all the usual benefits of the Abstract Data Type 方法中一样，例如你可以在不修改程序的情况下更改树的表示。

如何表示二叉树？

How to represent binary tree?

tree

scheme