二叉树的遍历算法实验报告

1、二叉树实验报告09信管石旭琳 20091004418一、实验目的：1、理解二叉树的遍历算法及应用2、理解哈夫曼树及其应用。3、掌握哈夫曼编码思想。二、实验内容：1、建立二叉树二叉链表2、实现二叉树递归遍历算法（中序、前序、后序）3、求二叉树高度4、求二叉树结点个数5、求二叉树叶子个数6、将序号为偶数的值赋给左子树三、主要程序：#include<stdio.h> #include<stdlib.h> typedef int ElemType; struct BiTNode ElemType data;struct BiTNode *lch,*rch;BiTNode,*Bi

2、Tree;struct BiTNode struct BiTNode void preorder void inorder*creat_bt1();*creat_bt2();(struct BiTNode *t)(struct BiTNode *t);void postorder (struct BiTNode *t);void numbt (struct BiTNode *t);int n,n0,n1,n2;void main()int k;printf("nnn");printf("nn1. 建立二叉树方法1(借助一维数组建立)");printf(&

3、quot;nn2. 建立二叉树方法2( 先序递归遍历建立)");printf("nn3. 先序递归遍历二叉树");printf("nn4. 中序递归遍历二叉树");printf("nn5. 后序递归遍历二叉树");printf("nn6. 计算二叉树结点个数");printf("nn 7. 结束程序运行");printf("n=");doprintf("n 请输入你要执行的操作(1,2,3,4,5,6,7)");scanf("%d&qu

4、ot;,&k);printf("n");switch(k)case 1:printf(" 你选择的是操作1 ，现用方法1 进行建立二叉树n");BiTree=creat_bt1();/* 调用性质5建立二叉树算法*/break; case 2:printf(" 你选择的是操作2，现用方法2进行建立二叉树n");BiTree=creat_bt2(); /* 调用递归建立二叉树算法*/break; case 3:printf(" 你选择的是操作3，现进行先序递归遍历二叉树n 结果为 :");preorder(B

5、iTree);break;case 4:printf(" 你选择的是操作4，现进行中序递归遍历二叉树n 结果为 :");inorder(BiTree);break;case 5:printf(" 你选择的是操作5，现进行后序递归遍历二叉树n 结果为 :");postorder(BiTree);break;case 6:n=0,n0=0,n1=0,n2=0;/* 全局变量置0 */printf(" 你选择的是操作6，现进行计算二叉树结点个数n 结果为 :");numbt(BiTree);printf("n二叉树结点总数是：%d

6、",n);printf("n二叉树叶子结点数是：%d",n0);printf("n度为1 的结点数是：%d",n1);printf("n度为2的结点数是：%d",n2);break;case 7:printf(" 你选择的是操作8， 将结束本程序运行，谢谢你的使用，再见！ n");break;while(k>=1&&k<7);struct BiTNode *creat_bt1()struct BiTNode *v50,*p,*t;int i,j;ElemType e;/*输入结

7、点的序号i、结点的数据e */printf("n i,data=");scanf("%d,%d",&i,&e);while(i!=0&&e!=0)p=(struct BiTNode *)malloc(sizeof(struct BiTNode);p->data=e;p->lch=NULL;p->rch=NULL;vi=p;if (i=1)/* 序号为 1 的结点是根*/t=p;elsej=(i+1)/2;if(i%2=0)/* 序号为偶数，做左孩子*/vj->lch=p;elsevj->rch

8、=p;printf("n i,data=");scanf("%d,%d",&i,&e);return t;struct BiTNode *creat_bt2()struct BiTNode *t;int e;printf("n data=");scanf("%d",&e);if(e=0) t=NULL;/* 对于0值，不分配新结点*/elset=(struct BiTNode *)malloc(sizeof(struct BiTNode);t->data=e;t->lch=cre

9、at_bt2();/* 左孩子获得新指针值*/t->rch=creat_bt2();return (t);void preorder (struct BiTNode *t)if(t)printf("%d ",t->data);preorder(t->lch);preorder(t->rch);void inorder (struct BiTNode *t)if(t)inorder(t->lch);printf("%d ",t->data);inorder(t->rch);void postorder(struct

10、 BiTNode *t)if(t)postorder(t->lch);postorder(t->rch);printf("%d ",t->data);void numbt(struct BiTNode *t)(if(t)(numbt(t->lch);(n+;if(t->lch=NULL&&t->rch=NULL)n0+;if(t->lch=NULL&&t->rch!=NULL)|(t->lch!=NULL&&t->rch=NUL L)n1+;if(t->lch!

11、=NULL&&t->rch!=NULL)n2+;numbt(t->rch);四、测试结果：你选择的是操作。现用方法2进行建立二叉树d-at-a =1Hata=2d-at-a -4.d总七县=0data=5(Lata =0dta=0data -3datA"8dAta=6dAta=0data=0请输入你要执行的操作S /，" * J你选拄的是操作孔现进行先序递归遍历二叉树 拮果为 2 4 5 3 &请输入你要执行的操作3,2广,4.£6/4你选择的是操作现进行中序递归遍历二叉树结 为：4 2 5 13 6常输X你要执行的操作523磊5,6.7)5你选择的是操作5.现进行后序递归遍历二叉树售果为:4 5 2 6 3 1