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

实验名称:二叉树链式存储结构实验类型：验证性实验班级：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()=#) 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); 中序遍历二叉树：void inorder(Bitree &T)if(T!=NULL) inorder(T-lchild); printf(%c,T-data); inorder(T-rchild); 后序遍历二叉树：void postorder(Bitree &T) if(T!=NULL)postorder(T-lchild); postorder(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; 4.运行、测试与分析运行程序，显示菜单，（1） 如图1.1: 图1.1（2） 结果图1.2：图1.25.实验收获及思考在实验过程中学会了调试程序，对于二叉树的相关知识有了不同的认识，不仅仅是抽象上的了。更重要的是懂得了自己写程序的重要性，慢慢养成习惯。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;createBitree(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); /中序遍历void postorder(Bitree &T) if(T!=NULL)postorder(T-lchild); postorder(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); printf(