C++使用数组存储二叉树统计叶子节点数量结果错误如何修复

• 数组越界访问：原代码for (int i = 0; i <= size; i++)边界错误，长度为size的数组合法索引范围是0~size-1，i<=size会访问到数组外的未知内存，导致判断逻辑异常。
• 空节点处理逻辑错误：遇到data[i] == -1的空节点时仅执行i++，没有跳过后续叶子判断逻辑，会导致逻辑错乱，且空节点本身不需要参与叶子统计。
• 空节点判断规则错误：代码中出现和NULL的比较不符合你约定的-1代表空节点的规则，NULL在C++中默认为0，会导致判断逻辑完全偏离预期。
• 未判断子节点索引越界：如果子节点索引超过数组长度，默认属于空节点，原代码直接访问data[2*i+1]会出现越界读的问题，读取到的脏值会导致叶子判断错误。

#include <iostream>
using namespace std;

int leaf(int data[],int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        // 跳过空节点
        if (data[i] == -1)
            continue;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 判断左右孩子是否都为空
        bool left_empty = (left >= size) || (data[left] == -1);
        bool right_empty = (right >= size) || (data[right] == -1);
        if (left_empty && right_empty) {
            result++;
        }
    }
    return result;
}

int main(){
    int data[]= { 1,9, 6, 8 ,12, 2,-1 ,10, -1 ,-1 ,-1, 5 };
    int size = 12;
    cout << "count of leave node: " << leaf(data, size)<< endl;
    return 0;
}

修复后代码运行输出为3，符合预期结果。

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