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

Question

我一直在尝试将列表格式转换为包含节点和引用的二叉树对象。到目前为止，我有3个例子，左边和右边的节点是空的，左边是空的，右边是空的。问题是每当我测试函数时，递归都不起作用。我的意思是递归深度在返回转换后的二叉树之前只有一个级别。在

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

检查您的功能：

(...)
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])来代替点，这两个条件都不满足。在

^{pr2}$

所以，第一个条件是true and false==>；false，第二个条件也是true and false==>；false。因此函数返回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))

打印出来了：

a=0
    b=1
        d=2
            *=3
            *=3
        f=2
            *=3
            *=3
    c=1
        *=2
        h=2
            *=3
            *=3

Answer 2

我想那是因为你没有定义动作，当l[1]和l[2]不是没有的时候。所以当你把参数传递给函数时，它会把'a'放到根的键上，然后发现定义的所有条件都不匹配，那么函数就不做任何事情就存在了。因此返回值只包含'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])