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

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

2、#) T=NULL;elseT=(Bitnode*)malloc(sizeof(Bitnode);T-data=ch;createBitree(T-lchild);createBitree(T-rchild);先序遍历二叉树： void preorder(Bitree &T)if(T!=NULL)printf(%c,T-data);preorder(T-lchild);preorder(T-rchild);.中序遍历二叉树： voidinorder(Bitree &T)if(T!=NULL) inorder(T-lchild); printf(%c,T-data); inorder(T-rch

3、ild);后序遍历二叉树： voidpostorder(Bitree &T)if(T!=NULL)postorder(T-lchild);postorder(T-rchild);printf(%c,T-data);/ 后序遍历后序遍历求二叉树深度：intDepth(Bitree &T)/ 返回深度int d,dl,dr;if(!T)d=0;else dl=Depth(T-lchild);dr=Depth(T-rchild);d=1+(dldr?dl:dr) ;return d;4. 运行、测试与分析运行程序，显示菜单，（ 1） 如图 1.1:图 1.1（ 2） 结果图 1.2：图 1.2.5.

4、 实验收获及思考在实验过程中学会了调试程序，对于二叉树的相关知识有了不同的认识，不仅仅是抽象上的了。更重要的是懂得了自己写程序的重要性，慢慢养成习惯。6. 源代码#include#includetypedef struct Bitnode char data;struct Bitnode *lchild,*rchild;Bitnode,*Bitree;/ 建立二叉树void createBitree(Bitree &T)char ch;if(ch=getchar()=#) T=NULL;elseT=(Bitnode*)malloc(sizeof(Bitnode);T-data=ch;creat

5、eBitree(T-lchild);createBitree(T-rchild);/ 先序遍历输出结点 void preorder(Bitree &T)if(T!=NULL)printf(%c,T-data);preorder(T-lchild);preorder(T-rchild);void inorder(Bitree &T)if(T!=NULL) inorder(T-lchild); printf(%c,T-data);inorder(T-rchild);/ 中序遍历voidpostorder(Bitree &T)if(T!=NULL)postorder(T-lchild);postor

6、der(T-rchild);.printf(%c,T-data);/后序遍历/ 后序遍历求深度 int Depth(Bitree &T) / 返回深度int d,dl,dr; if(!T) d=0;else dl=Depth(T-lchild); dr=Depth(T-rchild);d=1+(dldr?dl:dr) ;return d;int main()printf(*二叉树链表存储 *);printf(n1.建立二叉链表 n2. 先序遍历 n3. 中序遍历 n4. 后续遍历 n5. 后序遍历求深度 n);printf(例子： abc#de#g#f#n);Bitree T;printf(输入树的结点 :n);createBitree(T);printf(先序为： n);preorder(T);print