中序线索化二叉树数据结构#严选优质

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

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

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

4、*定义结点元素*/ PointerTag LTag,RTag; DataType data; struct BiThreTree *lchild,*rchild; BiThreTree; BiThreTree *pre; /*全局变量，用于二叉树的线索化*/ BiThreTree *CreateTree() /*按前序输入建立二叉树*/ BiThreTree *T; DataType ch; scanf(%c,&ch); if(ch=#) T=NULL; else T=(BiThreTree *)malloc(sizeof(BiThreTree); T-data=ch; T-LTag=Link

5、; /*初始化时指针标志均为Link*/ T-RTag=Link; 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 *InOrde

6、rThrTree(BiThreTree *T) /*中序线索化二叉树*/ BiThreTree *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

7、=Thre-lchild; while(p!=Thre) /*指针回指向头结点时结束*/ while(p-LTag=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(“In

8、Order Traverse Binary Tree:n”); InThrTravel(Thre); system(pause); 【调试举例】（1）建立二叉树时，按先序遍历方式输入：“ABD#EH#I#CF#G#”，其中“#”表示空指针。（2）建立的二叉树为： A B C D E F G H I （3）程序输出为中序遍历线索化二叉树的结果：DBHEIAFCG 已知A、B和C为三个递增有序的线性表，现要求对A表作如下操作：删除那些既在B表中出现又在C表中出现的元素。【实验步骤】1.试对顺序表编写实现上述操作的算法并上机编写代码，要求算法尽可能高效。在实验报告中分析你的算法的时间复杂度。2.A表

9、中要删除的元素实际上就是在三个表中都存在的元素。注意这三个线性表都是递增有序的线性表！可以利用这一性质减少对线性表“扫描”的趟数。3.改用单链表作为存储结构编写算法，请释放A表中无用的结点空间，并上机编程实现。【算法思想】先从B和C中找出共有元素same，再从A中从当前位置开始，凡小于same的元素均保留，等于same的就跳过，大于same时就再找下一个same。【顺序存储结构算法描述】void SqList_Delete(SqList&A, SqList B, SqList C)i=0;j=0;m=0;/*i指示A中元素原来的位置，m为移动后的位置*/while(iA.length&jB.l

10、ength&kC.length) if(B.elemjC.elemk)k+;else same= B.elemj;/*找到了相同元素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.l

11、ength=m;/*SqList_Delete*/【顺序存储结构参考程序】#includemain() #define N 3/*宏定义,代表数组维数*/ #define M 4 #define T 5 int 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=0;j=0;m=0;k=0;/*

12、分别赋值为0，即指向数组的第一元素*/ while(iN&jM&kT) if(bjck) k+; else same=bj; while(bj=same)j+; while(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

13、: 此时输入三组测试数据，数据间用空格隔开： 2 3 4回车 3 4 5 6 回车 4 5 6 7 8 回车 程序输出结果：a3=2,3，即删除了数组a中即在b和c中都出现的元素。【单链表存储结构参考程序】# include # include Typedef struct LNode int data; struct LNode *next; Lnode,*LinkList;/*定义链表节点的结构*/void main ( )/*功能：建立单链表A,B,C，并且删除A中均在B和C中出现的数据。*/CreateList (LinkList head);/*函数声明*/ListDelete (L

14、inkList La, LinkList Lb ,LinkList Lc);Print (LinkList head); LinkList headA,headB,headC; headA=NULL; headB=NULL; headC=NULL;headA=CreateList(headA);/*建立链表*/headB=CreateList(headB);headC=CreateList(headC);print(headA);/*输出显示链表数据*/print(headB);print(headC);headA=ListDelete(headA,headB,headC);/*删除A中满足条

15、件的节点*/Print (headA); LinkList createList(LinkList head)/*功能：建立有头节点head的数据单链表*/ LinkList p,q; p=q=(LinkList)malloc(sizeof(Lnode); printf(ninput data:n); scanf(%d,&p-data); p-next=NULL; while(p-data0)/*建立链表的输入数据必须大于0，数据输入时以输入任何负数作为结束*/ if(head=NULL) head=p; else q-next=p; q=p; p=(LinkList)malloc(sizeo

16、f(Lnode); printf(ninput data:n); scanf(%d,&p-data); p-next=NULL; return head; LinkList ListDelete(LinkList La,LinkList Lb,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中都存在的数据，并

17、且定位*/ if(pa-datadata)/*在A中找到B和C中都存在的数据*/ qa=pa; pa=pa-next; else if(pa-data=pb-data)/*删除节点*/ qa-next=pa-next; f ree(pa); pa=qa-next; else pb=pb-next; /*else*/ /*while*/ return La; void print(LinkList head)/*输出链表数据*/ LinkList r; r=head; printf(noutput data:n); while(r!=NULL) printf(%d ,r-data); r=r-n

18、ext;return;【实验分析】（1）因为单链表A，B，C中的元素都是递增有序的，所以先通过遍历B和C找到它们共同的元素，然后再查找该元素是否也存在于A中，存在则删除；否则再查找B和C中的下一个相同元素。(2)无论是顺序存储结构还是单链表存储结构，都采用一次遍历的方式来找到即在B和C中都出现的元素，故时间复杂度为O(n)。 作业参考答案 2007.9.271.试写出一个计算链表中数据元素结点个数的算法，其中指针P指向该链表的第一个结点。【参考算法】int ListLength_L(LinkList &L)p=L-next;i=0; while(p) p=p-next; i+; return

19、i;2.试设计实现在单链表中删去值相同的多余结点的算法。【参考算法】status ListDelete_L(LinkList &L) p=L-next; while(p) q=p-next; 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.有一个线性表（a1 a2 an），它存储在有附加表头结点的单链表中，写一个算法求出该线性表中值为x的元素的序号，若x不存在，则输出序号0.【参考算法】int Locate_L（LinkList L,int x） k=

20、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的元素，使插入后的线性表仍为非递减有序的，分别用向量和单链表编写算法。【参考算法】向量算法：status Insert_SqList(SqList &va,int x) if(va.length+1va.listsize) return error;

21、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) p=L-next; 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 &Lc)/*用La作为新线性表的头结点*/