如何将vector实现的二叉树转为邻接矩阵写入ASCII文本文件？

一、二叉树转层次化ASCII文件（匹配你给出的示例格式） #

根据你描述的vector<Node>存储结构（按完全二叉树索引规则，父节点i的子节点为2*i和2*i+1），我们可以按层次遍历二叉树，空节点用@占位的方式生成目标输出，具体实现如下：

1. 核心逻辑 #

• 先计算树的高度，确定输出的行数（每一层对应一行）
• 对每一层的每个位置，检查对应索引是否存在有效节点：存在则输出节点标识（比如d值、索引或自定义字母），不存在则输出@
• 使用std::ofstream将内容写入ASCII文件

2. 代码实现 #

#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <algorithm>

struct Node {
    int p;
    std::vector<int> c;
    float d;
};

// 计算二叉树的高度（根节点为第1层）
int getTreeHeight(const std::vector<Node>& tree) {
    if (tree.empty()) return 0;
    int maxDepth = 0;
    for (size_t idx = 0; idx < tree.size(); ++idx) {
        int depth = 0;
        int curr = idx;
        while (tree[curr].p != -1) { // 约定根节点的p为-1
            curr = tree[curr].p;
            depth++;
        }
        maxDepth = std::max(maxDepth, depth);
    }
    return maxDepth + 1;
}

// 生成层次化输出并写入文件
void writeTreeHierarchy(const std::vector<Node>& tree, const std::string& filePath) {
    std::ofstream outFile(filePath);
    if (!outFile.is_open()) {
        std::cerr << "无法打开目标文件" << std::endl;
        return;
    }

    int height = getTreeHeight(tree);
    for (int level = 1; level <= height; ++level) {
        int startIdx = std::pow(2, level - 1) - 1;
        int nodeCount = std::pow(2, level - 1);
        
        for (int i = 0; i < nodeCount; ++i) {
            size_t currIdx = startIdx + i;
            if (i != 0) outFile << " ";
            
            // 判断是否为有效节点：根节点或父节点索引有效
            bool isValid = (currIdx < tree.size()) && (currIdx == 0 || tree[currIdx].p != -2);
            // 这里约定无效节点的p为-2，可根据你的实际存储规则调整
            if (isValid) {
                // 可替换为自定义标识：比如char('A' + currIdx) 或 std::to_string(currIdx)
                outFile << tree[currIdx].d;
            } else {
                outFile << "@";
            }
        }
        outFile << "\n";
    }

    outFile.close();
}

// 测试示例
int main() {
    std::vector<Node> tree;
    // 根节点0
    tree.push_back({-1, {1, 2}, 1.0f});
    // 节点1（左子节点）
    tree.push_back({0, {}, 2.0f});
    // 节点2（右子节点）
    tree.push_back({0, {}, 3.0f});

    writeTreeHierarchy(tree, "tree_output.txt");
    return 0;
}

二、标准邻接矩阵生成 #

如果你需要的是n×n的标准邻接矩阵（行和列对应节点，有边则显示节点标识，无边则显示@），可以使用以下实现：

void writeAdjacencyMatrix(const std::vector<Node>& tree, const std::string& filePath) {
    std::ofstream outFile(filePath);
    if (!outFile.is_open()) {
        std::cerr << "无法打开目标文件" << std::endl;
        return;
    }

    size_t nodeNum = tree.size();
    // 写入表头（节点标识）
    for (size_t i = 0; i < nodeNum; ++i) {
        if (i != 0) outFile << " ";
        outFile << char('A' + i);
    }
    outFile << "\n";

    // 写入每一行的邻接关系
    for (size_t i = 0; i < nodeNum; ++i) {
        for (size_t j = 0; j < nodeNum; ++j) {
            if (j != 0) outFile << " ";
            // 判断i和j是否有边：父子或子父关系
            bool hasEdge = (tree[i].p == j) || (tree[j].p == i) || 
                           (std::find(tree[i].c.begin(), tree[i].c.end(), j) != tree[i].c.end());
            outFile << (hasEdge ? char('A' + j) : "@");
        }
        outFile << "\n";
    }

    outFile.close();
}

三、学习资源推荐 #

• C++基础与标准库：《C++ Primer》，重点掌握容器（vector）、文件IO（fstream）的使用
• 数据结构：《数据结构与算法分析——C++描述》，详细讲解树的顺序存储、遍历，以及图的邻接矩阵实现
• 二叉树专项：国内高校经典教材《数据结构》（严蔚敏版），对二叉树的顺序存储、层次遍历有清晰的理论讲解
• C++文件IO：参考C++官方文档中的fstream模块内容，了解文件读写的底层逻辑

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