用数据结构知识写出以下代码，一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法

假设完全二叉树的数组存储方式为 a[1], a[2], ..., a[n]，则该算法可以使用递归或者栈来实现。

以下是使用递归实现先序遍历的代码：

void preorder(int root) {
    if (root <= n) {
        cout << a[root] << " "; //访问根节点
        preorder(root * 2); //遍历左子树
        preorder(root * 2 + 1); //遍历右子树
    }
}

以下是使用栈实现先序遍历的代码：

void preorder() {
    stack<int> s;
    s.push(1);
    while (!s.empty()) {
        int root = s.top();
        s.pop();
        if (root <= n) {
            cout << a[root] << " "; //访问根节点
            s.push(root * 2 + 1); //先将右子树入栈
            s.push(root * 2); //再将左子树入栈
        }
    }
}

以上两种实现方式都具有时间复杂度 O(n)，空间复杂度 O(logn)。

相关问题

数据结构用C语言或者C++已知深度为h的二叉树以一维数组BT［0．．2h-2］作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数。为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。

算法的基本思想是采用递归的方式来遍历二叉树并计算叶子节点的数量。对于给定的深度`h`的一维数组表示的二叉树，每个节点的数据会按照层次顺序存储。我们可以通过数组下标来确定左右孩子的位置，并判断当前节点是否是叶子节点。

下面是基于这个思路的C++实现：

int leafCount(int BT[], int h, int node = 0) {
    // 如果节点值为0，说明它是叶子节点，计数加1
    if (BT[node] == 0) {
        return 1;
    }

    // 如果左孩子存在且非空，递归处理左孩子
    if (node * 2 + 1 < 2 * h) {
        int leftLeaves = leafCount(BT, h, node * 2 + 1);
        // 同理，如果右孩子存在且非空，递归处理右孩子
        if (node * 2 + 2 < 2 * h) {
            int rightLeaves = leafCount(BT, h, node * 2 + 2);
            return leftLeaves + rightLeaves;  // 返回左右叶子节点之和
        } else {
            // 只有左孩子，返回左孩子叶子节点数量
            return leftLeaves;
        }
    } else {
        // 没有左孩子，只看右孩子
        return leafCount(BT, h, node * 2 + 2);
    }
}