1、课程设计报告题目： 平衡二叉树匹配 班级 信计 1512 姓名 朱伟光 蔡闽龙 李建峰 张衍炳 陈家彤 学号 201521143045 201521143046 201521143047 201521143048 201521143049 完成日期 2017.01.19 1、需求分析1.根据输入的任意个不同的数字序列，判断是否和第一个序列模板为同一棵平衡二叉树。2.输入的第一行数据的第一个数 n（1data)p = T;return TRUE; /查找成功else if (key data)return SerchBST(T-lchild, key, T, p); /在左子树中继续查找else
2、return SerchBST(T-rchild, key, T, p); /在右子树中继续查找5、平衡二叉树的遍历算法：Status PreOrderTraverse(BiTree T) /按先序次序输出平衡二叉树中结点的值 if (!T) return ERROR;elseSFXTt = T-data; /访问根结点t+;PreOrderTraverse(T-lchild); /访问左子树PreOrderTraverse(T-rchild); /访问右子树return OK;6、主函数算法：#define ERROR 0#define OK 1#define FALSE 0#define
3、TRUE 1typedef 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 n m; /从文本中读入需要判断的个数 n 及序列的长度key = new intm; /关键字存储数组int num = (n + 1)*m;SFXT = n
4、ew intnum; /序列的存储数组for (i = 0; i keyj; /从文本中读入关键字BiTree p,s;/开始插入数据/当平衡二叉树 T 中不存在关键字等于 e.key 的数/据元素时，插入 e 并返回 /TURE，否则返回 FALSEif (!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
5、 为左孩子elsep-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.不好的地方在于本程序适用于数据量较小的情况，若数据量太大，可能导致内存占用太多。测试结果：第一组：输入数据：2 65 6 7 4 3 25 4 3 2 6 7输出数据：NO！
