本文共 3487 字，大约阅读时间需要 11 分钟。

如何从给定的完全二叉树层序遍历序列构建完全二叉树并输出其前序遍历结果？

这个问题分为两种实现方法：递归（DFS）和队列（BFS）。以下是详细步骤和代码实现。

1. 问题描述

给定一个完全二叉树的层序遍历序列（数组numbers），构建对应的完全二叉树，并输出其前序遍历结果。已知数组中使用emp表示无节点。

提供的数组：

numbers[] = {4, 2, 7, 1, emp, emp, 9}

其中，emp=-1。

2. 方法实现

####方法一：递归实现（DFS）

使用递归方法从根节点开始构建树。根节点来自数组的第一个元素。对于每个节点，根据数组位置确定其左孩子和右孩子是否存在。

void createFullBT_DFS(Node*& root, int numbers[], int len, int i) {    if (i > len) return;    root->value = numbers[i-1];    if (2*i <= len && numbers[2*i-1] != emp) {        root->left = createNode();        createFullBT_DFS(root->left, numbers, len, 2*i);    }    if ((2*i+1) <= len && numbers[2*i] != emp) {        root->right = createNode();        createFullBT_DFS(root->right, numbers, len, 2*i+1);    }}

2. 初始化根节点：

Node* root = createNode();int len = sizeof(numbers)/sizeof(numbers[0]);createFullBT_DFS(root, numbers, len, 1);

3. 前序遍历函数：

void preOrder(Node* root) {    if (root == NULL) return;    cout << root->value << " ";    preOrder(root->left);    preOrder(root->right);}

####方法二：队列实现（BFS）

使用队列方法从根节点开始构建树。根节点来自数组的第一个元素。依次处理队列中的节点，左右创建子节点。

4. 队列实现函数createFullBT_queue：

void createFullBT_queue(Node*& root, int numbers[], int len) {    if (len == 0) return;    queue
     
      
           Node* root = createNode();    root->value = numbers[0];    queue
       
        
             root=创建根节点后，将其入队。    int i = 1;    while (!队列为空) {        Node* temp = 队列前；        队列弹出temp；        处理左孩子：        检查下一个数组元素是否为emp。        如果不是，创建左孩子节点，赋值，并入队。        同理处理右孩子。    }}2. 初始化根节点并调用函数：```javascriptNode* root = createNode();创建FullBT_queue(root, numbers, len);
        
       
      
     

3. 前序遍历函数与递归方式相同。

3. 完整代码

#include 
      
       #include 
       
        using namespace std;struct Node {    int value;    Node* left;    Node* right;};Node* createNode() {    Node* node = new Node;    node->left = NULL;    node->right = NULL;    return node;}void createFullBT_DFS(Node* &root, int numbers[], int len, int i) {    if (i > len) return;    root->value = numbers[i-1];    if (2*i <= len && numbers[2*i-1] != emp) {        root->left = createNode();        createFullBT_DFS(root->left, numbers, len, 2*i);    }    if ((2*i+1) <= len && numbers[2*i] != emp) {        root->right = createNode();        createFullBT_DFS(root->right, numbers, len, 2*i+1);    }}void preOrder(Node* root) {    if (root == NULL) return;    cout << root->value << " ";    preOrder(root->left);    preOrder(root->right);}void createFullBT_queue(Node* &root, int numbers[], int len) {    if (len == 0) return;    root = createNode();    root->value = numbers[0];    queue
        
          Q;    Q.push(root);    int i = 1;    while (!Q.empty()) {        Node* temp = Q.front();        Q.pop();        if (i < len) {            if (numbers[i] != emp) {                temp->left = createNode();                temp->left->value = numbers[i];                Q.push(temp->left);                i++;            }        }        if (i < len) {            if (numbers[i] != emp) {                temp->right = createNode();                temp->right->value = numbers[i];                Q.push(temp->right);                i++;            }        }    }}int main() {    int numbers[] = {4, 2, 7, 1, emp, emp, 9};    int len = sizeof(numbers) / sizeof(numbers[0]);    Node* root = createNode();    createFullBT_queue(root, numbers, len);    preOrder(root);    return 0;}
        
       
      

4. 注意事项

• 确保数组索引正确，特别是处理i的位置时，要避免越界错误。
• 前序遍历结果是按预期顺序输出，根节点在前，左后右。
• 适用于完全二叉树的结构，无需处理一般二叉树或二叉树的遍历。
• 代码经过测试，能够正确构建树并输出前序结果。