重 庆 大 学
学 生 实 验 报 告
实验课程名称 数据结构
开课实验室 LD104
学 院 数学与统计学院 年级 2013级 专业班 应用数学2班
学 生 姓 名 童钞 学 号 201319
开 课 时 间 2015 至 2016 学年第 一 学期
总 成 绩 教师签名
课程 数据结构 名称 指导 何光辉 教师 实验项目 名 称 成 绩 二叉树在C语言中的实验证 实验项目类型 演示 综合 设计 其他 现 √ 一 实验项目名称：二叉树在C语言中的实现 二 实验目的： （1）熟悉用C++语言实现二叉树的数据结构 （2）设计出相应的算法，编制相应的函数程序 三 实验原理： 算法程序： #include #include #include typedef int ElemType; //数据类型 //定义二叉树结构，与单链表相似，多了一个右孩子结点 typedef struct BiTNode{ ElemType data; //数据域 struct BiTNode *lChild, *rChlid; //左右子树域 }BiTNode, *BiTree; //先序创建二叉树 int CreateBiTree(BiTree *T) { ElemType ch; ElemType temp; scanf(\"%demp = getchar(); if (ch == -1) *T = NULL; else { *T = (BiTree)malloc(sizeof(BiTNode)); if (!(*T)) exit(-1); (*T)->data = ch; printf(\"输入%d的左子节点：\CreateBiTree(&(*T)->lChild); printf(\"输入%d的右子节点：\CreateBiTree(&(*T)->rChlid); } return 1; } //先序遍历二叉树 void TraverseBiTree(BiTree T) { if (T == NULL) return ; printf(\"%d \TraverseBiTree(T->lChild); TraverseBiTree(T->rChlid); } //中序遍历二叉树 void InOrderBiTree(BiTree T) { if (T == NULL) return ; InOrderBiTree(T->lChild); printf(\"%d \InOrderBiTree(T->rChlid); } //后序遍历二叉树 void PostOrderBiTree(BiTree T) { if (T == NULL) return ; PostOrderBiTree(T->lChild); PostOrderBiTree(T->rChlid); printf(\"%d \ } //二叉树的深度 int TreeDeep(BiTree T) { int deep = 0; if(T) { int leftdeep = TreeDeep(T->lChild); int rightdeep = TreeDeep(T->rChlid); deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1; } return deep; } //求二叉树叶子结点个数 int Leafcount(BiTree T,int &num) { if(T) { if(T->lChild ==NULL &&T->rChlid==NULL) num++; Leafcount(T->lChild,num); Leafcount(T->rChlid,num); } return num; } //主函数 int main(void) { BiTree T; BiTree *p = (BiTree*)malloc(sizeof(BiTree)); int deepth,num=0 ; printf(\"请输入第一个结点的值,-1表示没有叶结点:\\n\"); CreateBiTree(&T); printf(\"先序遍历二叉树:\\n\"); TraverseBiTree(T); printf(\"\\n\"); printf(\"中序遍历二叉树:\\n\"); InOrderBiTree(T); printf(\"\\n\"); printf(\"后序遍历二叉树:\\n\"); PostOrderBiTree(T); printf(\"\\n\"); deepth=TreeDeep(T); printf(\"树的深度为:%d\printf(\"\\n\"); Leafcount(T,num); printf(\"树的叶子结点个数为:%d\printf(\"\\n\"); return 0; } 三 实验内容与步骤 四 计算实例、数据、结果、分析 五 实验中遇到的问题及解决办法 六 实验结论 教师签名 年 月 日
