中序线索化二叉树数据结构

1、中序线索化二叉树数据结构.当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右孩子结点的指 针，所以从任一结点出发只能直接找到该结点的左、右孩子。在一般情况下靠它无法直接找 到该结点在某种遍历次序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结 点的指针，将降低存储空间的效率。与此同时，我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的 二叉链表中含有2n个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针， 因此一共使用了 n-1个指针，所以在n个结点的二叉链表中含有2n-(n-l)=n+1个空指针。因此，可以利用这些空指针，存放指向结点

2、在某种遍历次序下的前驱和后继结点的指针。这 种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉 树。为了区分一个结点的指针是指向其孩子的指针，还是指向其前驱或后继结点的线索，可 在每个结点中增加两个线索标志。这样，线索二叉树结点类型定义为：LchildLtagDataRtagRchild其中：Ltag=0时，表示Lchild指向该结点的左孩子；Ltag=1时，表示Lchild指向该结点的线性前驱结点;Rtag=0时，表示Rchild指向该结点的右孩子；Rtag=1时，表示Rchild指向该结点的线性后继结点;以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结

3、构，叫做线索二叉链表；指 向结点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树 对二叉树以某种次序遍历将其变为线索二叉树的过程叫做线索化。中序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法 访问结点时建立线索。例如有如上图所示二叉树，则中序遍历的顺序是：0 / J * I + H A G【参考程序】#include #include typedef enumLink,Thread PointerTag; /*指针标志*/typedef char DataType;typedef struct BiThreTree /*定义结点元素*/Po

4、interTag LTag,RTag;DataType data;struct BiThreTree *lchild,*rchild;BiThreTree;BiThreTree *pre;/*全局变量，用于二叉树的线索化*/BiThreTree *CreateTree()/*按前序输入建立二叉树*/BiThreTree *T;DataType ch;scanf(%c,&ch);if(ch=#)T=NULL;elseT=(BiThreTree *)malloc(sizeof(BiThreTree);T-data=ch;T-LTag二Link；/*初始化时指针标志均为Link*/T-RTag=Li

5、nk;T-lchild=CreateTree()；T-rchild=CreateTree()；return T；void InThread(BiThreTree *T)BiThreTree *p；p=T；if(p)InThread(p-lchild)；if(!p-lchild) p-LTag=Thread；p-lchild=pre;if(!pre-rchild) pre-RTag=Thread;pre-rchild=p;pre=p;InThread(p-rchild);BiThreTree *InOrderThrTree(BiThreTree *T) /*中序线索化二叉树*/ BiThreTr

6、ee *Thre；/*Thre 为头结点的指针*/Thre=(BiThreTree *)malloc(sizeof(BiThreTree);Thre-lchild=T；Thre-rchild=Thre；pre=Thre；InThread(T)；pre-RTag=Thread；pre-rchild=Thre；Thre-rchild=pre；return Thre；void InThrTravel(BiThreTree *Thre) /*中序遍历二叉树*/BiThreTree *p;p=Thre-lchild;while(p!=Thre) /*指针回指向头结点时结束*/ while(p-LTag=

7、Link)p=p-lchild;printf(%4c,p-data); while(p-RTag=Thread&p-rchild!=Thre)p=p-rchild;printf(%4c,p-data);p=p-rchild;void main()BiThreTree *T,*Thre;printf(“PreOrder Create Binary Tree:n”);T=CreateTree();Thre=InOrderThrTree(T);printf(“InOrder Traverse Binary Tree:n”);InThrTravel(Thre);system(pause);【调试举例】

8、建立二叉树时，按先序遍历方式输入：“ABD#EH#I#CF#G#”，其中“#”表示空指 针。建立的二叉树为：ABCD E F GH I程序输出为中序遍历线索化二叉树的结果：DBHEIAFCG已知A、B和C为三个递增有序的线性表，现要求对A表作如下操作：删除那些既在B表中 出现又在C表中出现的元素。【实验步骤】试对顺序表编写实现上述操作的算法并上机编写代码，要求算法尽可能高效。在实验报告 中分析你的算法的时间复杂度。A表中要删除的元素实际上就是在三个表中都存在的元素。注意这三个线性表都是递增有 序的线性表！可以利用这一性质减少对线性表“扫描”的趟数。3改用单链表作为存储结构编写算法，请释放A表中

9、无用的结点空间，并上机编程实现。【算法思想】先从B和C中找出共有元素same，再从A中从当前位置开始，凡小于same的元素均保留, 等于same的就跳过，大于same时就再找下一个same。【顺序存储结构算法描述】void SqList_Delete(SqList&A, SqList B, SqList C)i=O；j=O；m=O；/*i指示A中元素原来的位置，m为移动后的位置*/while(iA.leng th&jB.leng th&kC.leng th)if(B.elemjC.elemk) j+；else if(B.elemjC.elemk)k+；elsesame= B.elemj；/*找

10、到了相 同元素 same*/while(B.elemj=same)j+；while(C.elemk)=same)k+；/*j,k 后移到新的元素*/while(iA.length&A.elemisame)A.elemm+=A.elemi+；/ *需要保留的元素移动到新位置*/while( iA.length&A.elemi=same)i+；/*else*/*while*/while(iA.length)A.elemm+=A.elemi+；/*A 的剩余元素重新存储*/A.length=m;/*SqList_Delete*/【顺序存储结构参考程序】#includemain()#defineN3/

11、*宏定义,代表数组维数*/#defineM4#defineT5int i,j,k,r,m,same；/*定义变量分别指向数组a,b,c*/int aN,bM,cT;printf(“please input numbers:n”)；for (i=0；iN；i+) scanf(%d,&ai)；for (j=0；jM；j+) scanf(%d,&bj)；for (k=0；kT；k+)scanf(%d,&ck)；i=O；j=O；m=O；k=O；/*分别赋值为0,即指向数组的第一元素*/while(iN&jM&kT)if(bjck) k+；elsesame=bj； while(bj=same)j+;wh

12、ile(ck=same)k+;while(iN&aisame)am+=ai+;while(iN&ai=same) i+;while(iN)am+=ai+;printf(a%d二,m)；/*输出删除元素后的数组a/*for (r=0;rm-1;r+)printf(%d,ar);printf(%d,am-1)；printf(n)；return；【程序调试】程序运行是屏幕显示：please input numbers:此时输入三组测试数据,数据间用空格隔开:2 3 4回车3 4 5 6回车4 5 6 7 8回车程序输出结果：a3 = 2,3,即删除了数组a中即在b和c中都出现的元素。单链表存储结构参

13、考程序】# include # include Typedef struct LNodeint data;struct LNode *next;Lnode,*LinkLis t；/*定义链表节点的结构*/void main ( )/*功能：建立单链表A,B,C，并且删除A中均在B和C中出现的数据。*/Crea te Lis t (LinkLis t head)；/*函 数声明*/ListDelete (LinkList La, LinkList Lb ,LinkList Lc)；Print (LinkList head)；LinkList headA,headB,headC；headA=NUL

14、L；headB=NULL；headC=NULL；headA=Crea teLis t( headA)；/*建立链表*/headB=CreateList(headB)；headC=CreateList(headC)；prin t(headA)；/*输出显示链表数据*/print(headB)；print(headC)；headA二ListDelete(headA,headB,headC)；/*删除 A 中满足条件的节点*/Print (headA);LinkList createList(LinkList head)/*功能：建立有头节点head的数据单链表*/LinkList p,q;p=q=

15、(LinkList)malloc(sizeof(Lnode);printf(ninput data:n);scanf(%d,&p-data);p-next=NULL;while(p-dataO)/*建立链表的输入数据必须大于0，数据输入时以输入任何负数作 为结束*/if(head=NULL) head=p;elseq-next=p;q=p;p=(LinkList)malloc(sizeof(Lnode);printf(ninput data:n);scanf(%d,&p-data);return head;LinkList ListDelete(LinkList La,LinkList Lb,

16、LinkList Lc)/*功能：删除A中的有关节点*/LinkList pa,pb,pc,qa;pa=La;qa=La;pb=Lb;pc=Lc;while(pb&pc)if(pb-datadata)pb=pb-next;else if(pb-datapc-data)pc=pc-next;else/*首先找到B和C中都存在的数据，并且定位*/f (pa-datapb-data)/*在A中找到B和C中都存在的数据*/ qa=pa;else if(pada ta=pbda ta)/*删 除节点*/ qa-next=pa-next; f ree(pa);pa=qa-next;else pb=pb-n

17、ext;/*else*/*while*/return La;void print(LinkList head)/*输出链表数据*/LinkList r;r=head;printf(noutput data:n);while(r!=NULL)printf(%d ,r-data);return;【实验分析】因为单链表A, B, C中的元素都是递增有序的，所以先通过遍历B和C找到它们共同 的元素，然后再查找该元素是否也存在于A中，存在则删除；否则再查找B和C中的下一个 相同元素。无论是顺序存储结构还是单链表存储结构，都采用一次遍历的方式来找到即在B和C中 都出现的元素，故时间复杂度为 O(n)。作业

18、参考答案2007.9.271试写出一个计算链表中数据元素结点个数的算法，其中指针P指向该链表的第一个结点。【参考算法】int ListLength_L(LinkList &L)p=L-next;i=0;while(p)p=p-next;i+;return i;2试设计实现在单链表中删去值相同的多余结点的算法。【参考算法】status ListDelete_L(LinkList &L)p=L-next;while(p)r=p;while(q)if(q-data=p-data)r-next=q-next;free(q);q=r-next;else r=q;q=q-next;p=p-next;3有一

19、个线性表(al a2 -an),它存储在有附加表头结点的单链表中，写一个算法求出该 线性表中值为x的元素的序号，若x不存在，则输出序号0.【参考算法】int Locate_L(LinkList L,int x)k=1;for (p=L-next;p&p-data!=x;p=p-next)k+;if(knext;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next;q-next=p;s-next=q;L-next=s;5.在一个非递减有序线性表中，插入一个值为x的元素，使插入后的线性表仍为非递减有序 的，分别用向

20、量和单链表编写算法。【参考算法】向量算法：status Insert_SqList(SqList &va,int x)if(va.length+1va.listsize) return error;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;retrun ok;单链表算法：status Insert_LinkList(LinkList &L)while(p &p-datanext;q=(LinkList)malloc(sizeof(LNode);q-data=x;q-next=p;r-next=q;rerurn ok;6将两个递增有序的线性表归并成一个非递增有序表。【参考算法】void MergeList_L(LinkList &La,LinkList &Lb,LinkList