二进制数组构建与遍历二叉树

二进制数组构建与遍历二叉树

在计算机科学中，二叉树是一种重要的数据结构，其应用广泛，从数据库索引到算法实现都有它的身影。本文将介绍如何使用一个整数数组来构建一棵二叉树，并通过队列实现二叉树的层次遍历。

构建二叉树: 使用数组构建二叉树时，通常每个元素代表一个节点，而该元素的索引则用于确定其在树中的位置。例如，对于索引i的节点，其左子节点位于2*i+1的位置，右子节点位于2*i+2的位置。为了构建二叉树，我们使用两个队列，一个用于存储当前层的节点（父节点），另一个用于存储下一层的节点（子节点）。随着构建过程的推进，这两个队列会不断交换角色。

二叉树的数据结构定义:

struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int x) : value(x), left(nullptr), right(nullptr) {} };

构建二叉树的函数:

TreeNode* createTree(const std::vector& values) { if (values.empty()) return nullptr; std::queue parents, children; TreeNode* root = new TreeNode(values[0]); parents.push(root); for (size_t i = 1; i left) parent->left = child; else { parent->right = child; parents.push(parent); } children.push(child); if (parents.empty()) { parents.swap(children); } } return root; }

遍历并打印二叉树: 为了打印二叉树，我们同样使用两个队列。首先将根节点放入一个队列，然后逐层处理每个节点，同时将其子节点加入另一个队列。当当前层的所有节点都被处理后，交换两个队列的角色，继续处理下一层，直到所有节点都被打印。

void printBinaryTree(TreeNode* root) { if (!root) return; std::queue currentLevel, nextLevel; currentLevel.push(root); while (!currentLevel.empty()) { TreeNode* node = currentLevel.front(); currentLevel.pop(); std::cout <value <<' '; if (node->left) nextLevel.push(node->left); if (node->right) nextLevel.push(node->right); if (currentLevel.empty()) { std::cout <

测试代码:

int main() { std::vector data = {1, 2, 3, 4, 5, 6, 7}; TreeNode* tree = createTree(data); printBinaryTree(tree); return 0; }

输出结果:

1 
2 3 
4 5 6 7