C++实现二叉树层次遍历示例及广义表创建

在C++编程中，实现二叉树的层次遍历是一种常见的数据结构操作，有助于我们理解树形数据结构的节点访问顺序。这篇示例代码展示了如何使用队列数据结构来执行层次遍历，并结合广义表表示法构建二叉树。层次遍历，也称为广度优先搜索（Breadth-First Search, BFS），按照从上到下、从左到右的顺序逐层遍历树中的节点。 首先，我们定义了一个名为`TreeNode`的结构体，它包含整数值`val`、指向左子节点的指针`left`和指向右子节点的指针`right`。结构体初始化器`TreeNode(int x)`用于创建一个新节点，给定一个整数值作为节点值。 接下来是`levelOrder`函数，这是核心部分。它接收一个二叉树的根节点`root`作为输入，返回一个二维向量`res`，其中每个内部向量表示一层的节点值。函数首先检查根节点是否为空，然后使用`queue<TreeNode*>`存储待访问的节点。初始化时，队列只包含根节点。在循环中，每次从队列中取出一个节点，访问其值，然后将其左右子节点（如果存在）依次放入队列。如此反复，直至队列为空，所有节点都被访问过并存入结果数组`res`。 `createTree`函数用于根据输入的整数数组`nums`动态构建二叉树。数组的索引对应树的层次结构，如果索引超出数组范围或数值为-1，则表示叶子节点或结束。函数递归地为每个节点创建左子树和右子树。 在`main`函数中，我们创建一个二叉树实例，通过调用`createTree`函数传入一个`nums`数组，这个数组的元素代表树的节点值和它们的子节点关系。创建完成后，调用`levelOrder`函数进行层次遍历，最终得到的二维向量`res`包含了树的层次遍历结果。 总结起来，这段代码展示了如何在C++中实现二叉树的层次遍历，包括定义二叉树节点、创建树结构以及执行层次遍历算法。层次遍历是处理图和树问题的重要技巧，对于理解节点之间的层次关系和算法优化具有重要意义。通过这个示例，程序员可以学习如何运用队列数据结构处理二叉树问题，并进一步探索其他高级数据结构和算法。