实验报告(二叉树).doc

仲恺农业工程学院实验报告纸 信息科学与技术（院、系） 计算机 专业 144 班 数据结构与算法 课 学号201420224417 姓名刘智龙 实验日期 2015.12.8 教师评定 一、实验目的 1、掌握二叉树的特点，以及的二叉链表存储结构。 熟练掌握二叉树的各种操作，如建立、遍历、查找和输出。 利用已经掌握的知识进行实际应用。 1) 硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP。 2) 软件：visual c++6.0。 三、实验题目和实验内容 实验题目：二叉树操作及应用 四、实验项目的程序结构（包含的各个文件中的函数调用功能描述、程序中的函数调用关系图）(可写可不写) 五、实验数据和实验结果（程序运行结果的截图） 实验7.1结果： 实验7.2结果： 实验7.3结果： 六、附录（程序代码） 实验7.1源代码： #include stdio.h #include malloc.h #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; //数据元素 struct node *lchild; //指向左孩子 struct node *rchild; //指向右孩子 } BTNode; void CreateBTNode(BTNode *b,char *str) //由str串创建二叉链 { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; //建立的二叉树初始时为空 ch=str[j]; while (ch!=\0) //str未扫描完时循环 { switch(ch) { case (:top++;St[top]=p;k=1; break; //为左节点 case ):top--;break; case ,:k=2; break; //为右节点 default:p=(BTNode *)malloc(sizeof(BTNode)); p-data=ch;p-lchild=p-rchild=NULL; if (b==NULL) //p指向二叉树的根节点 b=p; else //已建立二叉树根节点 { switch(k) { case 1:St[top]-lchild=p;break; case 2:St[top]-rchild=p;break; } } } j++; ch=str[j]; } } BTNode *FindNode(BTNode *b,ElemType x) //返回data域为x的节点指针 { BTNode *p; if (b==NULL) return NULL; else if (b-data==x) return b; else { p=FindNode(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); } } BTNode *LchildNode(BTNode *p) //返回*p节点的左孩子节点指针 { return p-lchild; } BTNode *RchildNode(BTNode *p) //返回*p节点的右孩子节点指针 { return p-rchild; } int BTNodeDepth(BTNode *b) //求二叉树b的深度 { int lchilddep,rchilddep; if (b==NULL) return(0); //空树的高度为0 else { lchilddep=BTNodeDepth(b-lchild); //求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild); //求右子树的高度为rchilddep return (lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); } } void DispBTNode(BTNode *b