如何在不破坏树的情况下从BST弹出所有项目？

因此，我试图创建一种方法，该方法将二进制搜索树的所有节点返回给我，而不删除它们。我想让我的数据结构保持不变。但是我找不到办法！

成功的唯一想法是创建一个pop方法，该方法返回bst的根（克隆），然后删除它。代码是这样的：

    def pop(self):

    #Empty tree.
    if self.root == None:
        return None

    #Copy the root.
    return_node = self.root.clone()

    #Find MAX Node.
    if self.root.left != None:

        #Starting node.
        MAX = self.root.left

        #Find max node.
        while MAX.right != None:
            MAX = MAX.right

        #Swap data with root.
        self.root.swap_data(MAX)

        #Destroy max node.
        MAX.destroy()



    #Find MIN Node.
    elif self.root.right != None:

        #Starting node.
        MIN = self.root.right

        #Find max node.
        while MIN.left != None:
            MIN = MIN.left

        #Swap data with root.
        self.root.swap_data(MIN)

        #Destroy max node.
        MIN.destroy()


    #Else set root to none.
    else:
        self.root = None



    #Return the poped node.
    self.size -= 1
    return return_node

因此，此代码在此循环中的工作原理很吸引人：

node = tree.pop()

while node != None:
    #Do something with current node

    node = tree.pop() #Keep moving.

但是问题在于，这棵树最终将被摧毁。

之后，我认为遍历方法可以解决问题，但我无法成功。

def preorder(self, root):

    if root == None:
        return

    #Do something here.
    #But how am i going to return all the nodes
    #Using this traversal method?

    self.preorder(root.left)
    self.preorder(root.right)

那么，有没有一种方法可以从二进制搜索树中获取所有项目而又不破坏它呢？