C++使用数组结构实现平衡二叉搜索树及向量存储异常问题

Alright, let's dig into why you're seeing negative values when printing your vector-based binary tree, and how to fix it. This is a common pitfall with the 2i/2i+1 indexing approach—let's break down the most likely issues and solutions:

1. You're Mixing Up Index Starting Positions #

The classic 2i (left child) / 2i+1 (right child) formula almost always assumes the root node starts at index 1, not 0 (which is vector's default starting point). Here's what happens if you ignore that:

• If you place the root at index 0, calculating left child as 2*0 = 0 will overwrite the root itself.
• For larger parent indices, 2i might jump way beyond your vector's current size. Accessing vec[2i] directly here triggers undefined behavior—you'll end up reading uninitialized memory, which often shows up as random negative integers.

Fix: Choose a Consistent Indexing Scheme #

Either:

• Root at index 1: Reserve index 0 as a dummy placeholder (so the math works). When inserting children, always check if the target index is beyond the vector's size, and resize first to fill in gaps with initialized nodes.
• Root at index 0: Adjust the formula to left child = 2*i + 1, right child = 2*i + 2 to avoid overlapping indices.

2. Your Node Struct Isn't Properly Initialized #

If your TreeNode struct doesn't have an explicit constructor, any new elements added to the vector (via resize or implicit expansion) will leave int members (ID, Age) uninitialized. These uninitialized values are garbage—they can be negative, huge positive numbers, or anything else.

Fix: Add a Constructor to Initialize All Members #

Make sure every node starts with valid, predictable values:

struct TreeNode {
    int ID;
    int Age;
    std::string name;

    // Default constructor with safe initial values
    TreeNode(int id = 0, int age = 0, const std::string& n = "") 
        : ID(id), Age(age), name(n) {}
};

3. Insert Logic Doesn't Handle Vector Resizing Correctly #

You can't just assign to vec[target_index] if that index is larger than vec.size() - 1. Doing so will either crash or leave you with uninitialized data. You need to explicitly resize the vector to cover the target index first.

Example: Safe Insertion with Root at Index 1 #

#include <vector>
#include <string>
#include <iostream>

struct TreeNode {
    int ID;
    int Age;
    std::string name;

    TreeNode(int id = 0, int age = 0, const std::string& n = "") 
        : ID(id), Age(age), name(n) {}
};

void insertLeftChild(std::vector<TreeNode>& tree, int parentIndex, TreeNode child) {
    int targetIdx = 2 * parentIndex;
    if (targetIdx >= tree.size()) {
        // Resize to ensure we reach the target index, filling gaps with default nodes
        tree.resize(targetIdx + 1);
    }
    tree[targetIdx] = child;
}

void printTree(const std::vector<TreeNode>& tree) {
    for (size_t i = 1; i < tree.size(); ++i) { // Skip dummy index 0
        if (tree[i].ID != 0) { // Only print initialized nodes
            std::cout << "Index " << i 
                      << ": ID=" << tree[i].ID 
                      << ", Age=" << tree[i].Age 
                      << ", Name=" << tree[i].name << "\n";
        }
    }
}

int main() {
    std::vector<TreeNode> tree;
    tree.emplace_back(); // Dummy node at index 0
    tree.emplace_back(1, 30, "Alice"); // Root at index 1

    insertLeftChild(tree, 1, TreeNode(2, 25, "Bob"));
    // Insert right child manually using 2i+1
    int rightIdx = 2 * 1 + 1;
    if (rightIdx >= tree.size()) tree.resize(rightIdx + 1);
    tree[rightIdx] = TreeNode(3, 35, "Charlie");

    printTree(tree);
    return 0;
}

Final Checks #

• Always verify that the target index exists in the vector before assigning to it.
• When printing, skip any dummy or uninitialized nodes (check for ID != 0 or another sentinel value you choose).
• Avoid using vector::operator[] for indices beyond the current size—use resize or emplace_back to ensure valid, initialized elements.

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