二叉树实验报告

数据结构实验报告实验名称：二叉树班 级：12级电气本2学 号：2012081227姓 名：赵雪磊指导教师：梁海丽日 期：2013年10月7日数学与信息技术学院一、 实验目的1.掌握二叉树的存储实现方法。2.掌握二叉树的基本操作：建立二叉树、二叉树的遍历等运算在链式存储结构上的实现。二、 实验要求1.以二叉树先序的序列为输入顺序建立一个二叉树，从键盘输入二叉树的扩充的先序序列，以#字符代表要NULL二叉树标志，用递归算法；2.用递归算法输出二叉树的先序序列；3.用递归算法输出二叉树的后序序列。三、 算法描述#includestdio.h #include #includestdlib.hchar pre =A,B,D,H,L,E,K,C,F,G; char mid =H,L,D,B,E,K,A,F,C,G; typedef struct _Node char v; struct _Node *left; struct _Node *right; Node,*PNode;int Position(char c) return strchr(mid,c)-mid; void PreMidCreateTree(PNode pn,int i,int j,int len) Int m; if(lenv=prei; m=Position(prei); PreMidCreateTree(pn-left,i+1,j,m-j); PreMidCreateTree(pn-right, i+(m-j)+1, m+1, len-1-(m-j); void printTree(PNode pn) if(pn=NULL) printf(%c,pn-v); if(pn-left!=NULL|pn-right!=NULL) printf(); printTree(pn-left); if(pn-right!=NULL) printf(,); printTree(pn-right); printf(); int main() PNode root; PreMidCreateTree(root, 0, 0, strlen(mid); printTree(root); 四、 程序清单#includestdlib.h#includestdio.h#includemalloc.h#include #include typedef char DataType; typedef struct Node DataType data;struct Node *LChild;struct Node *RChild;BiTNode,*BiTree; /*声明二叉树的二叉链表结点的结构*/void CreateBiTree(BiTree *bt) /*利用“扩展先序遍历序列”创建二叉链表*/char ch;ch=getchar();if(ch=.) *bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode); /*申请空间*/(*bt)-data=ch;CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild);return;/*采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左右子树的叶子结点数之和*/int leaf(BiTree bt)int LeafCount;if(bt=NULL)LeafCount =0;else if(bt-LChild=NULL)&(bt-RChild=NULL)LeafCount=1;elseLeafCount=leaf(bt-LChild)+leaf(bt-RChild);return LeafCount;void PrintTree(BiTree bt,int nLayer) /*按竖向树状打印二叉树*/if(bt=NULL)return;PrintTree(bt-RChild,nLayer+1);for(int i=0;idata);PrintTree(bt-LChild,nLayer+1);void main() /*调用主函数连接其他函数，构成完整的程序*/ BiTree bt; printf(请输入二叉树的序列: n); CreateBiTree(&bt); printf(该二叉树的叶子结点个数为: %dn,leaf(bt); printf(该二叉树的形状为：n); int nLayer=0; PrintTree(bt,nLayer);五、 实验结果与分析六、 实验心得在这