欧阳化创编 2021..02.12
问题二叉树遍历
1.
时间：2021.02.12 一
创作人：欧阳化 ：
2. 问题描述
设输入该二叉树的前序序列为：
ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务：
⑴ 请根据此输入来建立该二叉树，并输出该二叉树的前
序、中序和后序序列；
⑵ 按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶ 求该二叉树的高度。 3. 设计描述
（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、
欧阳化创编 2021..02.12
欧阳化创编 2021..02.12
LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。
（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。 （3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序
1 #include
10 void CreateBTree(structBTreeNode** T) 11 { 12 14 15 16
char ch;
if (ch == '#') *T = NULL; else {
(*T) = malloc(sizeof(structBTreeNode));
13 scanf_s(\
欧阳化创编 2021..02.12
欧阳化创编 2021..02.12
17
(*T)->data = ch;
18 CreateBTree(&((*T)->left)); 19 CreateBTree(&((*T)->right)); 20 21 }
22 void Preorder(structBTreeNode* T) 23 { 24 26 27 28 29 }
30 void Inorder(structBTreeNode* T) 31 { 32 33 34 36 37 }
38 void Postorder(structBTreeNode* T) 39 { 40
if (T != NULL) {
41 Postorder(T->left); 42 Postorder(T->right); 43 printf(\ 44 45 }
46 void Levelorder(structBTreeNode* BT) 47 {
48 structBTreeNode* p; 49 structBTreeNode* q[30]; 50 int front=0,rear=0; 51 52 53 54
if(BT!=NULL) { rear=(rear+1)% 30; q[rear]=BT; } }
if (T != NULL) { Inorder(T->left); printf(\ }
if (T != NULL) { Preorder(T->left); Preorder(T->right); }
25 printf(\
}
35 Inorder(T->right);
欧阳化创编 2021..02.12
数据结构二叉树遍历实验报告之欧阳化创编
