python - 使用 dfs 遍历二叉树，在给定点停止(在 Python 中)

Question

我正在学习一些基本的计算机科学概念。作为演示，我正在用 Python 创建一个脚本，它将在二叉树上执行各种功能。除了一个特定的功能外，我已经能够成功地编写这些功能中的大部分。

对于从整数数组创建的二叉树，我想对整数进行深度优先搜索，然后返回通过树的路径，直到找到该整数作为数组(最后一个该数组中的数字是正在搜索的数字)。一旦找到该整数的第一个匹配项，我就想停止遍历树。

例如，对于整数 4 的数组 [3,2,4,1,4,6,8,5] 的中序 dfs，它应该返回 [1,2,3,4]

对于整数 5，它应该返回 [1,2,3,4,4,5] 等。

这是我的代码:

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

    def getValue(self):
        return self.value

def buildTree(array):
    print("building tree....")
    root=Node(array[0])
    del(array[0])
    for a in array:
        insert(root,Node(a))
    print("building complete")
    return root

def insert(root,node): 
    if root is None: 
        root = node 
    else: 
        if root.value < node.value: 
            if root.right is None: 
                root.right = node 
            else: 
                insert(root.right, node) 
        else: 
            if root.left is None: 
                root.left = node 
            else: 
                insert(root.left, node) 

def depthFirstSearch(root,target,results,subSearch):
#0:preorder
#1:inorder
#2:postorder
    if root!=None:

        if subSearch==0:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

        depthFirstSearch(root.left,target,results,subSearch)

        if subSearch==1:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

        depthFirstSearch(root.right,target,results,subSearch)

        if subSearch==2:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

    return results

if __name__ == '__main__':
    #stuff that gets our arguments
    #...
    array=[3,2,4,1,4,6,8,5] #we would actually get this as an argument, but using this for example array
    target=4 #example target
    subSearch=1 #using inorder traversal for this example

    root=buildTree(array)
    results=[]
    results=depthFirstSearch(root,target,results,subSearch) 
    print(results) #expected:[1,2,3,4]

Answer 1

好的，这很简单，只需使用一个附加变量标志，然后您的函数就变成了

def depthFirstSearch(root,target,results,subSearch, flag = 0):
#0:preorder
#1:inorder
#2:postorder
    if root!=None:

        if subSearch==0:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

        results, flag =depthFirstSearch(root.left,target,results,subSearch)
        if flag == 1:
            return results, flag
        if subSearch==1:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

        results, flag = depthFirstSearch(root.right,target,results,subSearch)
        if flag == 1:
            return results, flag

        if subSearch==2:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

    return results, flag

这里的 Flag 变为 1，并且随着函数堆栈的缩小而传播，在每次递归调用后保留它们会处理这个问题。

同样在main函数中，函数调用变为

results, _=depthFirstSearch(root,target,results,subSearch)

由于 flag = 0 出现在函数定义中，您只需丢弃第二个变量，您甚至可以使用它来检查是否在树中找到该元素，而不仅仅是打印整棵树如果元素不存在。

如果您有任何疑问或疑虑，请在下方发表评论。