北理工数据结构实验3

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; 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)

5

{ 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) { 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))

6

{ 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(\二叉树的后序序列：\

PostOrderTraverse(T,Visit); printf(\ printf(\二叉树的层次遍历序列：\

LevelOrderTraverse(T); printf(\ return ok; }

四、程序调试分析

（1）在编写的过程中对于visit的使用一直不太明白，开始我认为参数应该是一个函数的指针所以如下定义了一个函数指针的的变量

结果编译通不过报错，说函数指针Visit没有类型

7

后来经过不断地尝试终于弄对了，函数指针的定义和使用应该如下所示

最后我去交流，老师说其实不用非得用函数指针去做，函数的名本身也代表着函数的入口地址，也是一个指针变量，如下就可以

虽然在这次的过程中浪费了不少的时间自己转了一个大圈子，但对于一直不太明白的指针变量这次有了一个比较准确的把握，同时也学会了指针变量的具体使用还是很有收获的

（2） 在完成了对于visit的正确使用时，遇到了新的问题，如下所示

感觉程序没有什么问题，老师看了也说没什么问题，问题的解决还要依赖于对于报错的提示，如上，提示说函数PreOrderTraverse（）的参数不应该只有一个应该有两个，而程序上方很明显有两个参数，说明是书写有问题，在仔细一看原来是参数间的“，”写的是中文的所以当成了一个参数，这种虽然看起来是不起眼的小问题，但同时也是最难发现的，因

8