二叉树遍历课程设计】

1、数据结构程序设计报告学院：班级：学号： 姓名：实验名称：二叉树的建立与遍历一、 实验目的：1.掌握二叉树的二叉链表存储结构；2.掌握二叉树创建方法；3.掌握二叉树的先序、中序、后序的递归实现方法。二、实验内容和要求：创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。三、叉树的建立与遍历代码如下：#include <stdio.h>#include <malloc.h>struct tnode/结点结构体char data;struct tnode *lchild,*rchild;typedef struct tnode TNODE;TNODE *cre

2、at(void)TNODE *root,*p;TNODE *queue50; int front=0,rear=-1,counter=0;/初始队列中需要的变量front、rear和计数器counterchar ch;printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)n"); ch=getchar();while(ch!='!')if(ch!='#') p=(TNODE *)malloc(sizeof(TNODE); p->data=ch; p->lchild=NULL; p->rchild=NULL;re

3、ar+; queuerear=p;/把非#的元素入队if(rear=0)/如果是第一个元素，则作为根节点root=p;counter+;elseif(counter%2=1)/奇数时与其双亲的左子树连接queuefront->lchild=p;if(counter%2=0)/偶数时与其双亲的右子树连接queuefront->rchild=p;front+;counter+; else/为#时，计数，但不连接结点if(counter%2=0)front+;counter+;ch=getchar();return root;void preorder(TNODE *bt)/先序遍历if

4、(bt!=NULL)printf("%c ",bt->data);preorder(bt->lchild);preorder(bt->rchild); void inorder(TNODE *bt)/中序遍历if(bt!=NULL)inorder(bt->lchild);printf("%c ",bt->data);inorder(bt->rchild); void postorder(TNODE *bt)/后序遍历if(bt!=NULL)postorder(bt->lchild);postorder(bt-&g

5、t;rchild);printf("%c ",bt->data); int main() TNODE *root; root=creat();printf("递归先序遍历是:"); preorder(root);printf("n");printf("递归中序遍历是：");inorder(root);printf("n");printf("递归后序遍历是：");postorder(root);printf("n");return 0;四、程序运行结果

6、：五、程序设计指导：1.创建二叉树的算法：首先对一般的二叉树，添加若干个虚结点使其成为完全二叉树，然后依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点，若是第一个，则令其为根结点，否则将新结点链接至它的双亲结点上。如此重复下去，直至遇到输入结束符（自定）为止。为了使新结点能够与双亲结点正确相连，并考虑到这种方法中先建立的结点其孩子结点也一定先建立的特点，可以设置一个指针类型的数组构成的队列来保存已输入结点的地址，并使队尾(rear)指向当前输入的结点，队头(front)指向这个结点的双亲结点的前一个位置。由于根结点的地址放在队列的第一个单元里，所以当rear为奇数时，则rear所指的

7、结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则无须链接。若一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。2. void preorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先读取，再进行进入下一个递归循环中。3.void inorder(TNODE *bt)函数 ：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先左子树，再读取结点元素，再进行进入下一个递归循环中。4.void postorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先分别进入左右子树，再进行读取，再进行进入下一个递归循环中。六、心得体会：本次数据结构程序设计对我有一定的帮助。通过这次的实践，使我对数据结构这门课程有了更深入