二叉树的递归遍历和叶子数,深度

1、数据结构实验报告四实验内容： 建一个二叉树并对其进行遍历，并求出该树的叶子数和深度 学号：20105101256 姓名：肖丽芳 一、上机实验的问题和要求（需求分析）： 题目 1从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。2 求该二叉数的深度、并统计叶子结点的个数。二、程序设计的基本思想，原理和算法描述： 根据先序遍历的性质，先建立头结点，再建立左右子树，利用递归算法，先序建立二叉树。对树进行遍历时，根据先序、中序、后序不同的算法，将输出不同的序列。求树的叶子数和深度是要判断树是否为空，然后依据算

2、法看左右孩子。三、调试和运行程序过程中产生的问题及采取的措施：写主函数时注意不要抄写错误，尤其是大小写，注意函数的调用四、源程序及注释 源程序 程序名： 二叉树#include#include#include#define error 0#define ok 1#define overflow -1#define null 0typedef int status;typedef char telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;/左右孩子指针bitnode,*bitree;/二叉

3、树的二叉链表存储表示bitree creatbitree(bitree t)/按先序次序输入二叉树中结点的值（一个字符），空格字符表示空数/构造二叉连表表示的二叉树tchar ch;scanf(%c,&ch);if(ch=#) t=null;/用#表示空指针elset=(bitree)malloc(sizeof(bitnode);t-data=ch;/生成根结店t-lchild=creatbitree(t-lchild);/生成左子树t-rchild=creatbitree(t-rchild);/生成右子树return t;/createbitreevoid preorder(bitree t

4、) 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);/后序遍历左子树postor

5、der(t-rchild);/后序遍历右子树 printf(%c,t-data);/访问根结点/后序遍历二叉树int leaf_count(bitree t)/求二叉树中叶子结点的数目if(!t) return 0;/空树没有叶子else if(!t-lchild &!t-rchild ) return 1;/叶子节点else return leaf_count(t-lchild)+leaf_count(t-rchild);/左子树的叶子数加上右子树的叶子数int height(bitree t)int m,n;if(t=null) return 0;/空数深度为0else m=height(

6、t-rchild);/m为右孩子的深度n=height(t-lchild);/n为左孩子的深度if(mn)return(m+1);/如果右孩子的深度大于左孩子的深度则右孩子m+1else return(n+1);/否则左孩子n+1void main()bitree t=null; t=creatbitree(t);int depth;int leaf; printf(先序遍历的顺序是); preorder(t);printf(n); printf(中序遍历的顺序是); inorder(t);printf(n);printf(后序遍历的顺序是); postorder(t);printf(n);leaf=leaf_count(t);printf(此二叉树的叶子数为：%dn,leaf);depth=height(t);printf(此二叉树的深度为：%dn,depth);五、运行结果 abc#de