计算机软件基础实验2二叉树

1、实 验 报 告实验项目 计算机软件基础 实验2 二叉树 实验仪器 电脑 学院/班级 学号/姓名 实验日期 一、实验名称 二叉树的应用二、实验目的 掌握二叉树的链式和顺序存储结构，利用队列对二叉树进行运算。三、实验内容（1）编写函数creatbt,其功能是将一维数组方式存储的二叉树转化为链式存储的二叉树，返回root指针。（2）编写函数freebt，其功能是释放二叉树链表节点的存储空间。函数原型为：void freebt (TNODE * root)（3）编写函数实现前序、中序和后序遍历；（4）用下面的应用程序作测试，检查输出结果：void main() int t_array14=8,11,2

2、,3,9,15,6,-1,-1,-1,10,-1,-1,13; /-1表示空struct tnode *root;root=creatbt(t_array,14,0);preorder(root);inorder(root);postorder(root);freebt(root);int t_array14=8,11,2,3,9,15,6,-1,-1,-1,10,-1,-1,13;/-1表示空前序：8,11,3,9,10,2,15,6,13中序: 3,11,9,10,8,15,2,13,6后序：3,10,9,11,15,13,6,2,8层次：8,11,2,3,9,15,6,10,13结点总个

3、数：9个叶子个数：4个（5）（选做）编写函数计算二叉树结点总数和叶子结点的个数；int node_sum(TNODE *bt) ;int leaf_sum(TNODE *bt);（6）（选做）编写算法实现对树中结点按层次遍历的函数，函数原型为：void leveltrav(TNODE * bt);算法概述：i.设置一个队列，TNODE *queueMAXSIZE 其元素的数据类型为TNODE *，将bt(根root)入队；ii.重复以下过程直至队空：取出队头元素到bt，若bt->lchild不为空，则输出bt->lchild->data，且bt->lchild入队；若b

4、t->rchild不为空，则输出bt->rchild->data，且bt>rchild入队。（7）(选做) 把二叉树所有结点的左右子树交换void exchage(TNODE *bt); 交换后为前序：8,2,6,13,15,11,9,10,3中序: 6,13,2,15,8,10,9,11,3,后序：13,6,15,2,10,9,3,11,8层次：8,2,11,6,15,9,3,13,10四、调试结果分析图1、运行界面五、实验心得本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我是按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序

5、、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历，其中递归的三种遍历大同小异，此处仅以中序代替，非递归遍历则通过栈来实现，在入栈出栈中要注意一些边界条件，否则会出现运行错误，层次遍历通过队列实现；在本此实验中吗，栈队列我调用了库函数里的模板，这样是整个程序看起来简单多了；二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，这里不再赘述，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。附录：实验代码#include <stdio.h>#include <stdlib.h>#include <

6、;malloc.h>#include <string.h>int count=0;typedef struct TNODEint data;struct TNODE *lchild,*rchild;TNODE;TNODE *creatbt(int T,int n,int i) /递归 创建二叉树程序 TNODE *r; if (i>n-1|Ti=-1) /-1表示空 总计n个数存储在 0-n-1 return (NULL); r=(TNODE *)malloc(sizeof(TNODE); r->data=Ti; r->lchild=creatbt(T,n,

7、2*i+1); r->rchild=creatbt(T,n,2*i+2); return(r);void preorder(struct TNODE *BT) /前序遍历二叉树 if(BT!=NULL) printf("%d, ",BT->data); preorder(BT->lchild); preorder(BT->rchild); void inorder(struct TNODE *BT) /中序遍历二叉树 if(BT!=NULL) inorder(BT->lchild); printf("%d, ",BT->

8、;data); inorder(BT->rchild); void postorder(struct TNODE *BT) /后序遍历二叉树 if(BT!=NULL) postorder(BT->lchild); postorder(BT->rchild); printf("%d, ",BT->data); int leaf_sum(struct TNODE *BT) /求叶子节点数 if(!BT) return 0; else if(!BT->lchild&&!BT->rchild) return 1; else ret

9、urn leaf_sum(BT->lchild)+leaf_sum(BT->rchild);int node_sum(struct TNODE *BT) /计算二叉树结点个数，需定义全局变量count if(BT) node_sum(BT->lchild); node_sum(BT->rchild); count+; /结点个数 return count;void leveltrav(struct TNODE *BT) /按层次遍历二叉树TNODE *p; TNODE *qu9; int front,rear; front=rear=-1; rear+; qurear=

10、BT; while(front!=rear) front=(front+1)%9; p=qufront; printf("%d,",p->data); if(p->lchild!=NULL) rear=(rear+1)%9; qurear=p->lchild; if(p->rchild!=NULL) rear=(rear+1)%9; qurear=p->rchild; void exchage(struct TNODE *BT) struct TNODE *temp; if (BT = NULL) return; exchage(BT ->

11、;lchild); /交换左子树 exchage(BT ->rchild); /交换右子树 temp = NULL; temp = BT ->lchild; /交换 BT->lchild=BT->rchild; BT->rchild=temp;void freebt(struct TNODE *BT) /释放二叉树的所有结点 if(BT=NULL) /*若是空树*/ return; freebt(BT->lchild);/*递归调用*/ freebt(BT->rchild); BT->lchild=NULL; BT->rchild=NULL

12、; free(BT);void main() int t_array14=8,11,2,3,9,15,6,-1,-1,-1,10,-1,-1,13; /-1表示空 struct TNODE *root; root=creatbt(t_array,14,0); printf("二叉树先序遍历结果是：n");preorder(root);printf("n");printf("二叉树中序遍历结果是：n");inorder(root);printf("n");printf("二叉树后序遍历结果是：n"

13、);postorder(root);printf("n"); printf("二叉树叶子节点的个数是:n %dn",leaf_sum(root); printf("二叉树结点总个数是:n %dn",node_sum(root);printf("二叉树层次遍历结果是：n");leveltrav(root);printf("nn");exchage(root); /二叉树所有结点的左右子树交换 printf("二叉树所有结点的左右子树交换nn");printf("交换后二叉树先序遍历结果是：n");preorder(root);printf("n");printf("交换后二叉树中序遍历结果是：n");inorder(root);printf(