课程设计（论文）-线索二叉树的应用.doc

吉 首 大 学课程设计课程设计名称：线索二叉树的应用 专 业 班 级：_09计科1班_ 学 生 姓 名： 学 号： 指 导 教 师： 课程序设计时间：2011.6.22-2011.7.02目录一.需求分析2二.概要设计21.定义数据结构模块22.中序线索二叉树的表示模块33.线索二叉树的插入模块34.线索二叉树的删除模块45.程序流程图：4三.详细设计和编码51.建立二叉树52.中序遍历二叉树并对其中序线索化63.线索二叉树的插入74.线索二叉树的删除9四.调试分析141.测试结果142.调试结果分析16五.总结17六.参考书目17一.需求分析此程序需要完成如下要求：建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。实现本程序需要解决以下几个问题：1.如何建立线索二叉树。2.如何实现线索二叉树的插入。3.如何实现线索二叉树的删除。4.如何实现线索二叉树恢复线索的实现。在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实现。n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。而在此次课程设计中，采用的是中序线索二叉树。本问题的关键和难点在于线索二叉树的插入和删除。在线索二叉树中插入一个结点或删除一个结点，一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。因此一般来说，这个过程度的代价几乎与重新进行线索化相同。二.概要设计1.定义数据结构模块typedef struct node /定义数据结构int ltag,rtag; /表示child域指示该结点是否孩子 char data; /记录结点的数据struct node *lchild,*rchild; /记录左右孩子的指针Bithptr;线索链表中的结点结构为：lchildLtagDataRtagrchild2.中序线索二叉树的表示模块建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。 操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0;（2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。（3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。3.线索二叉树的插入模块在中序线索二叉树中插入一个结点p，使其成为结点s的右孩子。（1）若s的右子树为空，则插入结点p之后成为p的中序前驱，而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。（2）若s的右子树非空,插入结点p之后s原来的右子树变成p的右子树，由于没有左子树，故s成为p的的中序前驱，p成为s的右孩子;而又由于s原来的后继成为p的后继，因此还要将s原来的本业指向s的后继的左线索改为指向p。4.线索二叉树的删除模块删除的情况有以下三种（1）删除的节点p是叶子节点，直接删除，修改其父亲的线索（2）删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变（3）除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除 5.程序流程图：三.详细设计和编码1.建立二叉树建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。Bithptr *CreatTree() /建树函数，返回根指针char ch;int front,rear;Bithptr *T,*s;T=NULL;front=1;rear=0; /置空二叉树printf(创建二叉树，进行初始化，请依次输入，以#结束n);ch=getchar(); /输入第一个字符while(ch!=#) /判断是否为结束字符s=NULL;if(ch!=) /判断是否为虚结点s=(Bithptr *)malloc(sizeof(Bithptr);s-data=ch;s-lchild=NULL;s-rchild=NULL;s-rtag=0;s-ltag=0;rear+; Qrear=s; /将结点地址加入队列中if(rear=1)T=s; /输入为第一个结点为根结点else if(s!=NULL&Qfront!=NULL) /孩子和双亲结点均不是虚结点if(rear%2=0) Qfront-lchild=s; else Qfront-rchild=s;if(rear%2=1)front+;ch=getchar();return T;2.中序遍历二叉树并对其中序线索化二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继void Inorder(Bithptr *T) /中序遍历if(T)if(T-ltag!=1)Inorder(T-lchild);printf(%c,T-data);if(T-rtag!=1)Inorder(T-rchild);Bithptr *pre=NULL;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);void PrintIndex(Bithptr *t) /输出线索Bithptr *f;f=t;if(f)if(f-ltag=1&f-lchild=NULL&f-rtag=1) printf(【%c】,f-data); /如果是第一个结点if(f-ltag=1&f-lchild!=NULL) printf(%c【%c】,f-lchild-data,f-data); /如果此结点有前驱就输出前驱和此结点 if(f-ltag=1&f-rtag=1&f-rchild!=NULL) printf(%c,f-rchild-data); /如果此结点有前驱也有后继，就输出后继else if(f-rtag=1&f-rchild!=NULL) printf(【%c】%c,f-data,f-rchild-data);/如果没有前驱，就输出此结点和后继printf(n);if(f-ltag!=1)PrintIndex(f-lchild);if(f-rtag!=1)PrintIndex(f-rchild);3.线索二叉树的插入在中序线索二叉树中插入一个结点p，使其成为结点s的右孩子。（1）若s的右子树为空，则插入结点p之后成为p的中序前驱，而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。（2）若s的右子树非空,插入结点p之后s原来的右子树变成p的右子树，由于没有左子树，故s成为p的的中序前驱，p成为s的右孩子;而又由于s原来的后继成为p的后继，因此还要将s原来的本业指向s的后继的左线索改为指向p。void Insert(Bithptr *root)char ch;char c;Bithptr *p1,*child,*p2;printf(请输入要插入的结点的信息:); scanf(%c,&c);scanf(%c,&c); p1=(Bithptr *)malloc(sizeof(Bithptr); /插入的结点信息p1-data=c;p1-lchild=NULL;p1-rchild=NULL;p1-rtag=0;p1-ltag=0;printf(输入查找的结点信息:); scanf(%c,&ch);scanf(%c,&ch);child=SearchChild(root,ch); /查孩子结点的地址if(child=NULL)printf(没有找到结点n);system(pause);return ;else printf(发现结点%cn,child-data);if(child-ltag=0) /当孩子结点有左孩子的时候p2=child;child=child-lchild;while(child-rchild&child-rtag=0) /找到左子树下，最右结点child=child-rchild;p1-rchild=child-rchild; /后继化 p1-rtag=1;child-rtag=0;child-rchild=p1; /连接 p1-lchild=child; /前驱化p1-ltag=1; else /当孩子结点没有左孩子的时候p1-lchild=child-lchild; /前驱化child-ltag=0;p1-ltag=1;child-lchild=p1;p1-rchild=child;p1-rtag=1;printf(nt插入结点操作已经完成，并同时完成了线索化的恢复n);4.线索二叉树的删除删除的情况有以下三种（1）删除的节点p是叶子节点，直接删除，修改其父亲的线索（2）删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变（3）除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除 Bithptr * DeleteNode(Bithptr *t)Bithptr *child,*pre,*s,*q;char ch;printf(输入查找的结点信息:); ch=getchar();ch=getchar();child=SearchChild(t,ch); /查找该结点的孩子结点printf(发现结点:%cn,child-data);printf(ltag=%d,rtag=%dn,child-ltag,child-rtag);if(NULL=child)printf(没有找到结点:);return t;if(child!=t)pre=SearchPre(t,child);printf(发现结点:%cn,pre-data);else /当是头结点的时候if(child-ltag=1&child-rtag=1) /没有左右孩子t=NULL;else if(t-ltag=1&t-rtag!=1) /有右孩子没有左孩子t=child-rchild;child-rchild-lchild=NULL;free(child);return t;else if(t-ltag!=1&t-rtag=1) /有左孩子没有右孩子t=child-lchild;child-lchild-rchild=NULL;free(child);return t;elseif(t-ltag!=1&t-rtag!=1) /有左孩子也有右孩子t=child-lchild;s=child-lchild;while(s-rchild&s-rtag!=1)/查找孩子左子树的最右下结点s=s-rchild;q=child-rchild;while(q-lchild&q-ltag!=1)/查找孩子右子树最左下结点q=q-lchild;s-rchild=child-rchild; /连接s-rtag=0;q-lchild=s;free(child);return t; if(child=pre-lchild|child=pre) /是父亲结点的左孩子if(1=child-ltag&1=child-rtag)/孩子结点无左右pre-lchild=child-lchild;pre-ltag=1;if(child-lchild!=NULL)if(child-lchild-rtag=1)child-lchild-rchild=pre;free(child);else if(1!=child-ltag&1=child-rtag)/孩子结点有左无右 pre-lchild=child-lchild; s=child-lchild; while(s-rchild) /查找左子树的最右下结点s=s-rchild; s-rchild=child-rchild;free(child);else if(1=child-ltag&1!=child-rtag)/孩子结点有右无左 pre-lchild=child-rchild;s=child-rchild;while(s-lchild)s=s-lchild;s-lchild=child-lchild;if(child-lchild!=NULL) if(child-lchild-rtag=1)child-lchild-rchild=pre;free(child); else if(1!=child-ltag&1!=child-rtag)/孩子结点左右都有 pre-lchild=child-lchild;s=child-rchild;while(s-lchild&s-ltag!=1) /找到右子树的最左下结点s=s-lchild;q=child-lchild;while(q-rchild&q-rtag!=1) /找到左子树下最右下结点q=q-rchild;q-rchild=child-rchild; /将孩子结点右子树接到左子树最右下结点q-rtag=0;s-lchild=q;free(child); else if(child=pre-rchild) /是父亲结点的右孩子if(1=child-ltag&1=child-rtag)/孩子结点无左右pre-rchild=child-rchild;pre-rtag=1;if(child-rchild!=NULL)if(child-rchild-ltag=1)child-rchild-lchild=pre;free(child);else if(1!=child-ltag&1=child-rtag)/孩子结点有左无右pre-rchild=child-lchild;s=child-lchild;while(s-rchild)s=s-rchild;s-rchild=child-rchild;if(child-rchild!=NULL)if(child-rchild-ltag=1)child-rchild-lchild=pre;free(child);else if(1=child-ltag&1!=child-rtag)/孩子结点有右无左 pre-rchild=child-rchild;s=child-rchild;while(s-lchild)s=s-lchild;s-lchild=child-lchild;free(child);else if(1!=child-ltag&1!=child-rtag) /孩子结点左右都有pre-rchild=child-rchild;s=child-rchild;while(s-lchild&s-ltag!=1) /找到右子树的最左下结点s=s-lchild;q=child-lchild;while(q-rchild&q-rtag!=1) /找到左子树下最右下结点q=q-r