使用层序遍历创建二叉树的C语言实现

本资源是一份C语言编写的代码，用于实现数据结构中的中序层序遍历构建二叉树。作者提供了一个名为"In_Level_CreatBiTree"的函数，它接受一个整数数组In和Level作为输入，以及一个整数n表示元素个数，目标是根据给定的层次顺序（由Level数组指定）构建一棵二叉树。层次顺序遍历也称为宽度优先搜索（BFS），在这种方法中，先处理同一层的所有节点，然后递归地处理下一层。 首先，定义了两个结构体：BiTree用于表示二叉树节点，包含整型数据data和指向左孩子和右孩子的指针lchild和rchild；QueueType则是一个队列结构，包含数据、队列头指针front、队列尾指针rear以及其他辅助信息。LinkQueue是一个链接队列类型，用于在"In_Level_CreatBiTree"函数中进行操作。 函数"InitQueue"初始化队列，"EnQueue"将元素添加到队列尾部，"DeQueue"取出并返回队首元素，"QueueEmpty"检查队列是否为空。主函数首先读取输入的节点层次位置和数值，然后调用"In_Level_CreatBiTree"函数构建二叉树，并通过预序遍历(PreOrderTraverse)和后序遍历(PostOrderTraverse)来展示树的结构。 "In_Level_CreatBiTree"函数的工作流程如下： 1. 定义变量r记录当前处理的层次，初始值为-1，low和high分别用于记录当前子树的边界，lr表示当前节点的左右孩子关系。 2. 初始化空树root和临时队列Q。 3. 遍历Level数组，对于每个层次，找到其起始节点s并将它添加到队列尾部，同时设置s.l为0，表示这是队列中的第一个元素。 4. 当队列非空时，执行循环： a. 弹出队首节点s，将其作为当前节点p。 b. 更新low和high，表示p节点所在子树的范围。 c. 遍历In数组，找到p节点的左孩子ch，如果ch存在于In数组中且在其父节点的预期位置，创建一个新的BiTree结构，将其数据赋值给ch，ch的左右孩子指向NULL，然后添加ch到队列中，更新lr（左孩子）。 d. 遍历In数组，找到p节点的右孩子ch，同理处理，但更新lr为右孩子。 5. 如果p节点没有完成子树构建，将其添加到root的对应子树中，否则返回根节点。 通过这个过程，In_Level_CreatBiTree函数能够根据层次顺序构建一棵完整的二叉树，后续的PreOrderTraverse和PostOrderTraverse函数则可以用来验证构建结果并按照先序和后序遍历的顺序输出节点信息。 这份代码为理解和实现中序层序遍历构建二叉树提供了一个实用的参考模板，适合学习者和初学者练习和理解数据结构与算法中的二叉树构建。