从递归二叉树搜索返回数组

Question

你好我做了一个简单的二叉树并添加了一个前序遍历方法。在抛出一些想法之后，我陷入了寻找一种方法 return 来自数组中 traverse_pre() 方法的每个值的方法。

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

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        if self.left:
            self.left.traverse_pre()
        print(self.value)

        if self.right:
            self.right.traverse_pre()


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

Tree.traverse_pre()

如何将 traverse_pre() 函数修改为 return 由节点值组成的数组。有没有这个过程的一个很好的例子让我进一步理解这一点，我对如何在递归中将值附加到数组有点困惑。

Answer 1

这是我的做法 - 所有分支 return 它们的子元素列表。

如果节点没有子元素，它只有 return 自己的值。否则，它还包含来自子元素的元素。

Extend将子节点结果列表中的所有元素添加到父节点结果列表中。

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

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        results = []

        if self.left:
            results.extend(self.left.traverse_pre())

        results.append(self.value)

        if self.right:
            results.extend(self.right.traverse_pre())

        return results


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

print(Tree.traverse_pre())

Answer 2

您可以将数组用作全局变量，并且在 traverse_pre() 函数中您可以将值附加到该数组，而不是打印出来。

arr = []
class BST:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        if self.left:
            self.left.traverse_pre()
        arr.append(self.value)

        if self.right:
            self.right.traverse_pre()


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

Tree.traverse_pre() 
print(arr)

Answer 3

我会这样处理问题：

def traverse_pre(self):
    rslt = [self.value]
    if self.left:
        rslt.extend(self.left.traverse_pre())

    if self.right:
        rslt.extend(self.right.traverse_pre())

Answer 4

我不建议使用 .append 或 .extend 将整个树复制到中间列表。而是使用 yield 这使得你的树可迭代并且能够直接使用许多内置的 Python 函数 -

class BST:
    # ...
    def preorder(self):
        # value
        yield self.value
        # left
        if self.left: yield from self.left.preorder()
        # right
        if self.right: yield from self.right.preorder()

我们可以简单地重新排序这些行以提供不同的遍历，例如 inorder -

class BST:
    # ...
    def inorder(self):
        # left
        if self.left: yield from self.left.inorder()
        # value
        yield self.value
        # right
        if self.right: yield from self.right.inorder()

和postorder-

class BST:
    # ...
    def postorder(self):
        # left
        if self.left: yield from self.left.postorder()
        # right
        if self.right: yield from self.right.postorder()
        # value
        yield self.value

生成器的使用提供了控制反转。不是由遍历函数决定每个节点会发生什么，而是让调用者决定要做什么。如果列表确实是所需的目标，只需使用 list -

list(mytree.preorder())

# => [ ... ]

也就是说，您的其余代码还有改进的余地。无需直接在 BST class 中改变节点和缠结 self 上下文和递归方法。使用薄 class 包装器的功能方法将使您更容易扩展树的功能。有关此技术的更多信息，请参阅 .

如果您需要促进显着大小的树，可能需要不同的遍历技术。只要在评论中提问，就会有人帮你找到你要找的东西。

从递归二叉树搜索返回数组

Returning Array from Recursive Binary Tree Search

python

recursion

binary-tree

tree-traversal

binary-search-tree