问题一： 二叉树遍历 1. 问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴ 请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵ 按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶ 求该二叉树的高度。 2. 设计描述 （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 BTreeNode* left; struct BTreeNode* right; 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 }; void CreateBTree(struct BTreeNode** T) { char ch; scanf_s("\n%c", &ch); if (ch == '#') *T = NULL; else { (*T) = malloc(sizeof(struct BTreeNode)); (*T)->data = ch; CreateBTree(&((*T)->left)); CreateBTree(&((*T)->right)); } } void Preorder(struct BTreeNode* T) { if (T != NULL) { printf("%c ", T->data); P...
VIP
