文档介绍：二叉树基本操作实验报告二叉树基本操作实验报告实验名称二叉树基本操作实验目的 ; ; ; ; 。实验内容编制一个演示二叉树创建、遍历、计算等操作的程序。问题描述用数据结构相关知识,实现二叉树的定义和操作。该程序包括二叉树结构类型以及对二叉树操作的具体的函数定义(包括:初始化二叉树、清空二叉树、检查二叉树是否为空、遍历二叉树(先序、后序、中序、层次) 、求二叉树的深度、求二叉树所有节点数)。问题分析该实验是基于 C语言和数据结构知识基础的对二叉树的基本操作的检验,无需设计复杂的算法,程序语句也相对简单。因此,我直接按要求定义了对二叉树操作的具体函数, 并于主函数中实现对应的功能调用,其中,功能选择靠 switch 语句实现。实验步骤 1. 需求分析本演示程序用 VC++ 编写,完成二叉树的生成、遍历、计算等基本操作。 1输入的形式和输入值的范围:以字符(其中‘#’表示虚节点)的形式输入, 以创建二叉树;在输入二叉树节点前,必须先确定该序列能正确创建二叉树。②输出的形式:在所有三种操作中都显示操作是否正确以及操作后二叉树的内容。③程序所能达到的功能:完成二叉树的生成、遍历(包括先序、后序、中序、层次四种方式)、计算等基本操作。④测试数据:创建操作中依次输入 a,b,d,#,g,#,#,#,c,e,#,#,f,#,# 生成一个二叉树。 2 .概要设计 1)为了实现上述程序功能,需要定义二叉树的抽象数据类型: ADT BitTree {数据对象:由一个根节点和两个互不相交的左右子树构成数据关系:结点具有相同的数据类型及层次结构基本操作: Void BinTreeInit( BitTree *T)初始条件:无操作结果:初始化一棵二叉树 Void BinTree Creat ( BitTree *T)初始条件:二叉树 T已存在操作结果:按先序次序创建一棵二叉树 2)本程序包含 7个函数: ①主函数 main() ②初始化二叉树函数 BinTreeInit() ③建立一棵二叉树函数 BinTree Creat ()④先序遍历函数 PreOrderTraverse() ⑤中序遍历函数 InOrderTraverse() ⑥后序遍历函数 PostOrderTraverse() ⑦层次遍历函数 LevelOrderTraverse() ⑧求二叉树深度函数 Countlevel() ⑨检验空树函数 BinTreeEmpty() ⑩求节点数函数 Countnode() 函数说明#include<> #include<> typedef char Datatype; typedef struct NodeType { Datatype data; struct NodeType *lchild; struct NodeType *rchild; }BiTNode; typedef BiTNode * BinTree; // 初始化二叉树。即把树指针置空 void BinTreeInit(BiTNode *T) { // BiTNode *T; T=(BiTNode *)malloc(sizeof(BiTNode)); T=NULL; } // 二叉树的建立 BinTree CreateBiTNode() { BiTNode *T; Datatype ch; ch=getchar(); if(ch=='#') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("Error!"); T->data=ch; T->lchild=CreateBiTNode(); T->rchild=CreateBiTNode(); } return T;} // 先序遍历 void PreOrderTraverse(BiTNode *p){ if(p!=NULL){ printf("%c ",p->data); PreOrderTraverse(p->lchild); PreOrderTraverse(p->rchild); }} // 中序遍历 void InOrderTraverse(BiTNode *p){ if(p!=NULL){ InOrderTraverse (p->lchild); printf("%c ",p->data); InOrderTraverse (p->rchild); }} // 后序遍历 void