二叉树：列表到节点的列表和递归引用

Question

我一直在尝试将列表格式的列表转换为由节点和引用组成的二叉树对象。到目前为止，我有3种情况，左右节点为空，左为空，右为空。问题是每当我测试我的函数时，递归都不起作用。我的意思是递归深度仅在 returns 转换后的二叉树之前一级。

argument =  ['a', ['b', ['d', None, None],['f', None, None]], ['c', None, ['h', None, None]]]

def linkedlisttobinarytree (l):
    '''
    list of lists -> (nodes and references)
    Takes a list of lists and returns a binary tree in nodes and references form
    '''
    bt = BinaryTree(l[0])
    if (l[1] and l[2]) == None:
        return bt.getRootValue()
    elif l[1] != None and l[2] == None:
        bt.left = ll2nr(l[1])
    elif l[2] != None and l[1] == None:
        bt.right = ll2nr(l[2])
    return bt

例如，当我将变量 'argument' 发送到我的方法时，它只产生 'a' 作为根节点并且只产生 'a'，该方法只转换第一个元素'argument'。有人能解释一下为什么我的递归深度这么浅吗？

Answer 1

我认为那是因为当 l[1] 和 l[2] 不是 none 时，您没有定义操作。所以当你把参数传给函数时，它把'a'放到root的key上，发现定义的条件中有none匹配了，那么这个函数什么都不做就存在了。因此 return 值仅包含 'a' 。试试这个：

if (l[1] and l[2]) == None: return bt.getRootValue() elif l[1] != None and l[2] == None: bt.left = ll2nr(l[1]) elif l[2] != None and l[1] == None: bt.right = ll2nr(l[2]) else: bt.left = ll2nr(l[1]) bt.right = ll2nr(l[2])

Answer 2

正在检查您的功能：

(...)
elif l[1] != None and l[2] == None:
    bt.left = ll2nr(l[1])
elif l[2] != None and l[1] == None:
    bt.right = ll2nr(l[2])

您可以很容易地看到添加 print (l[1], l[2]) 代替点，这两个条件都不满足。

l[1] == ['b', ['d', None, None], ['f', None, None]]
and
l[2] == ['c', None, ['h', None, None]]

所以，第一个条件是真假 ==> 假，第二个条件也是真假 ==> 假。因此函数 returns bt.

如果你把它改成类似

if l[1] != None: # You might simply write "if l[1]:" as well...
    bt.left = ll2nr(l[1])
if l[2]:         # ...like this
    bt.right = ll2nr(l[2])

它可能会更好用。

我把你的函数改成这样：

def make_tree(l):
    bt = BinaryTree(l[0])
    #if (l[1] and l[2]) == None:
    #    return bt.getRootValue()
    if l[1]:
        bt.left = make_tree(l[1])
    if l[2]:
        bt.right = make_tree(l[2])
    if not l[1] and not l[2]:
        bt.left = "*"
        bt.right = "*"
    return bt

def printer(node, depth=0):
    indent = '\t' * depth
    if node:
        if isinstance(node, basestring):
            print ("{}{}={}".format(indent, node, depth))
        else:
            print ("{}{}={}".format(indent, node.key, depth))
            printer(node.left, depth + 1)
            printer(node.right, depth + 1)
    else:
        print ("{}*={}".format(indent, depth))

并获得了漂亮的打印输出：

二叉树：列表到节点的列表和递归引用

Binary Tree: List of List to Nodes and Reference with Recursion

python

recursion

binary-tree

list