文档介绍：吉首大学课程设计课程设计名称:线索二叉树的应用专业班级:_09计科1班_____学生姓名:学号:指导教师:课程序设计时间:- : :建立线索二叉树,并实现线索二叉树的插入、删除和恢复线索的实现。实现本程序需要解决以下几个问题:。。。。在这个问题中,要解决的任务是:实现线索二叉树的建立、插入、删除、恢复线索的实现。n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。而在此次课程设计中,采用的是中序线索二叉树。本问题的关键和难点在于线索二叉树的插入和删除。在线索二叉树中插入一个结点或删除一个结点,一般情况下,这些操作有可能破坏原来已有的线索,因此,在修改指针时,还需要对线索做相应的修改。因此一般来说,这个过程度的代价几乎与重新进行线索化相同。{//定义数据结构 intltag,rtag;//表示child域指示该结点是否孩子 chardata;//记录结点的数据 structnode*lchild,*rchild;//记录左右孩子的指针}Bithptr;线索链表中的结点结构为:(即指在内存中建立二叉树的存储结构),建立一个二叉链表,需按某种顺序一次输入二叉树中的结点,且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树,需添加虚结点,使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列,该队列是一个指针类型的数组,保存已输入的结点地址。操作:(1)令队头指针front指向其孩子结点当前输入的建立链接的父结点,队尾指针rear指向当前输入的结点,初始:front=1,rear=0;(2)若rear为偶数,则该结点为父结点的左孩子;若rear为奇数,则该结点的右孩子;若父结点和孩子结点为虚结点,则无需链接。(3)若父结点与其两个孩子结点的链接完毕,则令front=front+1,使front指向下一个等待链接的父结点。,使其成为结点s的右孩子。(1)若s的右子树为空,则插入结点p之后成为p的中序前驱,而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。(2)若s的右子树非空,插入结点p之后s原来的右子树变成p的右子树,由于没有左子树,故s成为p的的中序前驱,p成为s的右孩子;而又由于s原来的后继成为p的后继,因此还要将s原来的本业指向s的后继的左线索改为指向p。(1)删除的节点p是叶子节点,直接删除,修改其父亲的线索(2)删除的节点p有一个儿子,p有一个左儿子,以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继,中序前驱不变;p有一个右儿子,以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱,中序后继不变(3)除的节点p有二个儿子,:(即指在内存中建立二叉树的存储结构),建立一个二叉链表,需按某种顺序一次输入二叉树中的结点,且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树,需添加虚结点,使其成为完全二叉树。Bithptr*CreatTree(){//建树函数,返回根指针 charch; intfront,rear; Bithptr*T,*s; T=NULL; front=1;rear=0;//置空二叉树 printf("创建二叉树,进行初始化,请依次输入,以#结束\n"); ch=getchar();//输入第一个字符 while(ch!='#')//判断是否为结束字符 { s=N