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

1、中原工学院软件学院实验报告实验项目名称 二叉树的基本操作实现及其应用课程名称数据结构学生学生学号所在班级学科专业任课教师完成日期一、实验目的1熟悉二叉树结点的结构和对二叉树的基本操作。 2掌握对二叉树每一种操作的具体实现。3学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4.会用二叉树解决简单的实际问题。二、实验容题目一设计程序实现二叉树结点的类型定义和对二叉树的基本操作 该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数 1 按先序次序建立一个二叉树，2按 (A:先序B:中序C:后序)遍历输岀二叉树的所有结点以上比做，以下选做求二叉树中所有结点数求二叉树的深度三、实验

2、步骤、数据结构与核心算法的设计描述typedef struct nodechar 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)求 深度(二)、函数调用及主函数设计程序调试及运行结果分析勒序遍历：de ba*后序谨历， 二賈树深度

3、科严J程一尺勒序遍历：de ba*后序谨历， 二賈树深度科严J程一尺PJI刑八P点序列用三格锂代；表王卩点xabed二冥树创建成功T数 点 一 度 历历無 逅黑的 先中后t结九序遍历；二叉树节点数N如结果所示，该程序实现了先序创建二叉树，先序遍历，中序遍 历，后序遍历及求深度，求节点数等功能。（四）实验总结 该实验主要是对二叉树的基本操作进行了训练。在实验的过程中，我 熟悉了二叉树的构造方法，以及二叉树的一些操作，通过此次实验， 我对二叉树的基本构造方法以及怎么使用递归的方法有了更深的理 解。四、主要算法流程图及程序清单1、主要算法流程图+*先序遍历 PreOrd&rQ中序遍历 InOrder

4、Q后序遍历 PostOrderQ12、程序清单#include#include#include typedef struct nodechar 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();

5、/构造左子树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);pr

6、intf(%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);elsereturn

7、0;/主函数 void main()BinTree root;int i,depth，NodeNum;printf(创建二叉树；输入节点序列(用空格键代表空节点):n); root=CreatBinTree();printf（二叉树创建成功!nn）;创建二叉树，返回根结点printf（tt*选择操作*n）;printf（tt*选择操作*n）;printf（tt1:先序遍历n）;printf（tt2:中序遍历n）;printf（tt3:后序遍历n）;printf（tt4:求树的深度，节点数n）; printf（ttO:结束n）;printf（tt*汝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