平衡二叉树匹配课程设计

课程设计报告题目： 平衡二叉树匹配 班级 信计1512 姓名 朱伟光 蔡闽龙 李建峰 张衍炳 陈家彤 学号 201521143045 201521143046 201521143047 201521143048 201521143049 完成日期 2017.01.19 1、 需求分析 1.根据输入的任意个不同的数字序列，判断是否和第一个序列模板为同一棵平衡二叉树。 2.输入的第一行数据的第一个数n（1=ndata) p = T;return TRUE; /查找成功 else if (key data) return SerchBST(T-lchild, key, T, p); /在左子树中继续查找 elsereturn SerchBST(T-rchild, key, T, p); /在右子树中继续查找5、 平衡二叉树的遍历算法： Status PreOrderTraverse(BiTree T) /按先序次序输出平衡二叉树中结点的值 if (!T) return ERROR; else SFXTt = T-data; /访问根结点 t+; PreOrderTraverse(T-lchild); /访问左子树 PreOrderTraverse(T-rchild); /访问右子树 return OK; 6、主函数算法： #define ERROR 0 #define OK 1 #defineFALSE 0 #define TRUE 1 typedef int Status; int *SFXT,t=0; int main(void) int i, j, n, m,*key; /n，m分别表示n个判断的序列及每个序列的长度，i,j为中间量 BiTree T; T = (BiTree)malloc(sizeof(BiTNode); ifstream fin(input.txt,ios:in); /打开input.txt文件进行读取if(!fin)cout cant open file n m; /从文本中读入需要判断的个数n及序列的长度 key = new intm; /关键字存储数组 int num = (n + 1)*m; SFXT = new intnum; /序列的存储数组 for (i = 0; i = n; i+) T = NULL; for (j = 0; j keyj; /从文本中读入关键字 BiTree p,s; /开始插入数据 /当平衡二叉树T中不存在关键字等于e.key的数/据元素时，插入e并返回 /TURE，否则返回FALSE if (!SerchBST(T, e, NULL, p) /查找不成功 s = (BiTree)malloc(sizeof(BiTNode); s-data = e; s-lchild = s-rchild = NULL; if (!p) T = s; /被插结点*s为新的根结点 else if (e data) p-lchild = s; /被插结点*s为左孩子 else p-rchild = s; /被插结点*s为右孩子 /树中已有关键字相同的结点，不再插入 PreOrderTraverse(T); /按先序次序输出平衡二叉树中结点的值 /判断序列是否与模板序列一样 for (int i = 1; i = n; i+) int count = 0; /定义一个计数的变量for (int j = 0; j m; j+)if (SFXTj = SFXTj + i*m) /判断序列是否相同count+; /相同，则计数器加一if (count = m)fout YES endl; /若计数器的值等于序列长度，则输出“YES”elsefout NO endl; /否则，输出“NO” return 0; /结束主函数 4、 测试结果与分析调试分析： 1.调试运行时出现类型转换：无法从void*转换成为BiTree的问题。 2.在编写程序时没有注意到存在越界，导致调试一度出现中断。 3.本程序的关键在于平衡二叉树的插入算法。 4.不好