在Python中递归返回由列表表示的树的节点

Question

我必须创建一个列表，其中包含按升序排列的二叉树的编号。但是我有一些困难要做。而且，我必须使用递归

下面是我的二进制数据树的一个示例：

t1 = [[[None,4,None],5,[None,5,None]],6,[None,7,[None,8,None]]]

我的函数返回：

[2, 5, 5, 6, 7, 8]

我当时所做的：

def recursive_course(t):
    """  Return  list which contain the numbers of t in order from a binary tree - recursive"""
    liste=[]
    for i in t:
        if isinstance(i,int):
            liste.append(i)
        if isinstance(i,list):
            for j in i:
                if isinstance(j,int):
                    liste.append(j)
                if isinstance(j,list):
                    for h in j:
                        if isinstance(h,int):
                            liste.append(h)
    if t != None:
        liste.append(t[1])
    return liste

它是有效的，但不是完全有效

我会解释我的意思：
在我的示例中，我的函数可以工作，但问题是，当我添加子树时，我的函数不能工作，因为我需要的树的数量与“for”循环的数量一样多。这就是为什么我必须使用递归方法，但我不知道如何使用上面的代码实现这一点

Answer 1

递归是一种函数遗产，因此将其与函数风格结合使用会产生最好的结果。由于二叉树可以嵌套到任何深度，因此不能依赖固定数量的嵌套for循环。然而，这并没有问题，因为函数样式使用递归来循环，而不是for语句

让我们首先为我们的二叉树模块btree编写一些基本函数。定义像is_empty、left、right和value这样的函数可以让我们很容易地了解有关树的简单信息，并使用有意义的标识符来处理它们-

# btree.py

def is_empty (t):
  return not t

def left (t):
  if is_empty(t):
    raise RuntimeError("cannot access left of empty tree")
  else:
    return t[0]

def right (t):
  if is_empty(t):
    raise RuntimeError("cannot access right of empty tree")
  else:
    return t[2]

def value (t):
  if is_empty(t):
    raise RuntimeError("cannot access value of empty tree")
  else:
    return t[1]

现在我们要定义inorder，它将按顺序遍历树的节点。首先访问left（最小）节点，然后访问right（最大）节点-

# btree.py (continued)

def inorder (t):
  if is_empty(t):
    return
  else:
    yield from inorder(left(t))  # recursion
    yield value(t)
    yield from inorder(right(t)) # recursion

现在，我们可以使用新的二叉树编写main程序-

# main.py

from btree import inorder

t1 = [[[None,4,None],5,[None,5,None]],6,[None,7,[None,8,None]]]

print(list(inorder(t1)))

[4, 5, 5, 6, 7, 8]