重庆大学城市科技学院
课程设计报告
    二叉树的基本操作  
学    院：            电气信息学院             
专    业：              软件工程               
年    级：                2011                 
姓    名：                                     
班    级：                01                 
学    号：              ********               
成    绩：                                     
完成时间：            2013年1月2日           
          指导教师：               
一、需求分析
二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。
二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。演示程序以用户与计算机对话的方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入相应动作的序号和相应的输入数据。
1.1课程设计任务及要求
(1)按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树t；
(2)对二叉树t作先序、中序、后序遍历的递归算法,输出结果；
(3)计算二叉树t的深度,输出结果；
(4)计算二叉树t的叶子结点个数
1.2课程设计思想
本次课程设计中，用到的主要知识就是递归思想，着重体会递归的思想。建立二叉树采用先序次序插入的方式。对二叉树进行遍历时采用递归函数的方式。求二叉树的深度及叶子结点个数均采用递归方式。
二、概要设计
2.1对程序中定义的核心数据结构及对其说明：
typedef struct BiTNode
{
      char data;
      struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
在开头定义了二叉树的链式存储结构，此处采用了每个结点中设置三个域， 即值域，左指针域和右指针域。
2.2 程序模块及其功能：
本程序分为：7大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、后序遍历、求叶子结点的个数计算、中序遍历、后序遍历、深度、主函数。
1、二叉树的建立链式存储结构；首先typedef struct BiTNode：定义二叉树的链式存储结
构，此处采用了每个结点中设置三个域，data：即值域，*lchild：左指针域和rchild：右指针域。
2、二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树。
3、二叉树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树。
4、二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点。
5、求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0。否则，就先别求出左右子树的深度并进行比较，取较大的+1就为二叉树的深度。
6、二叉树的求叶子结点的个数计算；先分别求得左右子树中各叶子结点个数，再计算出两者之和即为二叉树的叶子结点数。
先序中序后序遍历二叉树
7、主函数。主函数中分别调用各函数。
三、详细设计
3.1存储结构的建立由递归函数实现
具体函数为：
typedef struct bitnode
{
      telemtype data;
      struct bitnode *lchild,*rchild;
}bitnode ,*bitree;
bitree createbitree(bitree t)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#') t=NULL;
    else
    {
        if(!(t=(bitnode *)malloc(sizeof(bitnode)))) exit(overflow);
        t->data=ch;
        t->lchild=createbitree(t->lchild);
        t->rchild=createbitree(t->rchild);
   
    }
    return t;
}
在创建的二叉树中，左右孩子都为字符型。
char的作用是输入n个任意的字符，而且在输入n个字符后，必须输入n+1个'0'，才能得到本程序所有能够实现的功能。t=Null是将二叉树置空。
if(!(t=(bitnode *)malloc(sizeof(bitnode))))，采用动态申请新结点的方式，不仅实现起来方便，而且还节省大量的存储空间。
t->data=ch;值域
t->lchild=createbitree(t->lchild);
t->rchild=createbitree(t->rchild);
将二叉树中的每一个结点设置为：值域，左指针域，右指针。
这一小段程序实现了二叉树的置空，二叉树的建立，二叉树的存储。
3.2前序遍历：先访问根结点，再访问左子树，最后访问右子树。
具体函数为：
void preordertraverse(bitree t)
{
    if(t)
    {
        printf("%c",t->data);
        preordertraverse(t->lchild);
        preordertraverse(t->rchild);
    }
}
3.3中序遍历：先访问左子树，再访问根结点，最后访问右子树。
具体函数为：
void inordertraverse(bitree t)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。