带父亲结点报告.doc

课程设计报告课程设计名称:数据结构课程设计课程设计题目:带父亲结点的平衡二叉树的建立院(系):计算机学院专  业:计算机科学与技术班  级:94010102学  号:2009040101057姓  名:杨焕发指导教师:郑志勇目  录第1章 概要设计      2第2章  详细设计………………………………………………………………………………..………………………………………………………………………….  ………………………………………………………………………………………………………………………………………………….………………………………………………………………………….…………………………………………………………………….………………………………………………………………………….…………………………………………………………………...………………………………………………………………...………………………………………………………………………...  13第3章 系统实现      14参考文献  15附录(关键部分程序清单)…………………………………………………………16第1章 :从键盘上输入以整数序列,建立一棵平衡二叉树。要求:(1)要能过形象方便的观察书的结构(2)要能够形象的演示树的平衡过程(3)课程设计报告必须符合课程设计报告规范(4)提交合格的课程设计报告后,经指导教师测试程序,,要用二叉链表的存储结构。首先建立一棵二叉排序树。其树应该具备以下几个性质:(1)若它的左子树不空,则左子树上所有的结点的值均小于它的根结点的值。(2)若它的右子树不空,则右子树上所有的结点的值均大于它的根结点的值。(3)它的左右子树也分别为二叉排序树。平衡二叉树的建立以插入结点的方式实现,分为四种情况:LL型,RR型,RL型,LR型。这里树结点的产生分两种情况,一种是键盘输入,一种是电脑自动产生随机数。当插入一个结点的时候,如果不平衡,就是某个相对根结点的平衡因子绝对值超过1时,进行相应的平衡调整。每插入一个节点要用层次遍历来检验平衡二叉树的建立是否正确第2章 :主程序模块:调用构造树的函数,打印平衡二叉树并且调用遍历此树。构造树模块:构造一棵二叉排序树。处理不平衡模块:如果建树中出现不平衡对其进行处理。判断类型模块:此模块分为四钟情况:LL型,RR型,RL型,LR型。节点匹配模块:在这判断一下q是p的是结点。调整模块:对树进行总调整,在此模块调用另外两个函数,调整树的位置和调整树的数据函数。定位模块:用于定位n的位置。深度模块:用于求树的深度。遍历模块:层次遍历此树。,控制菜单操作,通过主函数模块分别调用各个模块,实现各项功能,。开始getch();,然后调用构造二叉排序树的函数,接着调用层次遍历树的函数,最后在黑屏上输出要生成的平衡二叉树。。构造一颗二叉排序树。++定义变量i初始化赋值0iN打印输入的数据个数Yi++初始化一个队列ii==0N给pqT分配空间结点Y给p分配空间结点Np!=NULLG指针指向P的指针D[i]>p->datap=p->left;p=p->right;D[i]>G->dataNq->parent=G;q->parent=G;YB(T);i++; 字符匹配模块流成图构造一颗二叉排序树,首先从键盘上输入要输入的数据个数,然后调用队的初始化,如果i=0就只有跟节点。如果i不等于0给新的结点分配存储空间,并让P指针指向T,如果P不为空,判断如果待插入的数据小于P指向的数据,则为P的左孩子,反之则为右孩子。以此继续,然后在调用调整函数。,[i].parent=c[i].left=c[i].right=-1;B1(T);i++i<100i=0inti;i++i<100对i进行初始化赋值0定义整形i变量N对每个结点进行初始化Y确定每个父亲节点和左右孩子节点确定每个孩子