C++实现一波二叉树遍历及节点操作实例

本文档主要介绍了如何使用C++语言解决一波二叉树的遍历问题，重点是层次遍历（按层打印节点）。层次遍历也称为广度优先搜索（BFS），其目标是从根节点开始，按照从上到下、从左到右的顺序依次访问二叉树的所有节点。这里涉及到的具体问题包括给定一个二叉树结构的输入数组，如何构建并打印出符合层次遍历规则的输出。 首先，作者定义了一个二叉树节点结构体`BTree`，包含整型数据`data`以及指向左右子节点的指针。层次遍历的关键在于利用队列（Queue）来辅助操作。在C++中，作者使用了`std::queue`容器，初始化一个固定大小的队列用于存储待访问的节点。 在`printLine`函数中，首先将根节点放入队列尾部，然后进入一个循环，直到队列为空。每次循环中，会从队列头部取出一个节点，打印其数据，并根据节点的左右子节点判断是否需要将它们加入队列。如果左子节点不为空且队列未满，将其放入队列；同样，如果右子节点不为空且队列未满，也将其加入。这样就保证了按照层次顺序依次访问节点。 题目一的具体实现代码如下： ```cpp #include <stdio.h> #include <stdlib.h> // ... (二叉树节点定义和 CreatTree 函数) int printLine(BTree* root) { BTree* queue[size]; // 初始化队列 int front = rear = 0; // 前后指针 rear = (rear + 1) % size; queue[rear] = root; // 队列尾部放根节点 while (front != rear) { // 取出队首节点 front = (front + 1) % size; BTree* p = queue[front]; printf("%3d", p->data); // 打印节点数据 // 将左子节点入队（如果未满） if (p->left && ((rear + 1) % size != front)) { rear = (rear + 1) % size; queue[rear] = p->left; } // 将右子节点入队（如果未满） if (p->right && ((rear + 1) % size != front)) { rear = (rear + 1) % size; queue[rear] = p->right; } } } int main() { int array[] = {8, 6, 10, 5, 7, 9, 11}; BTree* root = CreatTree(array, sizeof(array) / sizeof(array[0])); // 构建二叉树 printLine(root); // 打印层次遍历结果 printf("\n"); return 0; } ``` 总结，该文档详细地介绍了如何使用C++编程实现二叉树的层次遍历，通过队列的使用有效地解决了按层次顺序打印节点的问题。这对于理解二叉树数据结构和算法的实现具有实际参考价值，特别是对于那些希望学习或巩固C++编程基础、二叉树遍历技巧的读者来说非常实用。