Python二叉树递归插入函数实现遇困，求技术指点

原代码的核心问题 #

1. 递归未传递当前节点：每次递归都从根节点self.root开始，无法沿着树的分支向下遍历，导致插入逻辑完全错误。
2. 重复创建节点：每次调用insert_rec都将传入的Star对象转为TreeNode，递归调用时会再次转换，生成重复的节点实例。
3. 分支逻辑混乱：处理完左分支后直接进入右分支判断，无论左分支是否插入成功，都会尝试插入右分支，违背二叉搜索树的规则。
4. 根节点处理不完整：根节点为空时设置self.root后未终止函数，后续代码会继续执行，引发不必要的判断。

修正后的递归插入实现 #

我们需要调整递归逻辑，让函数沿着树的分支向下遍历，同时避免重复创建节点。以下是修正后的完整代码：

import time
import csv

class Star:
    def __init__(self, hvg_db, name, mag, spectral, habit, dist):
        self.hvg_db = hvg_db 
        self.display_name = name
        self.magnitude = mag 
        self.spectral_class = spectral  
        self.habitable = habit
        self.distance_parsecs = dist 

class TreeNode:
    def __init__(self, star):
        self.left = None
        self.right = None
        self.star_info = star
        self.name = "N" + str(self.star_info.hvg_db)
        self.key = star.display_name

class Tree:
    def __init__(self, name):
        self.name = name
        self.node_num = 0
        self.node_list = []
        self.root = None

    def insert_rec(self, star):
        # 仅在最外层创建TreeNode，避免重复实例化
        new_node = TreeNode(star)
        # 调用辅助递归函数，从根节点开始遍历
        self.root = self._insert_rec_helper(self.root, new_node)
    
    def _insert_rec_helper(self, current_node, new_node):
        # 递归终止条件：当前节点为空，返回新节点作为子节点
        if current_node is None:
            print(f"插入节点: {new_node.key}")
            self.node_num += 1
            return new_node
        
        # 二叉搜索树规则：键小于当前节点，递归左子树
        if new_node.key < current_node.key:
            current_node.left = self._insert_rec_helper(current_node.left, new_node)
        # 键大于当前节点，递归右子树（键唯一，无需处理等于的情况）
        elif new_node.key > current_node.key:
            current_node.right = self._insert_rec_helper(current_node.right, new_node)
        
        # 返回当前节点，维持树的结构
        return current_node

def main():
    star_tree = Tree("Star Catalog")

    with open('HabHYG_short.csv', 'r') as csvfile:
        lines = csv.reader(csvfile, delimiter=',')
        next(csvfile)  # 跳过表头
        
        t0 = time.perf_counter_ns()
        obs_processed = 0

        for row in lines:
            # 注意参数顺序匹配Star的__init__：hvg_db, name, mag, spectral, habit, dist
            this_star = Star(row[0], row[3], row[16], row[11], row[2], row[12])
            star_tree.insert_rec(this_star)
            obs_processed += 1
        
        t1 = time.perf_counter_ns()
        print(f"处理完成：共插入{obs_processed}颗恒星，耗时{t1 - t0}纳秒")

if __name__ == "__main__":
    main()

关键逻辑说明 #

• 辅助递归函数：_insert_rec_helper负责实际的递归遍历，参数为当前节点和要插入的新节点，每次递归返回更新后的节点，上层调用将其挂载到左/右子节点。
• 递归终止条件：当current_node为空时，说明找到了插入位置，返回新节点。
• 二叉搜索树规则：严格按照键的大小关系选择左/右子树递归，确保树的结构符合要求。
• 避免重复创建节点：仅在insert_rec最外层创建一次TreeNode，递归时直接传递该节点。

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