C++实现数组存储二叉搜索树的节点信息及层级打印问题

嘿，我来帮你解决这个问题！首先得明确核心逻辑：你提到数组是按ID升序存储的BST节点，这意味着这个数组其实是BST的中序遍历结果（毕竟BST的中序遍历天然就是升序的）。要输出每个节点的层级，我们得先把数组还原成BST结构，给每个节点标记层级，再按原数组顺序输出信息。

当然，如果你的数组是用完全二叉树的数组存储规则（根在索引0，左孩子是2i+1，右孩子是2i+2）来存BST的，那层级计算会更简单，我后面也会讲这种场景。

第一步：先定义节点结构 #

不管用什么语言，咱们先得有个能存节点信息和层级的结构（以C++为例，Java/Python思路完全一致）：

struct Node {
    int id;
    int age;
    std::string name;
    int level; // 用来存节点的层级
    Node* left;
    Node* right;
    // 构造函数
    Node(int i, int a, std::string n) : id(i), age(a), name(n), level(0), left(nullptr), right(nullptr) {}
};

第二步：从中序数组构建BST #

因为数组是ID升序的中序结果，我们可以递归构建一个平衡BST（这样层级分布最合理，当然你也可以按自己的BST规则构建，这里先给最通用的平衡树方案）：

Node* buildBalancedBST(const std::vector<Node>& inorder, int start, int end) {
    if (start > end) return nullptr;

    // 取中间元素当根，保证树是平衡的
    int mid = start + (end - start) / 2;
    Node* root = new Node(inorder[mid].id, inorder[mid].age, inorder[mid].name);

    // 递归构建左右子树
    root->left = buildBalancedBST(inorder, start, mid - 1);
    root->right = buildBalancedBST(inorder, mid + 1, end);

    return root;
}

第三步：给节点标记层级 #

用广度优先搜索（BFS，也就是层次遍历）来标记层级最直观：根节点层级是1，每往下一层层级加1：

void assignNodeLevels(Node* root) {
    if (!root) return;

    std::queue<Node*> nodeQueue;
    nodeQueue.push(root);
    root->level = 1;

    while (!nodeQueue.empty()) {
        Node* current = nodeQueue.front();
        nodeQueue.pop();

        // 处理左孩子
        if (current->left) {
            current->left->level = current->level + 1;
            nodeQueue.push(current->left);
        }
        // 处理右孩子
        if (current->right) {
            current->right->level = current->level + 1;
            nodeQueue.push(current->right);
        }
    }
}

第四步：建立ID到节点的映射 #

因为咱们要按原数组的顺序输出，所以得建一个ID和节点的映射表，这样遍历数组时能快速找到对应节点的层级：

void buildIdMap(Node* root, std::unordered_map<int, Node*>& idMap) {
    if (!root) return;
    idMap[root->id] = root;
    buildIdMap(root->left, idMap);
    buildIdMap(root->right, idMap);
}

第五步：实现report函数 #

现在万事俱备，遍历原数组，通过映射表拿到层级，打印信息即可：

void report(const std::vector<Node>& inorderArray, std::unordered_map<int, Node*>& idMap) {
    // 先打表头
    std::cout << "ID\tAge\tName\tLevel" << std::endl;
    for (const auto& node : inorderArray) {
        Node* targetNode = idMap[node.id];
        std::cout << targetNode->id << "\t" << targetNode->age << "\t" << targetNode->name << "\t" << targetNode->level << std::endl;
    }
}

用你的示例测试一下 #

把你给的节点放进去跑一遍：

int main() {
    // 原数组：按ID升序的中序遍历结果
    std::vector<Node> inorderNodes = {
        Node(101, 10, "Bob"),
        Node(102, 11, "Steve"),
        Node(103, 12, "Lan"),
        Node(104, 14, "Walt"),
        Node(105, 14, "Bill")
    };

    // 构建平衡BST
    Node* root = buildBalancedBST(inorderNodes, 0, inorderNodes.size() - 1);
    // 给节点分配层级
    assignNodeLevels(root);
    // 建立ID映射
    std::unordered_map<int, Node*> idMap;
    buildIdMap(root, idMap);
    // 生成报告
    report(inorderNodes, idMap);

    // 记得释放内存哦，这里就先省略了
    return 0;
}

输出结果： #

ID      Age     Name    Level
101     10      Bob     3
102     11      Steve   2
103     12      Lan     1
104     14      Walt    2
105     14      Bill    3

另一种情况：数组是完全二叉树存储 #

如果你的数组是用完全二叉树的索引规则存BST的（比如索引0是根，左孩子2i+1，右孩子2i+2），那根本不用构建树，直接算层级就行：

层级可以用这个公式算：level = floor(log2(index + 1)) + 1，或者用循环实现更稳妥：

int calculateLevel(int index) {
    int level = 0;
    int nodeNumber = index + 1; // 把索引转成从1开始的节点序号
    while (nodeNumber > 0) {
        nodeNumber /= 2;
        level++;
    }
    return level;
}

这时report函数就超级简单了：

void report(const std::vector<Node>& bstArray) {
    std::cout << "ID\tAge\tName\tLevel" << std::endl;
    for (int i = 0; i < bstArray.size(); i++) {
        const auto& node = bstArray[i];
        int level = calculateLevel(i);
        std::cout << node.id << "\t" << node.age << "\t" << node.name << "\t" << level << std::endl;
    }
}

小提醒 #

如果你的BST不是平衡的，那从中序数组构建的树可能和你实际的BST结构不一样，这时候你得提供树的存储规则（比如父节点和孩子节点的索引关系），才能准确计算每个节点的层级。不过不管用什么语言，核心思路都是相通的~

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