Python 数据结构：二叉搜索树（BST）插入操作

# /*
# Python 数据结构：二叉搜索树（BST）插入操作
# --------------------------------------------------------
# 概念：
# 二叉搜索树是一种有序二叉树，特点：
# 1) 左子树节点值 < 根节点值
# 2) 右子树节点值 > 根节点值
# 3) 左右子树也分别为 BST
#
# 插入操作：
# 1) 从根节点开始比较大小
# 2) 小于根节点 → 进入左子树
# 3) 大于根节点 → 进入右子树
# 4) 递归或迭代找到合适空位插入新节点
# */

# ========================================================
# BST 节点定义
# ========================================================
class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# ========================================================
# BST 插入操作
# ========================================================
class BST:
    def __init__(self):
        self.root = None

    # 插入新节点
    def insert(self, data):
        self.root = self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if node is None:
            return BSTNode(data)
        if data < node.data:
            node.left = self._insert_recursive(node.left, data)
        elif data > node.data:
            node.right = self._insert_recursive(node.right, data)
        # 如果 data == node.data，不插入（保持唯一性）
        return node

    # 中序遍历（升序输出）
    def inorder_traversal(self, node=None):
        if node is None:
            node = self.root
        result = []
        def _inorder(n):
            if n:
                _inorder(n.left)
                result.append(n.data)
                _inorder(n.right)
        _inorder(node)
        return result

# ========================================================
# 示例演示
# ========================================================
bst = BST()
for value in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(value)

print("中序遍历结果（升序）：", bst.inorder_traversal())

# 插入重复值（不影响 BST）
bst.insert(70)
print("插入重复值 70 后中序遍历：", bst.inorder_traversal())

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) BST 插入操作通过比较节点值递归找到合适位置；
# 2) 左子树值 < 根节点值，右子树值 > 根节点值；
# 3) 可选择递归或迭代实现插入；
# 4) 插入后，中序遍历结果为升序序列；
# 5) 对于重复元素可选择忽略或计数，保持 BST 唯一性。
# */
#
# 中序遍历结果（升序）：
# [20, 30, 40, 50, 60, 70, 80]
# 插入重复值 70 后中序遍历：
# [20, 30, 40, 50, 60, 70, 80]