二叉树的创建与遍历实验报告.doc

《二叉树的创建与遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课内实验报告书一、实验题目：二叉树的创建与遍历二、实验目的：通过本次实验，熟练掌握二叉树的存储结构定义及其遍历算法的实现，学会利用栈编写非递归的遍历算法。三、实验要求：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。要求：从键盘接受扩展先序序列，以二叉链表作为存储结构，建立二叉树，并将遍历结果打印输出。采用递归和非递归两种方法实现。四、设计与实现过程（1）存储结构定义typedefcharelemtype;typedefstructNode{elemtypedata

2、;structNode*lchild;structNode*rchild;}BitNode;（2）算法描述Node*creat(Node*pre){chare;Node*head;e=getchar();if(e!=''){head=(Node*)malloc(sizeof(Node));head->data=e;head->Lchild=creat(head);if(head->Lchild==NULL){head->Lflag=1;head->Lchild=pre;}head->Rchild=creat(hea

3、d);if(pre!=NULL&&pre->Rchild==NULL){pre->Rflag=1;pre->Rchild=head;}returnhead;}else{returnNULL;}}Node*InPre(Node*root){Node*p;if(root->Lflag==1){p=root->Lchild;}else{for(p=root->Lchild;p->Rflag==0;p=p->Rchild);}returnp;}Node*InNext(Node*root){Node*p;if(root->R

4、flag==1){p=root->Rchild;}else{for(p=root->Rchild;p->Lflag==0;p=p->Lchild);}returnp;}Node*Infirst(Node*root){Node*p;p=root;if(!p){fprintf(stdout,"n");returnNULL;}while(p->Lflag==0){p=p->Lchild;}returnp;}voidTInOrder(Node*root){Node*p;p=Infirst(root);while(p!=NU

5、LL){fprintf(stdout,"%c",p->data);p=InNext(p);}printf("");}五、运行结果输入ABECD输出BEADC六、技巧与体会通过实验，锻炼了自己的能力，加深了自己对有关知识的理解。以后要加强动手时间能力、多与同学交流算法精髓！在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学到很多的知识、熟练编程！