二叉树的基本操作实现及其应用.doc

_ 中原工学院软件学院实验报告实验项目名称二叉树的基本操作实现及其应用课程名称数据结构学生姓名 学生学号 所在班级学科专业 任课教师完成日期 一、实验目的1熟悉二叉树结点的结构和对二叉树的基本操作。2掌握对二叉树每一种操作的具体实现。3学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4.会用二叉树解决简单的实际问题。二、实验内容 题目一 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。1 按先序次序建立一个二叉树 ，2按（A:先序 B:中序 C:后序 ）遍历输出二叉树的所有结点 以上比做，以下选做3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤、数据结构与核心算法的设计描述typedef struct node char data; struct node *lchild,*rchild;BinTNode, *BinTree; /定义二叉树的指针BinTree CreatBinTree(void)/先序遍历算法创建二叉树void Preorder(BinTree T)先序遍历void Inorder(BinTree T)中序遍历void Postorder(BinTree T)后序遍历int TreeDepth(BinTree T)求深度、函数调用及主函数设计 程序调试及运行结果分析如结果所示，该程序实现了先序创建二叉树，先序遍历，中序遍历，后序遍历及求深度，求节点数等功能。（4） 实验总结 该实验主要是对二叉树的基本操作进行了训练。在实验的过程中，我熟悉了二叉树的构造方法，以及二叉树的一些操作，通过此次实验，我对二叉树的基本构造方法以及怎么使用递归的方法有了更深的理解。四、主要算法流程图及程序清单 1、主要算法流程图 2、程序清单 #include#include#includetypedef struct node char data; struct node *lchild,*rchild;BinTNode, *BinTree; /定义二叉树的指针BinTree CreatBinTree(void)/先序遍历算法创建二叉树 BinTree T; char ch; if(ch=getchar()= ) return(NULL); elseT=(BinTNode *)malloc(sizeof(BinTNode); T-data=ch;T-lchild=CreatBinTree(); /构造左子树T-rchild=CreatBinTree(); /构造右子树return(T);/先序遍历void Preorder(BinTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); /中序遍历void Inorder(BinTree T) if(T)Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /后序遍历void Postorder(BinTree T)if(T)Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); int TreeDepth(BinTree T) int hl,hr,max; if(T) hl=TreeDepth(T-lchild); hr=TreeDepth(T-rchild); max=hlhr? hl:hr; NodeNum=NodeNum+1; return(max+1); else return(0);Int TreeNode(BinTree T)int NodeNum=0;if(T) TreeDepth(T-lchild); TreeDepth(T-rchild); NodeNum=NodeNum+1; return(NodeNum);else return 0;/主函数void main() BinTree root; int i,depth，NodeNum; printf(创建二叉树； 输入节点序列(用空格键代表空节点):n); root=CreatBinTree(); printf(二叉树创建成功!nn); /创建二叉树，返回根结点 printf(tt* 选择操作 *n); printf(tt1: 先序遍历n); printf(tt2: 中序遍历n); printf(tt3: 后序遍历n); printf(tt4: 求树的深度，节点数n); printf(tt0: 结束n); printf(tt*n);while(scanf(%d,&i)/输入菜单序号（0-4） switch (i) case 1: printf(先序遍历: n); Preorder(root); break; case 2: printf(中序遍历: n); Inorder(root); break; case 3: printf(后序遍历:n ); Postorder(root); break; case 4: depth=TreeDepth(root); /求