二叉树遍历及基本属性算法.docVIP

学 生 实 验 报 告 学 院： 软件与通信工程学院 课程名称： 数据结构 专业班级： 软件105班 姓 名： 杨先刚 学 号： 0104028  学生实验报告（4） 学生姓名 杨先刚 学号 0104028 同组人：无 实验项目 二叉树 ■必修 □选修 □演示性实 ■验验证性实验 □操作性实验 □综合性实验 实验地点 H202 实验仪器台号 指导教师 蒋娜 实验日期及节次 一、实验综述 1、实验目的及要求 实验4：树和二叉树 实验要求： 1、创建一棵二叉树，以二叉链表作存储结构，实现先根遍历算法 2、创建一棵二叉树，实现先根遍历算法、中根遍历算法、后根遍历算法 3、求给定二叉树的叶结点数、结点数、高度 二、实验过程（实验步骤、记录、数据、分析） #includeiostream using namespace std; typedef struct BiTNode // 结点结构 { char data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; void visit(char e) //输出函数 { coute; // 以整型格式输出 } int CreateBiTree(BiTree T) { char ch; ch=getchar(); if (ch== ) T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(0); T-data = ch; // 生成根结点 CreateBiTree(T-lchild); // 构造左子树 CreateBiTree(T-rchild); // 构造右子树 } return 1; } // CreateBiTree void Preorder(BiTree T,void( *visit)(char e)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 if (T) { visit(T-data); // 访问结点 Preorder(T-lchild, visit); // 遍历左子树 Preorder(T-rchild, visit);// 遍历右子树 } } void InOrderTraverse(BiTree T,void(*Visit)(char e)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { InOrderTraverse(T-lchild,Visit); // 中序遍历左子树 Visit(T-data); // 访问根结点 InOrderTraverse(T-rchild,Visit); // 中序遍历右子树 } } void PostOrderTraverse(BiTree T,void(*Visit)(char e)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) // T不空 { PostOrderTraverse(T-lchild,Visit); // 后序遍历左子树 PostOrderTraverse(T-rchild,Visit); // 后序遍历右子树 Visit(T-data); // 后访问根结点 } } void CountLeaf (BiTree T, int count) { if ( T ) { if ((!T-lchild) (!T-rchild))