二叉树叶子结点从左到右链成单链表

《二叉树叶子结点从左到右链成单链表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告题目：实现二叉树的叶子结点按从左到右的顺序连成一个单链表采用的方法：二叉树按lchild-rchild的方式存储，链接时用叶子结点的rchild域存放指针。班级：计算机091班姓名：李盛闻指导教师：董跃华、井福荣成绩：__________________________信息工程学院-21-2011年6月13日目录摘要(题目)31.引言32.需求分析43.概要设计44.详细设计65.测试结果116.调试分析117.设计体会128.结束语13参考文献13附录13-21-摘要(题目)：实现二叉树的叶子结点按从左到

2、右的顺序连成一个单链表。二叉树按lchild-rchild的方式存储，链接时用叶子结点的rchild域存放指针。假设二叉树中结点的元素均为单个字符。首先输入一个根结点，若输入的是“#”字符，表示该二叉树为空树，即root=NULL；否则向系统申请结点空间，由root指向该结点，把输入的字符赋给root->data，之后，依次递归地建立它的左子树root->lchild和右子树root->rchild。本题目的思路是，输入数据、遍历二叉树、判断是否为叶子结点、创建由叶子结点组成的单链表、输出。1.引言：-21-通过本门课程的学习

3、，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在学校和离校后的工作和学习，也有重要意义。数据结构是电子信息科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好了数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题问能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部的数据结构来表示，然后设计一个解此数学模型的算法

4、，在进行编程调试，最后活的问题的解答。基于此原因，现在我们开设数据结构课程设计。针对数据结构课程的特点，着眼于培养我们的实践能力。2.需求分析：本题目要求实现二叉树的叶子结点按从左到右的顺序连成一个单链表。首先将数据i键盘输入，这时要对输入的数据进行一个判断，不妨设计如果输入数据不是“0”,则将数据插入到排序二叉树中，如果输入数据是“0”，则遍历二叉树。然后判断结点是否为叶子结点，如果不是叶子结点，则返回数值；如果是叶子结点，则将叶子结点依次接到头结点后。最后输出由二叉树叶子结点创建的链表。程序中，输入的数据要为整型，如果输入

5、整型以外的数据类型，程序将进入循环。3.概要设计：对题目进行算法模块描述，流程图如下：-21-将叶子结点依次接到头结点后是否为叶子结点遍历二叉树Yi=0将数据插入到排序二叉树输入数据i开始NNY输出由二叉树叶子结点创建的单链表结束图1-1-21-4.详细设计：定义结构体：typedefstructxiaofei{intdata;structxiaofei*lchild,*rchild;//定义结点的左右指针}test;xiaofei*root,*p,*q[max],*head,*first;intsum=0;intm=size

6、of(test);//生成二叉排序树voidinsert_data(intx){xiaofei*p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root){-21-root=s;}p=root;接入二叉排序树的适当位置的算法：while(p){q=p;if(p->data==x){printf("dataalreadyexist!");return;}elseif(xdata)p=p->lchild;elsep=p->rc

7、hild;}if(xdata)q->lchild=s;-21-elseq->rchild=s;}将二叉树叶子结点利用指针rchild生成单链表的算法：voidPreOrderTraverse(xiaofei*root)//先序遍历二叉树{xiaofei*n;n=root;if(!n)return;if(n->lchild==NULL&&n->rchild==NULL){//判断叶子结点并利用指针rchild生成单链表head->rchild=n;head=n;return;}if(n->lchild)PreOrderT

8、raverse(n->lchild);if(n->rchild)PreOrderTraverse(n->rchild);return;}-21-查找二叉树第最左边第一个叶子结点的算法：xiaofeiFinFLea(xiaofei*root){xiaofei*n;n=root;