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

1实验四二叉树的建立和遍历学院专业班学号姓名一．实习目的1.掌握二叉链表的存储结构；2.掌握二叉链表的建立；3.掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法；4.掌握二叉树遍历算法的应用；二．实习内容1.按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示）2.对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。3．统计二叉树中结点个数；4.求二叉树的高度；三．实验步骤1.定义二叉链表的存储结构#includestdio.h#includestdlib.htypedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;2.编写函数CreateBiTree，按先序序列建立二叉树的二叉链表;测试的字符序列为abdg###e##c#f##;程序代码为：voidCreateBiTree(BiTree&T){//算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，构造二叉链表表示的二叉树T。以#表示空树TElemTypech;scanf(%c,&ch);if(ch=='#')//空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));//生成根结点if(!T)2exit(-1);T-data=ch;CreateBiTree(T-lchild);//递归构造左子树CreateBiTree(T-rchild);//构造右子树}}2.编写二叉树的先序遍历、中序遍历、后序遍历的递归算法intpreOrderTraverse(BiTreeT){//初始条件：二叉树T存在，先序递归遍历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(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);//后序遍历右子树printf(%5c,T-data);//访问根结点3}}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.编写函数求二叉树的高度；intBitheight(BiTreeT){intlh,rh,th;if(T==NULL)return0;lh=Bitheight(T-lchild);//递归求T的左子树的高度lhrh=Bitheight(T-rchild);//递归求T的右子树的高度rhif(lhrh)th=lh+1;elseth=rh+1;returnth;}4.编写main函数，调用函数，输出结构voidmain(){inti,k,h;BiTreeT;printf(请按先序输入二叉树(如:ab###表示a为根结点,b为左子树的二叉树)\n);CreateBiTree(T);printf(先序遍历的结果为：\n);i=preOrderTraverse(T);printf(\n);printf(中序遍历的结果为：\n);i=inOrderTraverse(T);printf(\n);printf(后序遍历的结果为：\n);i=postOrderTraverse(T);printf(\n);k=countND(T);4printf(结点个数为%d\n,k);h=Bitheight(T);printf(输出树的高度为%d\n,h);}4.运行结果（截图）图1.二叉树的建立和遍历四实验小结通过本次实习，我掌握了先序、中序、后序遍历中的递归算法的使用，从而实现了对二叉树的先序、中序、后序遍历。