二叉树的测试有效性

Question

我需要一些关于递归函数使用的家庭作业问题的帮助。

我们希望通过嵌套元组表示二叉树，其中每个叶子都有一个字符串作为标签。我们要求叶子用不同的非空字符串标记，并且所有非叶节点都只有两个子节点。例如（（'A'，'B'），'C'），（'D'，（'F'，'E'））是有效的二叉树。

我要写一个递归函数valid_binary_tree（树），检查，即返回true或False，如果给定的树是一个递归元组，表示如上所述的二叉树。

我把这个问题分成两个功能。一个，检查字符串元组是否有效。即，它是不同字符串的元组，例如(' a '，' b '，' c ')，但不是(' a '，' a '，' c ')等。

def validate_string_tuple(t):
"""
Validates whether input is a tuple of distinct strings.
1st step; check if input is a tuple
    if not, return False
2nd step; go through tuple; finds all 'leaves' of the tuple
    If any element is not a string, return False
3rd step; check for uniqueness of 'leaves'
    If length(list_of_leaves) != len(set_of_leaves) return False
"""
if isinstance(t,tuple):
    
    leaves_l=[]
    for i in range(len(t)):
        
        if isinstance(t[i],str) and t[i]!="":
            #Element in the tuple is a string. Append to list of leaves.
            leaves_l.append(t[i])
        else:
            #An element in the tuple is not a string.
            return False
    return (len(leaves_l)==len(set(leaves_l)))

else: return False

这似乎足够有效。我用< code>('ab '，(' c '，' d ')(False)，< code>('a '，' a '，' b '，' c') (False)，< code>('a '，' b '，' c') (True)测试过。

后一部分，为了检查整个树，我想我弄得相当混乱。它适用于某些输入，例如，如果在（（'a'，'b'），'c'），（'e'，（'f'，'g'））上使用，它会返回true。然而，它也在（（'a'，'b'），'c'，'d'）上返回true，这是不应该的（据我从描述中看出的？）。不管怎样，它非常不优雅，我相信它可以得到很大的改进。

def valid_binary_tree(tree):
"""
Checks if a tree (tuple) is a valid binary tree. All non-leaf nodes have
exactly two children, and all leaves are labeled by distinct strings.

- If the initial input is not a tuple, immediately return false.
"""
if not isinstance(tree,tuple):
    return False

#Initially true "list", since, for whatever reason, simply returning False below did not work.
bools=[True]
#Empty list to be populated with leaves (for checking uniqueness later)
leaves_l=[]
def traverse(tree):
    nonlocal leaves_l
    nonlocal bools
    
    if isinstance(tree, str):
        leaves_l+=(tree) #if we've gotten to a simple string (non tuple), it must be a leaf (str)
    
    elif validate_string_tuple(tree): #we've found a legit tuple.
        if len(tree)==2:
            leaves_l+=tree            #The tuple is of length 2, i.e. binary. Append to leaves.
            print('found a valid string tuple;',tree)
        else:
            print('found a string tuple of length >2') #non-binary tuple.
#return False had no effect here, even when the print was called. Hence the bools.append...
            bools.append(False)
    
    else:
        for child in tree: #recursively goes through tree, as it could have arbitrarily many nested tuples.
            traverse(child)

traverse(tree)

#check leaves list vs. set
if len(leaves_l)!=len(set(leaves_l)):
    print('Non-unique labels! Not a valid binary tree')
    return False
#Checks if any non-legit tuples have shown up
if all(bools): 
    return True
else: 
    return False

我也认识到这不可能是最优雅的方式，即使它在某些情况下确实有效。

Answer 1

看起来你把它复杂化了——需要应用一组非常简单的检查来确定给定的树（或该树中的任何给定节点）是否有效。

• 是我们以前见过的叶子吗？False
• 是我们没见过的叶子吗？真
• 不是元组，还是长度不对的元组？False
• 两个子节点都验证吗？（这是递归部分！）

使用非本地和多级间接寻址会使您的代码难以调试，但我可以很容易地想象出一些错误：

• 您的非本地状态从一个调用“泄漏”到下一个调用。（这正是大多数程序员避免全局/non-local的原因；这种类型的bug绝对是可怕的，调试起来也不好玩。）
• 一些重要的数据没有从某个帮助函数传递给需要它的调用方。（同样，由于使用非本地等，这很复杂——当函数契约很混乱时，很难确定谁没有维护它们。）

只需在初始调用上创建集并显式地将其传递给所有递归调用，就可以避免很多麻烦（并大大简化代码）：

>>> def validate_tree(tree, leaves=None):
...     leaves = leaves or {None}
...     if isinstance(tree, str):
...         if tree in leaves:
...             return False  # duplicate leaf
...         leaves.add(tree)
...         return True  # unique leaf
...     if not isinstance(tree, tuple) or len(tree) != 2:
...         return False
...     return all(validate_tree(n, leaves) for n in tree)
...
>>> print(validate_tree(('a','a','b','c')))
False
>>> print(validate_tree(((('a','b'),'c'),('e',('f','g')))))
True
>>> print(validate_tree((('a','b'),'c','d')))
False