Python 搜索二叉树的递归函数

Question

Python 非常新，我正在尝试了解二叉树的递归。我已经实现了一个非常简单的树，它很有趣地将英文字符映射到二进制（1 和 0）。我只使用了一个非常简单的结构，因为我正在努力思考一个我已经设定好的更复杂的问题。我想如果我能理解我的例子那么我应该能够离开并看看我自己设置的问题。

下面创建了 class BinaryTree 和这个

的一个实例

class BinaryTree:
    """A rooted binary tree"""
    def __init__(self):
        self.root = None
        self.left = None
        self.right = None

def is_empty(testtree: BinaryTree) -> bool:
        """Return True if tree is empty."""
        return testtree.root == testtree.left == testtree.right == None

def join(item: object, left: BinaryTree, right: BinaryTree) -> BinaryTree:
    """Return a tree with the given root and subtrees."""
    testtree = BinaryTree()
    testtree.root = item
    testtree.left = left
    testtree.right = right
    return testtree

EMPTY = BinaryTree()
C = join('C',EMPTY,EMPTY)
D = join('D',EMPTY,EMPTY)
E = join('E',EMPTY,EMPTY)
F = join('F',EMPTY,EMPTY)
A = join('A',C,D)
B = join('B',E,F)
BINARY = join('START',B,A)

我想象如下

Visualisation of the Binary tree

现在我正在尝试创建一个函数，它将接受两个输入，一个二叉树和一个字符，输出将是对应字母的二进制代码（例如，D = " 10 "）。我输出为字符串而不是整数。我的功能和测试用例如下

# global variable
result = ''

#Convert binary to letter
def convert_letter(testtree: BinaryTree, letter: str) -> str:
    global result
    if testtree == None:
        return False
    elif testtree.root == letter:
        return True        
    else:  
        if convert_letter(testtree.left, letter) == True:
            result += "1"
            return result
        elif convert_letter(testtree.right, letter) == True:
            result += "0"
            return result
     
#Test
test = 'D' #Return '10'
convert_letter(BINARY, test)

不幸的是，这就是我碰壁的地方。我曾尝试在函数中初始化一个空字符串，但每次迭代函数时都会覆盖字符串。非常感谢任何帮助。

Answer 1

我冒昧地稍微简化了您的代码，如果您对它的工作原理有任何疑问，请告诉我。

class node:
    """A rooted binary tree"""
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

C = node('C')
D = node('D')
E = node('E')
F = node('F')
A = node('A',C,D)
B = node('B',E,F)
BINARY = node('START',B,A)

def convert_letter(n,letter):
    if n.value == letter:
        return "1"+(convert_letter(n.left,letter) if not n.left is None else "")+(convert_letter(n.right,letter)if not n.right is None else "")
    else:
        return "0"+(convert_letter(n.left,letter) if not n.left is None else "")+(convert_letter(n.right,letter)if not n.right is None else "")

def walk(n):
    return n.value+(walk(n.left) if not n.left is None else "")+(walk(n.right) if not n.right is None else "")

test = 'D'
print(convert_letter(BINARY, test))
print(walk(BINARY))

Answer 2

这不是我个人构建答案的方式，但我认为它最接近您的尝试。你的答案的缺点只是你只 returning 一个值，但有点跟踪两个值。请注意，我冒昧地更正了：

BINARY = join('START',A,B)

让我们将您的方法修改为 return 指示是否找到字母的布尔值以及路径指示符。

def convert_letter2(testtree: BinaryTree, letter: str):
    if not testtree:
        return (False, "")

    if testtree.root == letter:
        return (True, "")

    test, val = convert_letter2(testtree.left, letter)
    if test:
        return (True, "1" + val)

    test, val = convert_letter2(testtree.right, letter)
    if test:
        return (True, "0" + val)

    return (False, "")

那么如果我们：

print(convert_letter2(BINARY, "D")[1])

我们应该回去"10"

Answer 3

问题是您的函数有时 return 布尔值，有时是字符串，有时 None。所以用这个代码：

    if convert_letter(testtree.left, letter) == True:
        result += "1"
        return result
    elif convert_letter(testtree.right, letter) == True:
        result += "0"
        return result

...您没有捕获所有成功的搜索，因为成功的搜索会 return 实际的字符串“0”和“1”，这显然不是 True。在那种情况下，执行没有 else 去 returns None -- 即使在更深的节点中找到了字母。

您的函数不应该 return 布尔值 -- 也不匹配类型提示。它应该是一个字符串（结果）。您可以保留 None 以表示未找到该字母。

其他一些问题：

result += "0" 将追加数字，但由于您已经进行了递归调用，因此需要 prepend 这个数字——因为你现在在树上更高了。
树的初始化与图片中的不同：A 应该是左子树，而不是右子树。所以应该是join('START', A, B)

通过这些修复，您将获得以下代码：

def convert_letter(testtree: BinaryTree, letter: str) -> str:
    global result
    if testtree is None:
        result = None  # Not found here 
    elif testtree.root == letter:
        result = ''  # Found! Start a path
    elif convert_letter(testtree.left, letter) is not None:
        result = "1" + result  # Prepend
    elif convert_letter(testtree.right, letter) is not None:
        result = "0" + result  # Prepend
    else:
        result = None  # Not found here
    return result

如果您还正确使用 join('START', A, B)，则输出将为 10。

更好的做法

有些事情你可以做得更好：

不要使用全局变量来存储函数结果。当你 return 时，你可以捕获从递归调用中获得的 result 作为局部变量，添加到它前面，然后 return再次.
EMPTY 的定义使您的树变得不必要地大。只需使用 None 表示一棵空树。
不要调用节点的值root。一棵有根树只有一个根，它是一个节点，而不是一个节点的值。所以将该属性称为 value 或 data，而不是 root.
join 函数很好，但为什么不使用该函数的构造函数呢？构造函数可以将这些参数作为可选参数并立即使用这些参数初始化 left 和 right 属性。
convert_letter 函数上方的 code-comment 与函数的作用相反。

考虑到所有这些因素，您的代码可能如下所示：

class BinaryTree:
    def __init__(self, value, left: 'BinaryTree'=None, right: 'BinaryTree'=None):
        self.value = value
        self.left = left
        self.right = right

def convert_letter(tree: BinaryTree, letter: str) -> str:
    if not tree:
        return # Not found here, return None
    if tree.value == letter:
        return ""  # Bingo: return an empty path
    # No more global. path is a local variable
    path = convert_letter(tree.left, letter)
    if path is not None:
        return "1" + path
    path = convert_letter(tree.right, letter)
    if path is not None:
        return "0" + path

# Look how nice it is to create a tree using the constructor arguments
binary = BinaryTree("Start",
    BinaryTree("A",
        BinaryTree("C"), BinaryTree("D")
    ),
    BinaryTree("B",
        BinaryTree("E"), BinaryTree("F")
    )
)

# Test
test = 'D'
print(convert_letter(binary, test))  # 10

Python 搜索二叉树的递归函数

Python recursive function to search a binary tree

python

recursion

binary-tree

更好的做法