发布时间 : 星期三 文章北理工数据结构实验3更新完毕开始阅读9a08e0b4ce2f0066f5332272
为表面上看是没有错误的，真是花蕾大量的时间看才发现的，同时也给了我一个很重要的提示，参数少的时候要看看字符的问题，做程序一定要谨慎。 改成如下正确。
五、用户使用说明
1、本程序的运行环境为DOS操作系统
2、进入程序后，在\输入二叉树的扩展的前序序列\后按照拓展的前序序列（即 空子树处输入*）输入二叉树，回车后程序即运行。 3、程序运行后即在屏幕上输出计算结果。 六、程序运行结果
测试一： 书上127页的二叉树
测试二：书上133页的二叉树
七、程序清单 #include\#include\#define ok 1 #define error 0
9
/* 二叉链表的结点 */ typedef struct BiTNode {
char data;
struct BiTNode * lchild, * rchild; }BiTNode,*BiTree; /* 队列 */
typedef BiTree QElemType; //定义队列元素类型 typedef struct QNode {
QElemType data; struct QNode *next;
}QNode,*QueuePtr; //定义队列结点 typedef struct { QueuePtr front; QueuePtr rear;
}LinkQueue; //定义队列数据类型
char c; //输入的字符
/* 创建队列*/
int InitQueue(LinkQueue &Q) {
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(1); //存储分配失败 Q.front->next=NULL; return ok; }
/*插入元素e作为新的队尾元素*/
int EnQueue( LinkQueue &Q,QElemType e) {
QNode * p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(1); p->data=e;
p->next=NULL; Q.rear->next=p; Q.rear=p; return ok; }
/*删除队头元素并以e返回*/
int DeQueue(LinkQueue & Q,QElemType & e) {
if(Q.front==Q.rear) return error;
10
QNode *p=Q.front->next; e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front; free(p); return ok; }
/* 建立二叉树 */
int CreateTree(BiTree & T) { c=getchar(); if(c=='*') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) { printf(\ T->data=c; CreateTree(T->lchild); //递归建立左子树 CreateTree(T->rchild); //递归建立右子树 }
return ok; }
int Visit(char e)
{ printf(\ \
/* 先序遍历二叉树 */
int PreOrderTraverse(BiTree T,int (*Visit)( char c)) {
if(T) { Visit(T->data);
PreOrderTraverse(T->lchild,Visit); //先序遍历左子树 PreOrderTraverse(T->rchild,Visit); //先序遍历右子树 }
return ok; }
/* 中序遍历二叉树 */
int InOrderTraverse(BiTree T,int (*Visit)( char c)) {
if(T)
11
{ InOrderTraverse(T->lchild,Visit); //中序遍历左子树 Visit(T->data); InOrderTraverse(T->rchild,Visit); //中序遍历右子树 }
return ok; }
/* 后序遍历二叉树 */
int PostOrderTraverse(BiTree T,int (*Visit)( char c)) {
if(T) { PostOrderTraverse(T->lchild,Visit); //后序遍历左子树 PostOrderTraverse(T->rchild,Visit); //后序遍历右子树 Visit(T->data); }
return ok; }
/*层次遍历二叉树 */
int LevelOrderTraverse(BiTree & T) {
QElemType p; LinkQueue q; InitQueue(q);
if(T) EnQueue(q,T); //队头元素进队列 while(!(q.front==q.rear)) { DeQueue(q,p);
printf(\ \输出队头元素 if(p->lchild) EnQueue(q,p->lchild); //左子树进队列 if(p->rchild) EnQueue(q,p->rchild); //右子树进队列 }
return ok; }
int main() {
BiTree T;
printf(\输入二叉树的扩展的前序序列\\n\ CreateTree(T);
printf(\二叉树的先序序列：\
PreOrderTraverse(T,Visit); printf(\ printf(\二叉树的中序序列：\
InOrderTraverse(T,Visit); printf(\ printf(\二叉树的后序序列：\
12
PostOrderTraverse(T,Visit); printf(\ printf(\二叉树的层次遍历序列：\
LevelOrderTraverse(T); printf(\ return ok; }
13