使用 dfs 遍历二叉树，在给定点停止（Python）

Question

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

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

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

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

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

使用 dfs 遍历二叉树，在给定点停止（Python）

Traverse a binary tree using dfs, stopping at a given point (in Python)

python

binary-tree

depth-first-search