位置：文档库 > C/C++ > 在C语言中，打印给定层级的叶节点

在C语言中，打印给定层级的叶节点

TitanQuill 上传于 2020-08-13 16:41

《在C语言中，打印给定层级的叶节点》

在计算机科学中，树形结构是一种重要的非线性数据结构，广泛应用于文件系统、数据库索引、编译器的语法分析等领域。二叉树作为树形结构的典型代表，其节点分为内部节点（非叶节点）和叶节点（无子节点的节点）。在实际编程中，有时需要针对特定层级的叶节点进行操作，例如统计某层叶节点的数量、修改其值或打印其内容。本文将详细探讨如何在C语言中实现“打印给定层级的叶节点”功能，涵盖二叉树的构建、层级遍历以及叶节点判断等核心步骤。

一、二叉树的基础表示

在C语言中，二叉树通常通过结构体和指针实现。每个节点包含数据域、左子节点指针和右子节点指针。以下是一个简单的二叉树节点定义：

typedef struct TreeNode {
    int data;                   // 节点数据
    struct TreeNode *left;      // 左子节点指针
    struct TreeNode *right;     // 右子节点指针
} TreeNode;

通过这种结构，可以递归地构建二叉树。例如，创建一个简单的二叉树：

TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建示例二叉树
TreeNode* buildSampleTree() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    return root;
}

上述代码构建了一个三层二叉树，其结构如下：

二、层级遍历与叶节点判断

要打印指定层级的叶节点，需结合层级遍历（BFS）和叶节点判断。层级遍历通过队列实现，逐层访问节点；叶节点判断则检查节点的左右子节点是否均为空。

1. 队列辅助结构

队列用于存储待访问的节点及其层级信息。定义队列节点和队列结构如下：

typedef struct QueueNode {
    TreeNode* treeNode;          // 二叉树节点
    int level;                   // 节点所在层级
    struct QueueNode *next;      // 下一队列节点
} QueueNode;

typedef struct Queue {
    QueueNode *front;            // 队首指针
    QueueNode *rear;             // 队尾指针
} Queue;

初始化队列、入队和出队操作：

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, TreeNode* treeNode, int level) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->level = level;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

QueueNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QueueNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

2. 层级遍历实现

通过队列实现层级遍历，记录每个节点的层级，并在遇到叶节点时检查其层级是否匹配目标层级：

void printLeafNodesAtLevel(TreeNode* root, int targetLevel) {
    if (root == NULL) return;
    
    Queue* q = createQueue();
    enqueue(q, root, 1);  // 根节点层级为1
    
    while (q->front != NULL) {
        QueueNode* current = dequeue(q);
        TreeNode* node = current->treeNode;
        int currentLevel = current->level;
        
        // 判断是否为叶节点且层级匹配
        if (node->left == NULL && node->right == NULL) {
            if (currentLevel == targetLevel) {
                printf("%d ", node->data);
            }
        }
        
        // 将子节点入队，层级+1
        if (node->left != NULL) {
            enqueue(q, node->left, currentLevel + 1);
        }
        if (node->right != NULL) {
            enqueue(q, node->right, currentLevel + 1);
        }
    }
    free(q);  // 释放队列内存
}

三、完整代码示例

将上述部分整合为一个完整程序，演示如何打印指定层级的叶节点：

#include 
#include 

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct QueueNode {
    TreeNode* treeNode;
    int level;
    struct QueueNode *next;
} QueueNode;

typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, TreeNode* treeNode, int level) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->level = level;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

QueueNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QueueNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

void printLeafNodesAtLevel(TreeNode* root, int targetLevel) {
    if (root == NULL) return;
    
    Queue* q = createQueue();
    enqueue(q, root, 1);
    
    while (q->front != NULL) {
        QueueNode* current = dequeue(q);
        TreeNode* node = current->treeNode;
        int currentLevel = current->level;
        
        if (node->left == NULL && node->right == NULL) {
            if (currentLevel == targetLevel) {
                printf("%d ", node->data);
            }
        }
        
        if (node->left != NULL) {
            enqueue(q, node->left, currentLevel + 1);
        }
        if (node->right != NULL) {
            enqueue(q, node->right, currentLevel + 1);
        }
    }
    free(q);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    int targetLevel;
    printf("输入目标层级: ");
    scanf("%d", &targetLevel);
    
    printf("层级 %d 的叶节点: ", targetLevel);
    printLeafNodesAtLevel(root, targetLevel);
    printf("\n");
    
    return 0;
}

四、代码测试与分析

运行上述程序，输入目标层级后，程序会输出该层级的所有叶节点。例如：

输入 1，输出无（根节点非叶节点）。
输入 2，输出无（第二层节点均有子节点）。
输入 3，输出 4 5 6 7（第三层均为叶节点）。

时间复杂度分析：层级遍历需访问所有节点，时间复杂度为 O(n)，其中 n 为节点总数。空间复杂度取决于队列的最大长度，最坏情况下为 O(n)（完全二叉树最后一层节点数约为 n/2）。

五、扩展与优化

1. **递归实现**：可通过递归遍历树，记录当前层级，并在遇到叶节点时判断层级。但递归深度过大可能导致栈溢出。

void printLeafAtLevelRecursive(TreeNode* root, int currentLevel, int targetLevel) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL && currentLevel == targetLevel) {
        printf("%d ", root->data);
    }
    printLeafAtLevelRecursive(root->left, currentLevel + 1, targetLevel);
    printLeafAtLevelRecursive(root->right, currentLevel + 1, targetLevel);
}

2. **动态内存管理**：在真实项目中，需添加内存释放函数，避免内存泄漏。

void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

六、总结

本文通过队列实现了二叉树的层级遍历，结合叶节点判断条件，高效地打印了指定层级的叶节点。关键步骤包括：

使用结构体定义二叉树节点和队列节点。
通过队列实现广度优先搜索（BFS）。
在出队时检查节点是否为叶节点且层级匹配。

该方法适用于任意二叉树，且时间复杂度为线性。读者可进一步扩展至多叉树或添加其他条件（如值范围过滤）。

关键词：C语言、二叉树、叶节点、层级遍历、队列、BFS

简介：本文详细介绍了在C语言中如何打印二叉树指定层级的叶节点，涵盖二叉树结构定义、队列辅助的层级遍历算法、叶节点判断条件及完整代码实现，并分析了时间复杂度与扩展方向。

立即下载

C/C++相关