《数据结构课程设计-线索二叉树的应用》由会员分享，可在线阅读，更多相关《数据结构课程设计-线索二叉树的应用（24页珍藏版）》请在金锄头文库上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构课程设计-线索二叉树的应用数据结构课程设计-线索二叉树的应用安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 线索二叉树的应用 专业 计算机科学与技术 班级 10计本2班 学号10012084 姓名 王春雷 联系方式 15005656879指导教师江家宝 蔡敏20 11 年 12 月 25 日-目 录1、数据结构课程设计任务书11.1
2、、题目11.2、要求12、总体设计12.1、数据输入输出12.2、设计算法测试用例12.2、流程图23、详细设计23.1、程序中所采用的数据结构及存储结构的说明43.2、算法的设计思想54、调试与测试：64.1、调试方法与步骤：64.2、测试结果的分析与讨论：66、源程序清单和执行结果97、C程序设计总结178、致谢179、参考文献181、数据结构课程设计任务书1.1、题目线索二叉树的应用1.2、要求实现线索树建立、插入、删除、恢复线索的实现。2、总体设计2.1、数据输入输出：原始数据要求输入二叉树的7个结点：1234567，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索
3、化。对其进行插入：在7结点处插入结点8；删除：删除结点8;恢复线索等功能。进行二叉树的初始化，依次输入，以*结束：1234567*线索二叉树的应用*1、进行二叉树线索化2、进行插入操作3、删除4、中序输出5、线索输出0、退出请选择：1已经实现二叉树的线索化，可选择5查看线索。2.2、设计算法测试用例：（1）输入结点:1234567;(2)对输入的二叉树进行线索化；（3）查看二叉树的中序线索输出：4-2-5-1-6-3-7；（4）在7结点处插入结点8，此时完成线索化恢复，查看二叉树的中序线索输出：4-2-5-1-6-3-8-7;(5)删除结点8，此时完成线索化恢复，发现结点8，ltag=1,rt
4、ag=1,查看二叉树的中序线索输出：4-2-5-1-6-3-7;(6)继续删除结点r，发现无该结点，则输入错误。2.3、流程图开始定义二叉树T=CreatTree( )1=i输入i!=0输入选择菜单输入ii=1preThred(T)i=2Insert(T)i=3DeleteNode(T)i=4Inorder(T)退出3、详细设计（1）、主函数void main()Bithptr *T;int i;/system(color 1a);T=CreatTree();printf(n);i=1;while(i)printf(t1 进行二叉树线索化n);printf(t2 进行插入操作n);printf
5、(t3 进入删除操作n);printf(t4 中序输出n);printf(t5 线索输出n);printf(t0 退出n);printf(t 请选择:);scanf(%d,&i);printf(n);switch(i)case 1:PreThread(T);printf(t已经实现二叉树的线索化n);printf(n);break;case 2:Insert(T);printf(n);break;case 3:T=DeleteNode(T);printf(n);break;case 4:Inorder(T);printf(n);break;case 5:PrintIndex(T);break;
6、case 0:exit(1);default:printf(errornt请继续选择:);（2）、中序线索化算法：void PreThread(Bithptr *root) /中序线索化算法，函数实现Bithptr *p;p=root; if(p) PreThread(p-lchild);/线索化左子树 if(pre&pre-rtag=1)pre-rchild=p; /前驱结点后继线索化 if(p-lchild=NULL) p-ltag=1;p-lchild=pre;if(p-rchild=NULL) /后继结点前驱线索化p-rtag=1;pre=p;PreThread(p-rchild);3
7、.1、程序中所采用的数据结构及存储结构的说明二叉树是由n（n=0）个结点组成的有限集合，其中：（1）当n0时，为空二叉树。（2）当n0时，有且仅有一个特定的结点，称为二叉树的根，不相交的子集，其中每一个子集本身又是一棵二叉树，分别称为左子树和右子树。线索化是将二叉树转换成线索二叉树的过程。按某种遍历将二叉树线索化，只需在遍历过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继结点。（1）线索二叉树的结点的结构如下：ltaglchilddatartagrchild约定：Ltag=0 /表示lchild域指示该结点的左孩子Ltag=1 /表示lchild域指示该结点的前驱Rtag
8、=0 /表示rchild域指示该结点的右孩子Rtag=1 /表示rchild域指示该结点的后继(2)线索链表中结点类型说明： Typedef char datatype; Typedef struct node Int ltag,rtag; Datatype data; Struct node *lchild,*rchild;bithptr;(3)线索化算法：结点*pre 是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行以下三步操作：1）若*p有空指针域，则将相应的标志置1.2）若*p的左线索标志已经建立（p-ltag=1）,则可使其前驱线索化，令p-lchild=
9、pre.3)若*pre的右线索标志已经建立（pre-rtag=1）,则可使其后继线索化，令pre-rchild=p.如此，二叉树的线索化可以在二叉树的遍历过程完成，该算法应为相应顺序的遍历算法的一种变化形式。（4）二叉链表的建立：其算法描述如下：Bitree *crt_bt_pre(bitree *bt) Char ch; Ch=getchar( ); If(ch=) Bt=null; Else Bt=(bitree *)malloc(sizeof(bitree); Bt-data=c; Bt-lchild=crt_bt_pre(bt-lchild); Bt-rchild=crt_bt_pre
10、(bt-rchild); Return(bt);3.2、算法的设计思想建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0; （2）若rear为偶数，则该结点为父结点的左孩子；若rear为
11、奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 （3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。结点插入算法：由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况：1）：插入的节点t是右儿子，t
12、的中序后继是其父亲的中序后继，中序前驱是其父亲。2）：插入的节点t是左儿子，t的中序前驱是其父亲的中序前驱，中序后继是其父亲。结点删除算法：删除的情况与搜索二叉树的删除的类似1）：删除的节点p是叶子节点，直接删除，修改其父亲的线索。2）：删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变。3）：删除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除。4、调试与测试：4.1、调试方法与步骤：1、当用二叉链表作为二叉树的存储结构时。可以方便地找到某个结点的左右孩子，但一般情况下，无法直接摘到该结点在没中遍历序列中的前驱和后继接待你。为了解决这个问题，所以采用线索二叉树。但是在编写过程中，忽略了线索二叉树的改变，没有改变空的左孩子指针域，而后再看了一遍数据结构的相关指导教材，发现了错误，及时改正，将空的左孩子指针域改为指向其前驱。2、在进行线索化的编写过程中，出现了问题。开始只能对几点进行前驱线索化，而不能进行后继线索化。为此做了相应调整：（1）若*p有
