递归实现BST层序遍历填充数组及作用域解析符错误排查

语法错误分析 #

• 作用域与成员访问错误
  代码里BinaryNodeTree<ItemType> :: rootPtr;是错误写法：

  • 若rootPtr是BinarySearchTree继承自BinaryNodeTree的保护成员，直接写rootPtr即可，不需要加BinaryNodeTree<ItemType>::前缀；
  • 这行代码实际是声明了一个新的局部变量，并非访问类的成员根指针。
    同时fillArray(rootPtr)调用错误：当前fillArray只有接收数组的重载，没有接收节点指针的版本，应该调用fillArrayHelper。

• 函数调用语法错误

  • getLeftChildPtr是成员函数，调用时必须加括号，比如left->getLeftChildPtr()，不能写成left->getLeftChildPtr；
  • fillArrayHelper(left->getLeftChildPtr->getItem());参数完全不匹配，fillArrayHelper需要节点指针、数组、位置三个参数，这里传入的是节点值，类型完全不对。

• 逻辑错误（影响功能实现）
  当前代码逻辑完全不符合层序遍历（广度优先）的规则，层序遍历需要按层级依次访问节点，而非只处理左子节点的左子节点；递归实现层序通常需要结合队列或层级参数来控制访问顺序。

修正后的代码示例 #

假设BinarySearchTree继承自BinaryNodeTree，且rootPtr是父类的保护成员，以下是修正语法并实现递归层序遍历的代码：

队列辅助的递归实现（直观易读） #

template<class ItemType>
int BinarySearchTree<ItemType>::fillArray(ItemType arr[]) {
    // 直接使用类的根成员指针
    return fillArrayHelper(rootPtr, arr, 0);
}

template<class ItemType>
int BinarySearchTree<ItemType>::fillArrayHelper(BinaryNode<ItemType>* subtreePtr, 
                                                ItemType arr[], int pos) {
    if (subtreePtr == nullptr) {
        return pos; // 返回当前填充到的位置，方便后续节点使用
    }

    // 层序遍历用队列暂存当前层节点
    queue<BinaryNode<ItemType>*> q;
    q.push(subtreePtr);

    while (!q.empty()) {
        BinaryNode<ItemType>* current = q.front();
        q.pop();

        // 填充当前节点值到数组
        arr[pos++] = current->getItem();

        // 左子节点入队
        if (current->getLeftChildPtr() != nullptr) {
            q.push(current->getLeftChildPtr());
        }
        // 右子节点入队
        if (current->getRightChildPtr() != nullptr) {
            q.push(current->getRightChildPtr());
        }
    }

    return pos; // 返回填充的总元素个数
}

纯递归实现（无队列） #

template<class ItemType>
int BinarySearchTree<ItemType>::fillArray(ItemType arr[]) {
    int pos = 0;
    // 从第0层开始遍历
    fillArrayRecursive(rootPtr, arr, pos, 0);
    return pos;
}

template<class ItemType>
void BinarySearchTree<ItemType>::fillArrayRecursive(BinaryNode<ItemType>* subtreePtr, 
                                                   ItemType arr[], int& pos, int level) {
    if (subtreePtr == nullptr) {
        return;
    }

    // 遍历到当前层级时填充节点值
    if (level == 0) {
        arr[pos++] = subtreePtr->getItem();
    } else {
        // 递归处理左子树的下一层
        fillArrayRecursive(subtreePtr->getLeftChildPtr(), arr, pos, level - 1);
        // 递归处理右子树的下一层
        fillArrayRecursive(subtreePtr->getRightChildPtr(), arr, pos, level - 1);
    }

    // 处理下一层级，直到没有新节点
    if (level == 0) {
        int nextLevel = 1;
        while (true) {
            int prevPos = pos;
            fillArrayRecursive(rootPtr, arr, pos, nextLevel);
            if (prevPos == pos) {
                break; // 无新节点填充，遍历完成
            }
            nextLevel++;
        }
    }
}

说明 #

• 队列辅助的方案更符合层序遍历的本质，逻辑直观，容易维护；
• 纯递归方案通过层级参数控制访问顺序，逻辑稍复杂，但满足纯递归的需求；
• 需确保BinaryNode类的getLeftChildPtr()、getRightChildPtr()、getItem()成员函数已正确实现。

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