C++从文件重建二叉树：十六进制读取与#替代-1标记求助

看起来你在二叉树重建的输入处理上遇到了两个小坎——十六进制数字读取和空节点标记从-1改为#的问题，我来帮你梳理下解决方案，应该能快速解决你的问题。

核心问题分析 #

你之前尝试替换标记失败，大概率是因为仍然在按整数类型读取输入：#是字符，无法被int类型的读取操作正确解析，会导致输入流状态异常，进而中断后续的二叉树构建逻辑。而十六进制数字的读取则需要我们告诉程序：不要只认十进制，要支持十六进制格式。

完整解决方案代码 #

下面是修改后的核心代码，同时解决两个问题：

#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归构建二叉树的辅助函数
TreeNode* buildTreeHelper(std::istream& input) {
    std::string token;
    // 读取下一个标记（按空格分割）
    if (!(input >> token)) {
        return nullptr;
    }

    // 处理空节点标记#
    if (token == "#") {
        return nullptr;
    }

    // 处理十六进制/十进制数字转换
    int nodeVal;
    try {
        size_t parsePos;
        // base=0表示自动识别进制：0x开头为十六进制，否则为十进制
        nodeVal = std::stoi(token, &parsePos, 0);
        // 检查是否整个token都是有效数字（避免类似"12a"这种无效输入）
        if (parsePos != token.size()) {
            throw std::invalid_argument("Invalid characters in token");
        }
    } catch (const std::invalid_argument& e) {
        std::cerr << "Error parsing token '" << token << "': " << e.what() << std::endl;
        return nullptr;
    } catch (const std::out_of_range& e) {
        std::cerr << "Token '" << token << "' is out of integer range" << std::endl;
        return nullptr;
    }

    // 创建当前节点并递归构建左右子树
    TreeNode* currentNode = new TreeNode(nodeVal);
    currentNode->left = buildTreeHelper(input);
    currentNode->right = buildTreeHelper(input);
    return currentNode;
}

// 从文件读取并构建二叉树
TreeNode* buildTreeFromFile(const std::string& filePath) {
    std::ifstream inputFile(filePath);
    if (!inputFile.is_open()) {
        std::cerr << "Failed to open file: " << filePath << std::endl;
        return nullptr;
    }
    return buildTreeHelper(inputFile);
}

// 测试用例：前序遍历打印二叉树
void preOrderPrint(TreeNode* root) {
    if (!root) {
        std::cout << "# ";
        return;
    }
    std::cout << root->val << " ";
    preOrderPrint(root->left);
    preOrderPrint(root->right);
}

int main() {
    TreeNode* root = buildTreeFromFile("tree_input.txt");
    preOrderPrint(root);
    // 记得后续要释放二叉树内存，避免泄漏
    return 0;
}

关键修改点说明 #

1. 空节点标记处理

   • 把原来的int类型读取改为string类型读取，这样可以直接识别#字符
   • 当读取到的标记等于#时，直接返回nullptr表示空节点

2. 十六进制数字读取

   • 使用std::stoi函数并指定第三个参数为0，该参数表示自动识别进制：
     • 如果标记以0x或0X开头，按十六进制解析
     • 否则按十进制解析
   • 增加了异常捕获和有效性检查，避免无效输入导致程序崩溃

测试示例文件 #

修改后的程序可以处理如下格式的输入文件（混合十进制和十六进制）：

0xA 2 4 # # 0x5 # # 3 # #

运行后前序打印会输出：10 2 4 # # 5 # # 3 # # （因为0xA是十进制的10，0x5是十进制的5）

额外注意事项 #

• 记得在程序结束时释放二叉树的内存，避免内存泄漏（可以写一个递归的销毁函数）
• 如果输入文件中存在其他分隔符（比如逗号），需要修改读取逻辑，比如用getline配合stringstream分割

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