二叉树遍历第六次实验

1、实验十：高校本科招生最低录取分数线查询系统【问题描述】 二叉树采用二叉链表作存储结构，编程实现二叉树的如下基本操作：按先序序列构造一棵二叉链表表示的二叉树 T；对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序 列；求二叉树的深度/结点数目/叶结点数目；【数据描述】/ 二叉树的二叉链表存储表示 typedef struct BiTNodeTElemType data;Struct BiTNode * lchild, * rchild; /左右孩子指针BiTNode, * BiTree;【算法描述】建立一棵二叉树 BiTree CreateBiTree(BiTree &

2、T) / 算法6.4/ 按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树， /构造二叉链表表示的二叉树T。char ch;scanf(%c,&ch);if (ch=#) T = NULL;else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) return ERROR; T-data = ch;/ 生成根结点CreateBiTree(T-lchild);/ 构造左子树CreateBiTree(T-rchild);/ 构造右子树return T; / CreateBiTree先序遍历二叉树递归算法void Preorder (BiTree T

3、, void( *visit)(TElemType& e) / 先序遍历二叉树if (T) visit(T-data); / 访问结点 Preorder(T-lchild, visit); / 遍历左子树 Preorder(T-rchild, visit);/ 遍历右子树中序遍历的递归算法void Inorder (BiTree T, void( *visit)(TElemType& e) / 中序遍历二叉树if (T) Inorder(T-lchild, visit); / 遍历左子树 visit(T-data); / 访问结点 Inorder(T-rchild, visit);/ 遍历右子

4、树后序遍历递归算法void Postorder (BiTree T, void( *visit)(TElemType& e) / 后序遍历二叉树if (T) Postorder(T-lchild, visit); / 遍历左子树 Postorder(T-rchild, visit);/ 遍历右子树 visit(T-data); / 访问结点中序遍历非递归算法之一Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2/采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 /中序遍历二叉树T的非递归算法，对每个数

5、据元素调用函数Visit。 stack S;BiTree p;InitStack(S); Push(S, T); / 根指针进栈while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); / 向左走到尽头 Pop(S, p);/ 空指针退栈if (!StackEmpty(S) / 访问结点，向右一步Pop(S, p);if (!Visit(p-data) return ERROR;Push(S, p-rchild);return OK; / InOrderTraverse中序遍历非递归算法之二Status InOrderT

6、raverse(BiTree T, Status (*Visit)(ElemType) / 算法 6.3/采用二叉链表存储结构，Visit是对数据元素操作的应用函数。/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。stack S;BiTree p;InitStack(S); p = T;while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; /非空指针进栈，继续左 进else / 上层指针退栈，访问其所指结点，再向右进Pop(S, p);if (!Visit(p-data) return ERROR;p = p-r

7、child;return OK; / InOrderTraverse7 层次遍历二叉树的非递归算法Status LevelOrder(BiTree T)按层次遍历二叉树T, Q为队列InitQueue(Q);If (T!=NULL)/ 若树非空EnQueue(Q,T);根结点入队列While (!QueueEmpty(Q)DeQueue(Q,b); /队首元素出队列Visit(b-data); /访问结点If (b-lchild!=NULL) EnQueue(Q,b-lchild);左子树非空，则入队列If (b-rchold!=Null) EnQueue(Q,b-rchild); 右子树非空

8、，则入队列/while/ifLevelOrder8 求二叉树的深度int depth(BiTree T)若T为空树，则深度为0否则其深度等于左子树或右子树的最大深度加1if (T=NULL) return 0;else dep1=depth(T-lchild);dep2=depth(T-rchild);return dep1dep2?dep1+1:dep2+1;【C 源程序】#include #include #define MAX 20#define NULL 0typedef char TElemType;typedef int Status;typedef struct BiTNodeT

9、ElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;Status CreateBiTree(BiTree *T)char ch; ch=getchar();if (ch=#) (*T)=NULL;/* #代表空指针*/else (*T)=(BiTree) malloc(sizeof(BiTNode);/* 申请结点 */(*T)-data=ch;/*生成根结点 */CreateBiTree(&(*T)-lchild) ;/*构造左子树 */CreateBiTree(&(*T)-rchild) ;/*构造右子树 */retur

10、n 1;void PreOrder(BiTree T)if (T) printf(%2c,T-data); /*访问根结点，此处简化为输出根结点的数据值*/PreOrder(T-lchild); /*先序遍历左子树*/PreOrder(T-rchild); /*先序遍历右子树*/void LevleOrder(BiTree T)/*层次遍历二叉树T,从第一层开始，每层从左到右*/BiTree QueueMAX,b;/*用一维数组表示队列，front和rear分别表示队首和队尾指针 */BiTree QueueMAX,b;int front,rear;front=rear=0;/*根结点入队列*

11、/*当队列非空/*根结点入队列*/*当队列非空*/*队首元素出队列，并访问这个结点*/Queuerear+=T; while (front!=rear) b=Queuefront+;printf(%2c,b-data);if (b-lchild!=NULL) Queuerear+=b-lchild; /*左子树非空，则入队列*/ if (b-rchild!=NULL) Queuerear+=b-rchild; /*右子树非空，则入队列*/LevelOrderint depth(BiTree T) /*求二叉树的深度*/int dep1,dep2; if (T=NULL) return 0;el

12、se dep1=depth(T-lchild); dep2=depth(T-rchild); return dep1dep2?dep1+1:dep2+1;/depthmain()BiTree T=NULL;printf(nCreate a Binary Treen); CreateBiTree(&T); /*建立一棵二叉树 T*/ printf(nThe preorder is:n);PreOrder(T);/*先序遍历二叉树*/printf(nThe level order is:n);LevleOrder(T); /*层次遍历二叉树*/ printf(nThe depth is:%dn,depth(T); 【测试数据】输入：#/，建立一棵空树，先序遍历和层次遍历没有输出，树的深度输出为 0输入：A/先序和层次遍历输出均为 A；深度输出为： 1输入：ABC#DE#G#F#/,先序输出为： AB C D E G F层次遍历输出为： A B C D E F G深度输出为： 5二叉树中叶子结点的个数: 3二叉树中以值为 B 的结点为根的子树深度: 4 【说明】1. 按先序次序输入二叉树中结点的值，用#表示空树，对