二叉树的先序中序后序层次遍历，高度

从键盘输入二叉树的各结点值，按先序递归方式创建二叉树 2 ）分别实现先序、中序、后序递归遍历二叉树  3 ）输出二叉树的高度  4 ）输出二叉树的按层次遍历序列  5 ）输出二叉树的先序非递归遍历下的结点访问次序 6 ）以菜单方式运行 二叉树是一种特殊的树结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。本实验涉及了二叉树的创建、遍历以及计算高度等操作，这些都是理解和应用二叉树基本特性的核心内容。 二叉树的创建是通过先序递归方式进行的。在给定的代码中，`CreateBiTNode`函数用于创建二叉树。用户从键盘输入字符，当输入字符为'@'时，表示当前节点为空，返回NULL。否则，创建一个新的节点，其数据字段设置为输入的字符，并递归地创建左子树和右子树。这样，通过逐层构建，可以构建出用户输入的二叉树结构。 接着，实验要求实现二叉树的先序、中序、后序递归遍历。这三种遍历方法是二叉树遍历的基础： 1. **先序遍历**（PreOrder Traversal）：按照“根-左-右”的顺序访问每个节点。在给定的代码中，`PreOrderTraverse`函数实现了这个过程。首先访问根节点，然后递归遍历左子树，最后遍历右子树。 2. **中序遍历**（InOrder Traversal）：按照“左-根-右”的顺序访问每个节点。`InOrderTraverse`函数完成了这一操作。首先遍历左子树，然后访问根节点，最后遍历右子树。 3. **后序遍历**（PostOrder Traversal）：按照“左-右-根”的顺序访问每个节点。`PostOrderTraverse`函数实现了后序遍历。先遍历左子树，再遍历右子树，最后访问根节点。 此外，实验还要求计算二叉树的高度。二叉树的高度是指从根节点到最远叶子节点的最长路径上边的数目。`Height`函数计算树的高度，如果树为空，则返回0；否则，返回左子树和右子树中较高者的高度加1。 实验要求输出按层次遍历序列，即按照从根节点开始，逐层遍历所有节点的顺序。层次遍历通常使用队列来实现，因为队列是一种先进先出（FIFO）的数据结构，适合处理这种逐层处理的问题。 在菜单驱动的程序中，用户可以选择执行以上各种操作，提供了一种交互式的二叉树操作环境，有利于加深对二叉树遍历和属性的理解。通过这样的实践，学生能够更好地掌握二叉树的理论知识，并将其转化为实际的编程技能。