2

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

1 回答 1

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 并随着函数堆栈收缩而传播，在每次递归调用处理此问题后保留它们。

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

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

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

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

于 2019-02-20T15:40:26.660 回答