二叉树链式存储结构 第六章实验报告

《二叉树链式存储结构 第六章实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验名称:二叉树链式存储结构实验类型：验证性实验班级：20102111学号：2010211102姓名：实验日期：2012.5.271.问题描述二叉链表的C语言描述；基本运算的算法——建立二叉链表、先序遍历二叉树、中序遍历二叉树、后序遍历二叉树、后序遍历求二叉树深度。2.数据结构设计typedefstructBitnode{chardata;structBitnode*lchild,*rchild;}Bitnode,*Bitree;3.算法设计建立二叉链表：voidcreateBitree(Bitree&T){charch

2、;if((ch=getchar())=='#')T=NULL;else{T=(Bitnode*)malloc(sizeof(Bitnode));T->data=ch;createBitree(T->lchild);createBitree(T->rchild);}}先序遍历二叉树：voidpreorder(Bitree&T){if(T!=NULL){printf("%c",T->data);preorder(T->lchild);preorder(T->rchild);}}中序遍历二叉树：voidinorder(Bitr

3、ee&T){if(T!=NULL){inorder(T->lchild);printf("%c",T->data);inorder(T->rchild);}后序遍历二叉树：voidpostorder(Bitree&T){if(T!=NULL){postorder(T->lchild);postorder(T->rchild);printf("%c",T->data);}}//后序遍历后序遍历求二叉树深度：intDepth(Bitree&T){//返回深度intd,dl,dr;if(!T)d=0;else{dl=Depth

4、(T->lchild);dr=Depth(T->rchild);d=1+(dl>dr?dl:dr);}returnd;}4.运行、测试与分析运行程序，显示菜单，（1）如图1.1:图1.1（2）结果图1.2：图1.25.实验收获及思考在实验过程中学会了调试程序，对于二叉树的相关知识有了不同的认识，不仅仅是抽象上的了。更重要的是懂得了自己写程序的重要性，慢慢养成习惯。6.源代码#include#includetypedefstructBitnode{chardata;structBitn

5、ode*lchild,*rchild;}Bitnode,*Bitree;//建立二叉树voidcreateBitree(Bitree&T){charch;if((ch=getchar())=='#')T=NULL;else{T=(Bitnode*)malloc(sizeof(Bitnode));T->data=ch;createBitree(T->lchild);createBitree(T->rchild);}}//先序遍历输出结点voidpreorder(Bitree&T){if(T!=NULL){printf("%

6、c",T->data);preorder(T->lchild);preorder(T->rchild);}}voidinorder(Bitree&T){if(T!=NULL){inorder(T->lchild);printf("%c",T->data);inorder(T->rchild);}}//中序遍历voidpostorder(Bitree&T){if(T!=NULL){postorder(T->lchild);postorder(T->rchild);printf("%c",T->data);}}//后序遍历/

7、/后序遍历求深度intDepth(Bitree&T){//返回深度intd,dl,dr;if(!T)d=0;else{dl=Depth(T->lchild);dr=Depth(T->rchild);d=1+(dl>dr?dl:dr);}returnd;}intmain(){printf("**********二叉树链表存储********");printf("1.建立二叉链表2.先序遍历3.中序遍历4.后续遍历5.后序遍历求深度");printf("例子：abc##de#g##f###");B

8、itreeT;printf("输入树的结点:");createBitree(T);printf("先序为：");preorder(T);printf("中序遍历为：");inorder(T);printf("后序为：");postorder(T);printf("后序求深度：%d",Dep