Python面向对象实现二叉树：搜索函数实例比较报错问题

问题重现 #

使用面向对象实现二叉树时，搜索根节点（如27）正常，但搜索其他节点（如19）会触发以下类型错误：

Traceback (most recent call last):
  File "e:\Py School\Binary Trees\Binary Tree (Classes).py", line 43, in <module>
    x = tree.search(num)
  File "e:\Py School\Binary Trees\Binary Tree (Classes).py", line 24, in search  
    if copy1 < copy2:
TypeError: '<' not supported between instances of 'int' and 'Node'

用户的Node类代码：

class Node:
    def __init__(self,item):
        self.left = None
        self.right = None
        self.item = item
    def insert(self, item):
        if self.item:
            if item < self.item:
                if self.left is None:
                    self.left = Node(item)
                else:
                    self.left.insert(item)
            elif item > self.item:
                if self.right is None:
                   self.right = Node(item)
                else:
                    self.right.insert(item)
        else:
            self.item = item
    def search(self, item):
        while self.item != item:
            copy1 = item
            copy2 = self.item
            if copy1 < copy2:
                self.item = self.left
            else:
                self.item = self.right
            if self.item is None:
                return False
        return self.item

测试代码：

tree = Node(27)

tree.insert(19)
tree.insert(36)
tree.insert(42)
tree.insert(16)

print("Do you wish to search for a number in the tree?")
flag = 1
while True:
    num = int(input("Please enter the number you wish to search for \n"))
    x = tree.search(num)
    if x == False:
        print("The number is not present")
    else:
        print("The number is present", x)
    flag = int(input("If you wish to continue searching, enter 1, else enter 0 \n"))

问题根源 #

搜索函数的致命错误在于修改了self.item的类型：

• 初始时self.item是int类型的节点值
• 当执行self.item = self.left时，把Node实例赋值给了self.item
• 下一次循环时，copy2 = self.item变成了Node对象，和int类型的copy1比较自然触发类型错误

这种写法还会破坏原树的节点数据，导致后续操作全部异常。

修正方案 #

不要修改self.item，而是用一个临时变量追踪当前遍历的节点：

class Node:
    def __init__(self,item):
        self.left = None
        self.right = None
        self.item = item
    def insert(self, item):
        if self.item:
            if item < self.item:
                if self.left is None:
                    self.left = Node(item)
                else:
                    self.left.insert(item)
            elif item > self.item:
                if self.right is None:
                   self.right = Node(item)
                else:
                    self.right.insert(item)
        else:
            self.item = item
    def search(self, item):
        # 用current变量追踪当前节点，不修改self本身
        current = self
        while current is not None and current.item != item:
            if item < current.item:
                current = current.left
            else:
                current = current.right
        # 如果找到返回节点值，否则返回False
        return current.item if current else False

说明 #

• 使用current变量遍历树，不会修改原节点的任何属性，避免破坏树结构
• 循环条件同时判断current是否为None，防止空指针访问
• 最终返回逻辑更清晰：找到则返回节点值，找不到返回False

测试修正后的代码，搜索19、36等节点都能正常返回结果，且不会破坏原树结构。

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