Python中完全二叉树deleteNode函数异常，删除节点错误求助

我看了你的完全二叉树实现，问题出在deleteNode函数的逻辑上——现在的代码根本没定位到要删除的节点的正确位置，只是错误地把一个类变量self.item设为None，完全没有维护完全二叉树的结构，这自然会导致删错节点、树无法正常运作的问题。

完全二叉树删除节点的正确逻辑 #

因为你用数组来存储完全二叉树（这是完全二叉树的标准存储方式），删除节点需要遵循以下规则来保持树的完全性：

1. 找到要删除元素在数组中的索引位置
2. 如果树只有根节点且要删除的是根节点，直接清空树
3. 否则，用数组最后一个元素的值覆盖要删除节点的值（完全二叉树的最后一个节点是最底层最右侧的节点，用它替换不会破坏树的完全结构）
4. 移除数组的最后一个元素，同时更新节点计数count

修改后的完整代码 #

import math
class MyCompleteTree:
    def __init__ (self):
        self.arr = []
        self.arr.append(None)  # 索引从1开始，方便计算左右子节点
        self.count = 0
    def isEmpty(self):
        return self.count == 0
    def addNode(self, item):
        self.arr.append(item)
        self.count += 1
    def getHeight(self):
        return int(math.log2(self.count)) + 1 if self.count > 0 else 0
    def preorder(self, index):
        if index <= self.count:
            print(self.arr[index], end=' ')
            self.preorder(index * 2)
            self.preorder(index * 2 + 1)
    def inorder(self, index):
        if index <= self.count:
            self.inorder(index * 2)
            print(self.arr[index], end=' ')
            self.inorder(index * 2 + 1)
    def inorderFromRoot(self):
        self.inorder(1)
    def postorder(self, index):
        if index <= self.count:
            self.postorder(index * 2)
            self.postorder(index * 2 + 1)
            print(self.arr[index], end=' ')
    def printLeafNode(self, index):
        visit = False
        if index * 2 <= self.count:
            visit = True
            self.printLeafNode(index * 2)
        if index * 2 + 1 <= self.count:
            visit = True
            self.printLeafNode(index * 2 + 1)
        if not visit:
            print(self.arr[index], end=' ')
    def deleteNode(self, item):
        if self.isEmpty():
            print("Tree is empty")
            return
        
        # 找到要删除元素的索引
        try:
            del_index = self.arr.index(item)
            # 排除索引0的占位元素
            if del_index == 0:
                print("No nodes were found in the tree")
                return
        except ValueError:
            print("No nodes were found in the tree")
            return
        
        # 如果是最后一个节点，直接删除
        if del_index == self.count:
            self.arr.pop()
            self.count -= 1
            print(item, "Deleted")
            return
        
        # 用最后一个节点的值覆盖要删除的节点
        self.arr[del_index] = self.arr[-1]
        # 删除最后一个节点
        self.arr.pop()
        self.count -= 1
        print(item, "Deleted")

代码修改说明 #

1. 简化isEmpty函数：用更简洁的布尔判断替代分支逻辑
2. 优化getHeight函数：处理树为空的边界情况，避免log2(0)报错
3. 重写deleteNode函数：
   • 先判断树是否为空，提前返回提示
   • 通过arr.index(item)精准定位目标节点索引，同时捕获元素不存在的异常
   • 针对要删除的是最后一个节点的情况做单独处理
   • 核心逻辑：用最后一个节点的值覆盖目标节点，再移除最后一个节点，确保完全二叉树的结构不被破坏

测试示例 #

# 创建树并添加节点
tree = MyCompleteTree()
for num in [10, 20, 30, 40, 50, 60]:
    tree.addNode(num)

print("删除前中序遍历：")
tree.inorderFromRoot()  # 输出：40 20 50 10 60 30

tree.deleteNode(20)
print("\n删除20后中序遍历：")
tree.inorderFromRoot()  # 输出：40 60 50 10 30

内容的提问来源于stack exchange，提问作者박진수