二叉树的建立和遍历实验报告

《二叉树的建立和遍历实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四二叉树的建立和遍历学院专业班学号姓名一．实习目的1.掌握二叉链表的存储结构；2.掌握二叉链表的建立；3.掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法；4.掌握二叉树遍历算法的应用；二．实习内容1.按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示）2.对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。3．统计二叉树中结点个数；4.求二叉树的高度；三．实验步骤1.定义二叉链表的存储结构#include"stdio.h"#include"stdlib.h"typedefcha

2、rTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;2.编写函数CreateBiTree，按先序序列建立二叉树的二叉链表;测试的字符序列为abdg###e##c#f##;程序代码为：voidCreateBiTree(BiTree&T){//算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，构造二叉链表表示的二叉树T。以#表示空树T

3、ElemTypech;scanf("%c",&ch);if(ch=='#')//空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));//生成根结点if(!T)4exit(-1);T->data=ch;CreateBiTree(T->lchild);//递归构造左子树CreateBiTree(T->rchild);//构造右子树}}2.编写二叉树的先序遍历、中序遍历、后序遍历的递归算法intpreOrderTraverse(BiTreeT){//初始条件：二叉树T

4、存在，先序递归遍历T；if(T==NULL)return1;if(T!=NULL)//T不空{printf("%5c",T->data);//访问根结点preOrderTraverse(T->lchild);//先序遍历左子树preOrderTraverse(T->rchild);//先序遍历右子树}}intinOrderTraverse(BiTreeT){//初始条件：二叉树T存在，中序递归遍历T；if(T==NULL)return1;if(T!=NULL)//T不空{inOrderTraverse(

5、T->lchild);//中序遍历左子树printf("%5c",T->data);//访问根结点inOrderTraverse(T->rchild);//中序遍历右子树}}intpostOrderTraverse(BiTreeT){//初始条件：二叉树T存在，//操作结果：后序递归遍历T；if(T==NULL)return1;if(T!=NULL)//T不空{postOrderTraverse(T->lchild);//后序遍历左子树postOrderTraverse(T->rchild);//后序遍

6、历右子树printf("%5c",T->data);//访问根结点4}}3.编写函数统计二叉树中结点个数；（遍历算法）intcountND(BiTreeT){intn=0,k=0,m=0;if(T==NULL)return0;else{if(T->lchild!=NULL)k=countND(T->lchild);//后序遍历左子树,得到左子树结点个数if(T->rchild!=NULL)m=countND(T->rchild);//再后序遍历右子树n=m+k+1;}returnn;}4.编写函数求二叉

7、树的高度；intBitheight(BiTreeT){intlh,rh,th;if(T==NULL)return0;lh=Bitheight(T->lchild);//递归求T的左子树的高度lhrh=Bitheight(T->rchild);//递归求T的右子树的高度rhif(lh>rh)th=lh+1;elseth=rh+1;returnth;}4.编写main函数，调用函数，输出结构voidmain(){inti,k,h;BiTreeT;printf("请按先序输入二叉树(如:ab###表示a为根结

8、点,b为左子树的二叉树)");CreateBiTree(T);printf("先序遍历的结果为：");i=preOrderTraverse(T);printf("");printf("中序遍历的结果为：");i=inOrderTraverse(T);printf("");printf("后序遍历的结果为：");i=postOrderTraverse(T);printf("");k=countND(T);4prin