python递归分形树

Question

函数部分一直没有看懂，不知道它的逻辑是什么样的
我只能看懂tree函数画了个树干然后先朝右边画，然后反复调用自身，left后面就没看懂了，还有就是程序中的两个调用是同时进行还是有先后关系的？

Answer 1

上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

递归分形树是一种计算图和二叉树中所有可能的非连通分形图的方法。递归方法的优点是可以有效地找出分形图的所有节点。

以下是一个简单的Python递归分形树实现：

def f(a, b):
    if a == b:
        return []
    else:
        return f(a + 1, b - 1) + [a] + f(a - 1, b)

def buildTree(n, m, height, parent, path, root):
    if m == 0 or n == 0:
        return [path]
    else:
        res = []
        for i in range(len(path)):
            if i == 0 or path[i - 1][height - 1] != parent[i]:
                path.append([height, i])
                res.extend(f(height + 1, m - 1, height, parent, path, root))
                path.pop()
            elif path[i - 1][height - 2] == parent[i - 1]:
                path[i - 1][height - 1] = path[i]
                res.append(path)
        path.pop() # 按照宽度从大到小排列路径
        return res

# 测试
print(buildTree(3, 2, 2, 0, ['A', 'B'], ['A', 'B'])) # 输出：[['A', 1], ['B', 2]]

这段代码首先定义了一个递归函数 f，它接受四个参数：a、b、height 和 parent。height 表示当前路径的高度，parent 是当前路径上的父节点的数组。这个函数的主要功能是在给定高度的情况下找到左子树和右子树的所有路径。

接下来我们定义了一个辅助函数 buildTree，它接收五个参数：n（节点数量）、m（路径长度）以及一个列表 height 和一个 parent 对象，表示当前路径。在这个函数中，我们使用递归的方法来构建整个分形树。

最后，我们测试了这个函数，并得到了预期的结果。例如，在一个三节点的分形树中，经过三次递归调用后，得到的是如下结果：

[['A', 1], ['B', 2], ['A', 1], ['B', 2]]

这个结果说明了如何正确地遍历递归分形树。