2023年6月29日发(作者：)

python数据结构递归树_SICPPython描述3.3递归数据结构3.3 递归数据结构在第⼆章中，我们引⼊了偶对的概念，作为⼀种将两个对象结合为⼀个对象的机制。我们展⽰了偶对可以使⽤内建元素来实现。偶对的封闭性表明偶对的每个元素本⾝都可以为偶对。这种封闭性允许我们实现递归列表的数据抽象，它是我们的第⼀种序列类型。递归列表可以使⽤递归函数最为⾃然地操作，就像它们的名称和结构表⽰的那样。在这⼀节中，我们会讨论操作递归列表和其它递归结构的⾃定义的函数。3.3.1 处理递归列表递归列表结构将列表表⽰为⾸个元素和列表的剩余部分的组合。我们之前使⽤函数实现了递归列表，但是现在我们可以使⽤类来重新实现。下⾯，长度(__len__)和元素选择(__getitem__)被重写来展⽰处理递归列表的典型模式。>>> class Rlist(object):"""A recursive list consisting of a first element and the rest."""class EmptyList(object):def __len__(self):return 0empty = EmptyList()def __init__(self, first, rest=empty): = = restdef __repr__(self):args = repr()if is not :args += ', {0}'.format(repr())return 'Rlist({0})'.format(args)def __len__(self):return 1 + len()def __getitem__(self, i):if i == 0:return eturn [i-1]__len__和__getitem__的定义实际上是递归的，虽然不是那么明显。Python 内建函数len在⾃定义对象的参数上调⽤时会寻找叫做__len__的⽅法。与之类似，下标运算符会寻找叫做__getitem__的⽅法。于是，这些定义最后会调⽤对象⾃⾝。剩余部分上的递归调⽤是递归列表处理的普遍模式。这个递归列表的类定义与 Python 的内建序列和打印操作能够合理交互。>>> s = Rlist(1, Rlist(2, Rlist(3)))>>> ist(2, Rlist(3))>>> len(s)3>>> s[1]2创建新列表的操作能够直接使⽤递归来表⽰。例如，我们可以定义extend_rlist函数，它接受两个递归列表作为参数并将⼆者的元素组合到新列表中。>>> def extend_rlist(s1, s2):if s1 is :return s2return Rlist(, extend_rlist(, s2))>>> extend_rlist(, s)Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))与之类似，在递归列表上映射函数展⽰了相似的模式：>>> def map_rlist(s, fn):if s is :return sreturn Rlist(fn(), map_rlist(, fn))>>> map_rlist(s, square)Rlist(1, Rlist(4, Rlist(9)))过滤操作包括额外的条件语句，但是也拥有相似的递归结构。>>> def filter_rlist(s, fn):if s is :return srest = filter_rlist(, fn)if fn():return Rlist(, rest)return rest>>> filter_rlist(s, lambda x: x % 2 == 1)Rlist(1, Rlist(3))列表操作的递归实现通常不需要局部赋值或者while语句。反之，递归列表可以作为函数调⽤的结果来拆分和构造。所以，它们拥有步骤数量和所需空间的线性增长度。3.3.2 层次结构层次结构产⽣于数据的封闭特性，例如，元组可以包含其它元组。考虑这个数值1到4的嵌套表⽰。>>> ((1, 2), 3, 4)((1, 2), 3, 4)这个元组是个长度为 3 的序列，它的第⼀个元素也是⼀个元组。这个嵌套结构的盒⼦和指针的图⽰表明，它可以看做拥有四个叶⼦的树，每个叶⼦都是⼀个数值。在树中，每个⼦树本⾝都是⼀棵树。作为基本条件，任何本⾝不是元组的元素都是⼀个简单的树，没有任何枝⼲。也就是说，所有数值都是树，就像在偶对(1, 2)和整个结构中那样。递归是⽤于处理树形结构的⾃然⼯具，因为我们通常可以将树的操作降⾄枝⼲的操作，它会相应产⽣枝⼲的枝⼲的操作，以此类推，直到我们到达了树的叶⼦。例如，我们可以实现count_leaves函数，它返回树的叶⼦总数。>>> t = ((1, 2), 3, 4)>>> count_leaves(t)4>>> big_tree = ((t, t), 5)>>> big_tree((((1, 2), 3, 4), ((1, 2), 3, 4)), 5)>>> count_leaves(big_tree)9正如map是⽤于处理序列的强⼤⼯具，映射和递归⼀起为树的操作提供了强⼤⽽通⽤的计算形式。例如，我们可以使⽤⾼阶递归函数map_tree将树的每个叶⼦平⽅，它的结构类似于count_leaves。>>> def map_tree(tree, fn):if type(tree) != tuple:return fn(tree)return tuple(map_tree(branch, fn) for branch in tree)>>> map_tree(big_tree, square)((((1, 4), 9, 16), ((1, 4), 9, 16)), 25)内部值。上⾯描述的树只在叶⼦上存在值。另⼀个通⽤的树形结构表⽰也在树的内部节点上存在值。我们使⽤类来表⽰这种树。>>> class Tree(object):def __init__(self, entry, left=None, right=None): = = = rightdef __repr__(self):args = repr()if or :args += ', {0}, {1}'.format(repr(), repr())return 'Tree({0})'.format(args)例如，Tree类可以为fib的递归实现表⽰表达式树中计算的值。fib函数⽤于计算斐波那契数。下⾯的函数fib_tree(n)返回Tree，它将第 n个斐波那契树作为entry，并将所有之前计算出来的斐波那契数存⼊它的枝⼲中。>>> def fib_tree(n):"""Return a Tree that represents a recursive Fibonacci calculation."""if n == 1:return Tree(0)if n == 2:return Tree(1)left = fib_tree(n-2)right = fib_tree(n-1)return Tree( + , left, right)>>> fib_tree(5)Tree(3, Tree(1, Tree(0), Tree(1)), Tree(2, Tree(1), Tree(1, Tree(0), Tree(1))))这个例⼦表明，表达式树可以使⽤树形结构编程表⽰。嵌套表达式和树形数据结构的联系，在我们这⼀章稍后对解释器设计的讨论中起到核⼼作⽤。3.3.3 集合除了列表、元组和字典之外，Python 拥有第四种容器类型，叫做set。集合字⾯值遵循元素以花括号闭合的数学表⽰。重复的元素在构造中会移除。集合是⽆序容器，所以打印出来的顺序可能和元素在集合字⾯值中的顺序不同。>>> s = {3, 2, 1, 4, 4}>>> s{1, 2, 3, 4}Python 的集合⽀持多种操作，包括成员测试、长度计算和标准的交集并集操作。>>> 3 in sTrue>>> len(s)4>>> ({1, 5}){1, 2, 3, 4, 5}>>> ection({6, 5, 4, 3}){3, 4}除了union和intersection，Python 的集合还⽀持多种其它操作。断⾔isdisjoint、issubset和issuperset提供了集合⽐较操作。集合是可变的，并且可以使⽤add、·remove、discard和pop⼀次修改⼀个元素。额外的⽅法提供了多元素的修改，例如clear和update`。Python 集合⽂档⼗分详细并⾜够易懂。实现集合。抽象上，集合是不同对象的容器，⽀持成员测试、交集、并集和附加操作。向集合添加元素会返回新的集合，它包含原始集合的所有元素，如果没有重复的话，也包含新的元素。并集和交集运算返回出现在任意⼀个或两个集合中的元素构成的集合。就像任何数据抽象那样，我们可以随意实现任何集合表⽰上的任何函数，只要它们提供这种⾏为。在这章的剩余部分，我们会考虑三个实现集合的不同⽅式，它们在表⽰上不同。我们会通过分析集合操作的增长度，刻画这些不同表⽰的效率。我们也会使⽤这⼀章之前的Rlist和Tree类，它们可以编写⽤于集合元素操作的简单⽽优雅的递归解决⽅案。作为⽆序序列的集合。⼀种集合的表⽰⽅式是看做没有出现多于⼀次的元素的序列。空集由空序列来表⽰。成员测试会递归遍历整个列表。>>> def empty(s):return s is >>> def set_contains(s, v):"""Return True if and only if set s contains v."""if empty(s):return Falseelif == v:return Truereturn set_contains(, v)>>> s = Rlist(1, Rlist(2, Rlist(3)))>>> set_contains(s, 2)True>>> set_contains(s, 5)False这个set_contains的实现需要Θ(n)的时间来测试元素的成员性，其中n是集合s的⼤⼩。使⽤这个线性时间的成员测试函数，我们可以将元素添加到集合中，也是线性时间。>>> def adjoin_set(s, v):"""Return a set containing all elements of s and element v."""if set_contains(s, v):return sreturn Rlist(v, s)>>> t = adjoin_set(s, 4)>>> tRlist(4, Rlist(1, Rlist(2, Rlist(3))))那么问题来了，我们应该在设计表⽰时关注效率。计算两个集合set1和set2的交集需要成员测试，但是这次每个set1的元素必须测试set2中的成员性，对于两个⼤⼩为n的集合，这会产⽣步骤数量的平⽅增长度Θ(n^2)。>>> def intersect_set(set1, set2):"""Return a set containing all elements common to set1 and set2."""return filter_rlist(set1, lambda v: set_contains(set2, v))>>> intersect_set(t, map_rlist(s, square))Rlist(4, Rlist(1))在计算两个集合的并集时，我们必须⼩⼼避免两次包含任意⼀个元素。union_set函数也需要线性数量的成员测试，同样会产⽣包含Θ(n^2)步骤的过程。>>> def union_set(set1, set2):"""Return a set containing all elements either in set1 or set2."""set1_not_set2 = filter_rlist(set1, lambda v: not set_contains(set2, v))return extend_rlist(set1_not_set2, set2)>>> union_set(t, s)Rlist(4, Rlist(1, Rlist(2, Rlist(3))))作为有序元组的集合。⼀种加速我们的集合操作的⽅式是修改表⽰，使集合元素递增排列。为了这样做，我们需要⼀些⽐较两个对象的⽅式，使我们能判断哪个更⼤。Python 中，许多不同对象类型都可以使⽤运算符⽐较，但是我们会专注于这个例⼦中的数值。我们会通过将元素递增排列来表⽰数值集合。有序的⼀个优点会在set_contains体现：在检查对象是否存在时，我们不再需要扫描整个集合。如果我们到达了⼤于要寻找的元素的集合元素，我们就知道这个元素不在集合中：>>> def set_contains(s, v):if empty(s) or > v:return Falseelif == v:return Truereturn set_contains(, v)>>> set_contains(s, 0)False这节省了多少步呢？最坏的情况中，我们所寻找的元素可能是集合中最⼤的元素，所以步骤数量和⽆序表⽰相同。另⼀⽅⾯，如果我们寻找许多不同⼤⼩的元素，我们可以预料到有时我们可以在列表开头的位置停⽌搜索，其它情况下我们仍旧需要检测整个列表。平均上我们应该需要检测集合中⼀半的元素。所以，步骤数量的平均值应该是n/2。这还是Θ(n)的增长度，但是它确实会在平均上为我们节省之前实现的⼀半步骤数量。我们可以通过重新实现intersect_set获取更加可观的速度提升。在⽆序表⽰中，这个操作需要Θ(n^2)的步骤，因为我们对set1的每个元素执⾏set2上的完整扫描。但是使⽤有序的实现，我们可以使⽤更加机智的⽅式。我们同时迭代两个集合，跟踪set1中的元素e1和set2中的元素e2。当e1和e2相等时，我们在交集中添加该元素。但是，假设e1⼩于e2，由于e2⽐set2的剩余元素更⼩，我们可以⽴即推断出e1不会出现在set2剩余部分的任何位置，因此也不会出现在交集中。所以，我们不再需要考虑e1，我们将它丢弃并来到set1的下⼀个元素。当e2 < e1时，我们可以使⽤相似的逻辑来步进set2中的元素。下⾯是这个函数：>>> def intersect_set(set1, set2):if empty(set1) or empty(set2):return 1, e2 = , f e1 == e2:return Rlist(e1, intersect_set(, ))elif e1 < e2:return intersect_set(, set2)elif e2 < e1:return intersect_set(set1, )>>> intersect_set(s, )Rlist(2, Rlist(3))为了估计这个过程所需的步骤数量，观察每⼀步我们都缩⼩了⾄少集合的⼀个元素的⼤⼩。所以，所需的步骤数量最多为set1和set2的⼤⼩之和，⽽不是⽆序表⽰所需的⼤⼩之积。这是Θ(n)⽽不是Θ(n^2)的增长度 -- 即使集合⼤⼩适中，它也是⼀个相当可观的加速。例如，两个⼤⼩为100的集合的交集需要 200步，⽽不是⽆序表⽰的 10000 步。表⽰为有序序列的集合的添加和并集操作也以线性时间计算。这些实现都留做练习。作为⼆叉树的集合。我们可以⽐有序列表表⽰做得更好，通过将⼏个元素重新以树的形式排列。我们使⽤之前引⼊的Tree类。树根的entry持有集合的⼀个元素。left分⽀的元素包括所有⼩于树根元素的元素。right分⽀的元素包括所有⼤于树根元素的元素。下⾯的图展⽰了⼀些树，它们表⽰集合{1, 3, 5, 7, 9, 11}。相同的集合可能会以不同形式的树来表⽰。有效表⽰所需的唯⼀条件就是所有left⼦树的元素应该⼩于entry，并且所有right⼦树的元素应该⼤于它。树形表⽰的优点是：假设我们打算检查v是否在集合中。我们通过将v于entry⽐较开始。如果v⼩于它，我们就知道了我们只需要搜索left⼦树。如果v⼤于它，我们只需要搜索right⼦树。现在如果树是“平衡”的，每个这些⼦树都约为整个的⼀半⼤⼩。所以，每⼀步中我们都可以将⼤⼩为n的树的搜索问题降⾄搜索⼤⼩为n/2的⼦树。由于树的⼤⼩在每⼀步减半，我们应该预料到，⽤户搜索树的步骤以Θ(log n)增长。⽐起之前的表⽰，它的速度对于⼤型集合有可观的提升。set_contains函数利⽤了树形集合的有序结构：>>> def set_contains(s, v):if s is None:return Falseelif == v:return Trueelif < v:return set_contains(, v)elif > v:return set_contains(, v)向集合添加元素与之类似，并且也需要Θ(log n)的增长度。为了添加值v，我们将v与entry⽐较，来决定v应该添加到right还是left分⽀，以及是否已经将v添加到了合适的分⽀上。我们将这个新构造的分⽀与原始的entry和其它分⽀组合。如果v等于entry，我们就可以返回这个节点。如果我们被要求将v添加到空的树中，我们会⽣成⼀个Tree，它包含v作为entry，并且left和right都是空的分⽀。下⾯是这个函数：>>> def adjoin_set(s, v):if s is None:return Tree(v)if == v:return sif < v:return Tree(, , adjoin_set(, v))if > v:return Tree(, adjoin_set(, v), )>>> adjoin_set(adjoin_set(adjoin_set(None, 2), 3), 1)Tree(2, Tree(1), Tree(3))搜索该树可以以对数步骤数量执⾏，我们这个叙述基于树是“平衡”的假设。也就是说，树的左⼦树和右⼦树都拥有相同数量的相应元素，使每个⼦树含有母树⼀半的元素。但是我们如何确定，我们构造的树就是平衡的呢？即使我们以⼀颗平衡树开始，使⽤adjoin_set添加元素也会产⽣不平衡的结果。由于新添加的元素位置取决于如何将元素与集合中的已有元素⽐较，我们可以预测，如果我们“随机”添加元素到树中，树在平均上就会趋向于平衡。但是这不是⼀个保证。例如，如果我们以空集开始，并向序列中添加 1 到 7，我们就会在最后得到很不平衡的树，其中所有左⼦树都是空的，所以它与简单的有序列表相⽐并没有什么优势。⼀种解决这个问题的⽅式是定义⼀种操作，它将任意的树转换为具有相同元素的平衡树。我们可以在每个adjoin_set操作之后执⾏这个转换来保证我们的集合是平衡的。交集和并集操作可以在树形集合上以线性时间执⾏，通过将它们转换为有序的列表，并转换回来。细节留做练习。Python 集合实现。Python 内建的set类型并没有使⽤上述任意⼀种表⽰。反之，Python 使⽤了⼀种实现，它的成员测试和添加操作是(近似)常量时间的，基于⼀种叫做哈希(散列)的机制，这是其它课程的话题。内建的 Python 集合不能包含可变的数据类型，例如列表、字典或者其它集合。为了能够嵌套集合，Python 也提供了⼀种内建的不可变frozenset类，除了可变操作和运算符之外，它拥有和set相同的⽅法。