Skip to main content
 首页 » 编程设计

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

2024年11月24日17yjmyzz

我正在学习一些基本的计算机科学概念。作为演示,我正在用 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] 

请您参考如下方法:

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

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 出现在函数定义中,您只需丢弃第二个变量,您甚至可以使用它来检查是否在树中找到该元素,而不仅仅是打印整棵树如果元素不存在。

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