北理工数据结构实验3

为表面上看是没有错误的，真是花蕾大量的时间看才发现的，同时也给了我一个很重要的提示，参数少的时候要看看字符的问题，做程序一定要谨慎。 改成如下正确。

五、用户使用说明

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