C++中使用数组查找二叉树中叶子节点个数的问题

Question

我正在编写 C++ 代码，使用数组输入找出二叉树中叶节点的数量我的代码是：

int leaf(int data[],int size) {
    int result = 0;
    for (int i = 0; i <= size; i++) {
        if (data[i] == -1)
            i++;
        if (((data[(2*i)+1] == -1) && (data[(2 * i) +2] == -1)) || ((data[(2 * i) +1] == NULL) && (data[(2 * i) +2] == NULL)))
            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;
}

数组中，元素-1为空节点。树是这样的：

离开节点的总数应该是3也就是(12,10,5)，但是我的代码结果是2。我能知道我的代码有什么问题以及如何修复它吗？非常感谢！

Answer 1

一些问题：

当 for 循环变量等于 size 时，您将越界 index-access 到 data。在这种情况下，循环应该退出——size 是无效索引，因此使用 i < size 作为循环条件。
您的 for 循环将循环变量递增 i++；当您在数据中找到 -1 值时，没有理由在此基础上增加 i。如果 i 这样做会越界怎么办？如果下一个数据元素也有一个 -1 值怎么办？无论哪种情况，您的代码都会出错。而是使用 data[i] != -1 作为循环体中其余逻辑的条件。
在实际进行索引访问之前，您应该检查用于 data 的索引是否超出范围。将越界数据条目与 NULL 进行比较是不安全的：越界访问的值是未定义的，永远不必将 int 与 NULL 进行比较。 NULL 用于 pointers.
的上下文中
你也应该预见到左边child为-1，右边child出界的情况

以下是这些问题的修复方法：

int leaf(int data[], int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        if ( data[i] != -1 &&
                 (2*i+1 >= size || data[2*i+1] == -1) &&
                 (2*i+2 >= size || data[2*i+2] == -1) )
            result++;
    }
    return result;
}

此逻辑假定数组将像完整树一样组织。像这样的一些数组编码不会有两个 -1 条目来填充另一个 -1 条目的“children”，而是忽略它们，使公式 2*i+1 和 2*i+2 无效.

以这棵树为例：

如果编码是完整树编码，那么它将是{1, -1, 2, -1, -1, -1, 3}。如果它是更紧凑的编码，其中 -1 条目将没有 children 条目，那么它将是 {1, -1, 2, -1, 3}.

您的示例没有显示您正在处理的是两种编码中的哪一种，因为对于您的示例树来说它是同一个数组。如果是后面的编码，则完全需要不同的算法。

C++中使用数组查找二叉树中叶子节点个数的问题

Problem on finding the number of leave node in a binary tree in C++ using array

c++

arrays

binary-tree