《平衡二叉树匹配课程设计》由会员分享,可在线阅读,更多相关《平衡二叉树匹配课程设计(6页珍藏版)》请在金锄头文库上搜索。
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;else SFXTt = 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 = ne
4、w 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!