这里是SICP（计算机程序的结构和解释）的练习：
练习2.63：以下两个过程分别转换一个二进制文件 树到列表。
(define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '()))... 2.在将具有n个元素的平衡树转换为a时，两个过程的步数顺序是否相同？ 清单？如果不是，哪一个增长速度更慢？
查看这两个过程并且不对增长的顺序进行任何计算，tree-> list-2的所有基本操作都是常数，而tree-> list-1的操作之一append不是。因此，很明显，tree-> list-2的增长比tree-> list-1的增长慢。
现在，虽然练习中没有特别要求我们这样做，但是我想找到tree-> list-1的步长增长顺序。以下是我的尝试。
附加过程为：
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1)
(append (cdr list1)
list2))))
根据定义，步数的增长顺序随着theta（l1）增长，其中l1是第一个列表中的元素数。如果两个列表的长度相同，则增长顺序将以theta（n / 2）增长，其中n是两个列表的元素数之和。基于这些，我尝试像这样计算出tree-> list-1的增长顺序：
假设追加需要恒定的时间（仅用于初始），那么我们将发现tree-> list-1的增长顺序随theta（n）增长。由于append是唯一一个不恒定的过程，因此我相信我可以放心地忽略其他基本操作。使用append的实际运行时间，我得到以下观察结果。
注意：我观察到的树木是平衡的。因此，我通过将节点数量加倍（或增加树的高度）来测试运行时间。
0个节点-常数1个节点-常量3个节点-追加1个递归调用7个节点-5个要追加的递归调用（前2个来自子树（上面），3个来自左分支）15个节点-要追加的17个递归调用（10个来自子树（以上），7个来自左分支）31个节点-49个要追加的递归调用（34个来自子树（上方），17个来自左分支）63个节点-129个要追加的递归调用（98个来自子树（以上），31个来自左分支）...n个节点-2t +（n / 2），其中t是子树的步数，n是树中的节点数]
我的其他观察结果是：在完全不平衡的二叉树中：如果所有节点都在右分支中，则步数随着theta（n）的增加而增加。如果所有节点都在左分支中，则步数将增长为（1 + 2 + 3 + 4 + ... + n-1）或n（n-1）/ 2（我在某处找到了此公式） ）。根据我的数据，平衡的二叉树中的步数在两者之间增加。
现在，步数顺序是节点数加倍的顺序是：（1、5、17、49、129）。他们成长为（4，12，32，80）。
[似乎我们可以通过以下方式获得具有n个元素的平衡二叉树的步数：2t +（n / 2），其中t是两个子树的步数，n是节点数。
现在，对于我的一生，我无法找到该增长顺序所属的分类（例如线性，对数，二次，指数），尽管我已经确认该增长顺序比线性增长快，但比二次增长慢。] >
我的数据正确吗？我无法找到tree-> list-1随n增大的增长顺序，即使我无法对其进行分类？
这里是SICP（计算机程序的结构和解释）中的一项练习：练习2.63：以下两个过程中的每一个将一个二叉树转换为一个列表。 （定义（tree-> list-1 ...
如果使用书中的定义（1.2.3），则否，这两个函数的增长顺序都相同。本书需要一个函数，该函数具有正确的比例因子，既可以作为过程的上限，也可以作为过程的下限（对于足够大的n值）。
我相信tree-> list-1的增长顺序是n * log（n）。