如何在Python中将平衡BST转换为完全BST？

问题描述 #

已实现平衡BST的构建，尝试通过将平衡树的叶子节点移至左子树左侧来构建完全BST，但无法正确调整叶子节点。当前生成的树存在节点缺少子节点的情况，期望构建出符合完全二叉树定义的BST——除最后一层外所有层填满，最后一层节点从左到右依次排列。

当前构建平衡BST的函数代码 #

def test(sorted_numbers):
    bst = BST()
    array = []
    test_sort(sorted_numbers, bst, array)
    print("Array from Constructed Balanced BST:", array)
    return bst

def test_sort(sorted_numbers, bst, array):
    def sort(start, end):
        if start > end:
            return None
        if start == 0 and end == len(sorted_numbers) - 1:
            mid = (start + end) // 2  
            mid = min(mid + 3, len(sorted_numbers) - 1) 
        else:
            mid = (start + end + 1) // 2 
        mid_value = sorted_numbers[mid]
        bst.insert(mid_value)
        array.append(mid_value)
        sort(start, mid - 1)
        sort(mid + 1, end)
    sort(0, len(sorted_numbers) - 1)

TreeNode和BST类代码 #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(val, self.root)

    def _insert(self, val, node):
        if val < node.val:
            if node.left:
                self._insert(val, node.left)
            else:
                node.left = TreeNode(val)
        else:
            if node.right:
                self._insert(val, node.right)
            else:
                node.right = TreeNode(val)

    def inorder(self):
        self._inorder(self.root)
        print()

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.val, end=' ')
            self._inorder(node.right)

    def preorder(self):
        self._preorder(self.root)
        print()

    def _preorder(self, node):
        if node:
            print(node.val, end=' ')
            self._preorder(node.left)
            self._preorder(node.right)

    def postorder(self):
        self._postorder(self.root)
        print()

    def _postorder(self, node):
        if node:
            self._postorder(node.left)
            self._postorder(node.right)
            print(node.val, end=' ')

当前生成的树结构 #

__________65_______
                /                   \
           ____34_____           __84___
          /           \         /       \
        _14___       49___     80_     99_
       /      \     /     \   /   \   /   \
       0     21    46    57  66  82  90  132
      / \   /     /     /
     -8 9  18    45    55

期望的完全BST结构（示例） #

__________65_______
                /                   \
           ____34_____           __84___
          /           \         /       \
        _14___       49___     80_     99_
       /      \     /     \   /   \   /   \
       0     21    46    57  66  82  90  132
      / \   /  \   / \    
     -8 9  18  23 45  47                    (just an example of the shape I want)

实现指导 #

核心思路 #

完全二叉树的关键特性是层级填充，最后一层左对齐。直接修改平衡BST的叶子节点位置不可行，正确的做法是从有序数组出发，通过计算每个子树的节点数量，精准确定根节点的位置，递归构建出符合完全二叉树结构的BST。

具体步骤 #

1. 计算当前区间内的总节点数n
2. 计算树的高度h（最大层数，从0开始计数）
3. 确定最后一层的节点数量，进而计算左子树的节点数left_count：
   • 若最后一层节点数不超过上一层最大容量的一半，左子树包含所有最后一层节点加上上一层左半部分的满节点
   • 否则左子树是一个满二叉树
4. 根节点索引为start + left_count，以此为分界递归构建左、右子树

修改后的实现代码 #

替换原有的test和test_sort函数，使用以下代码直接构建完全BST：

def build_complete_bst(sorted_numbers):
    bst = BST()
    def construct(start, end):
        if start > end:
            return None
        # 计算当前区间的节点总数
        n = end - start + 1
        # 计算树的高度（从0开始）
        h = n.bit_length() - 1
        # 上一层的最大节点数的一半（即最后一层的最大容量）
        max_last_level = 1 << (h-1) if h > 0 else 0
        # 最后一层实际的节点数
        actual_last_level = n - ((1 << h) - 1)
        
        # 计算左子树的节点数
        if actual_last_level <= max_last_level:
            left_count = (1 << (h-1)) - 1 + actual_last_level
        else:
            left_count = (1 << h) - 1
        
        # 确定根节点的索引
        root_idx = start + left_count
        root_val = sorted_numbers[root_idx]
        node = TreeNode(root_val)
        
        # 递归构建左、右子树
        node.left = construct(start, root_idx - 1)
        node.right = construct(root_idx + 1, end)
        
        # 设置BST的根节点（仅第一次调用时）
        if start == 0 and end == len(sorted_numbers)-1:
            bst.root = node
        return node
    
    construct(0, len(sorted_numbers)-1)
    return bst

代码说明 #

• 使用位运算1 << k代替2^k，避免浮点运算误差且效率更高
• 直接构建TreeNode并链接，而非依赖BST.insert方法，确保严格按照完全二叉树的结构构建，不受插入顺序影响
• 通过计算左子树节点数，保证根节点的位置能让左子树尽可能填满，符合完全二叉树的层级填充规则

验证方式 #

调用build_complete_bst后，可通过preorder遍历输出节点顺序，或打印树的结构，检查底层节点是否从左到右依次填充，无空缺。

内容的提问来源于stack exchange，提问作者kdr1080k