《二叉树的递归遍历和叶子数,深度.doc》由会员分享，可在线阅读，更多相关《二叉树的递归遍历和叶子数,深度.doc（5页珍藏版）》请在三一办公上搜索。
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#G#F#先序遍历的顺序是：ABCDEGF中序遍历的顺序是：CBEGDFA后序遍历的顺序是：CGEFDBA此二叉树的叶子数为：3此二叉树的深度为：5Press any key to conntinue
