问题一： 二叉树遍历 1
问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴ 请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵ 按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶ 求该二叉树的高度
设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列
二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）
根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6 种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR
研究二叉树的遍历就是研究这6 种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR 与NRL、LNR 与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR 和LRN 三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”
采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观
（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点
遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束
（3）计算二叉树高度也 是利用递归来实现：若 一颗 二叉树为空，则 它的深 度为0，否 则 深 度等 于 左右子树的最 大 深 度加 一
3． 源 程序 1 2 3 4 5 6 7 8 #include #include #include #define ElemType char struct BTreeNode { ElemType data; struct BTreeNod
