二叉树的创建 遍历 交换子树

编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法。 2 编写将一棵二叉树的所有左右子树进行交换的算法。 提示：验证是否交换可以调用二叉树的遍历算法，比较输出结点序列。 3 编写一个主函数，将上面函数连在一起，构成一个完整的程序。 4 调试并运行实验源程序。 二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。在本实验中，我们主要关注二叉树的创建、遍历以及子树交换的操作。 二叉树的创建是通过输入节点数据来完成的。在给定的代码中，`create` 函数用于创建二叉树。它接收一个指向二叉树节点指针的指针作为参数，然后根据用户输入的字符（非零表示创建节点，零表示空节点）递归地构建二叉树的结构。输入的字符流决定了二叉树的形态。 接着，提供了四种遍历二叉树的方法： 1. **先序遍历**（`xianxu`）：先访问根节点，再遍历左子树，最后遍历右子树。在给定代码中，先序遍历的顺序为：打印当前节点 -> 先序遍历左子树 -> 先序遍历右子树。 2. **中序遍历**（`zhong`）：先遍历左子树，再访问根节点，最后遍历右子树。中序遍历的顺序为：中序遍历左子树 -> 打印当前节点 -> 中序遍历右子树。 3. **后序遍历**（`hou`）：先遍历左子树，然后遍历右子树，最后访问根节点。后序遍历的顺序为：后序遍历左子树 -> 后序遍历右子树 -> 打印当前节点。 4. **层次遍历**（`level`）：按照二叉树的层级顺序访问节点，同一层的节点按照从左到右的顺序访问。层次遍历通常使用队列辅助实现，从根节点开始，依次将子节点入队，然后出队访问。 为了验证左右子树交换操作，定义了`swap`函数。该函数交换二叉树节点的左右子树，同时递归地对左右子树执行相同的操作。交换完成后，可以通过遍历二叉树并打印节点序列，对比交换前后的节点顺序，从而验证交换是否成功。 在主函数`main`中，首先提示用户按先序输入二叉树的节点，然后调用相应的函数进行遍历和子树交换，并打印出遍历结果，供用户查看和验证。 实验的目的在于让学习者掌握二叉树的逻辑结构和不同遍历方式，以及如何使用指针类实现这些操作。通过这个实验，学生可以理解二叉树的基本操作，并加深对二叉链表存储结构的理解。同时，通过编写和调试代码，提高编程实践能力。