Python实现二叉排序树的两种方法：迭代与递归

今天早睡

发布时间：2026-10-15| 6人浏览过

原创

本文详细介绍Python实现二叉排序树的两种核心方法。第一种采用迭代方式，通过循环比较节点大小进行插入；第二种利用递归逻辑，简化代码结构。文章包含完整的代码示例，涵盖节点定义、插入逻辑及中序遍历输出，帮助开发者理解并选择适合的场景。

方法一采用迭代策略实现二叉排序树的构建。首先定义BTree类，初始化时接收数据。若输入为列表，则取首元素作为根节点，并依次调用insert方法插入剩余元素；若为单一数据，则直接赋值。insert方法通过while循环不断比较待插入数据与当前节点数据的大小：若待插入数据小于等于当前节点，则向左子树移动，若无左子树则创建新节点并结束；否则向右子树移动，若无右子树则创建新节点并结束。mid_order方法实现中序遍历，利用栈结构模拟递归过程，依次访问左子树、记录当前节点数据、再访问右子树，最终返回排序后的数据列表。测试数据[5,1,2,3,6,8,9]经BTree处理后，中序遍历结果应为有序序列。

#二叉排序树
class BTree():
    def __init__(self,data):
        self.left = None
        self.right = None
        if type(data) == list:
            self.data = data[0]
            for d in data[1:]:
                self.insert(d)
        else:
            self.data = data
    def insert(self,data):
        bt = self
        while True:
            if data <= bt.data:
                if bt.left == None:
                    bt.left = BTree(data)
                    break
                else:
                    bt = bt.left
            else:
                if bt.right == None:
                    bt.right = BTree(data)
                    break
                else:
                    bt = bt.right
    def mid_order(self):
        res = []
        stack = []
        node = self 
        while node or stack:
            while node:
                stack.append(node) 
                node = node.left
            node = stack.pop()
            res.append(node.data)
            node = node.right
        return res

data = [5,1,2,3,6,8,9]
bt = BTree(data)
print(bt.mid_order())

方法二采用递归策略实现二叉排序树。定义TreeNode类表示节点，包含data、left和right属性。BinaryTree类提供insert方法，该方法接收root和node两个参数。若root为空，直接返回node；否则比较node.data与root.data的大小，若node.data较小，则递归调用insert处理左子树；否则递归处理右子树。最终返回更新后的root。mid_order方法同样使用中序遍历，通过栈结构实现非递归遍历逻辑，确保输出有序序列。测试过程中，首先创建根节点，随后遍历剩余数据，依次调用insert方法构建整棵树，最后通过mid_order输出结果。

class TreeNode(object):
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree(object):
    def insert(self,root, node):
        if root is None:
            return node
        if node.data < root.data:
            root.left = self.insert(root.left, node)
        else:
            root.right = self.insert(root.right, node)
        return root
    def mid_order(self,root):
        node = root
        stack = []
        res = []
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.data)
            node = node.right
        return res
    
data = [5,1,2,3,6,8,9]
root = TreeNode(data[0])
tree = BinaryTree()
for i in data[1:]:
    tree.insert(root,TreeNode(i))
print(tree.mid_order(root))