数据结构课设线索二叉树.docVIP

//数据结构课设 线索二叉树 #define ERROR 0 #define OVERFLOW 0 #define OK 1 typedef enum PointerTag{ Link , Thread}; typedef struct BiThrNode{ char data; struct BiThrNode *lchild ,*rchild; PointerTag LTag ,RTag; }BinThrNode, *BiThrTree; #include iostream #include 课设 线索二叉树.h using namespace std; BiThrTree pre; void InThreading(BiThrTree p); void CreateBiThrTree(BiThrTreeT){ //按先序次序输入二叉树结点的值，#字符表示空树 char ch; cinch; if(ch==#) T=NULL; else{ T=(BiThrNode *)malloc(sizeof(BiThrNode)); T-data=ch; CreateBiThrTree(T-lchild); T-LTag=Link; CreateBiThrTree(T-rchild); T-RTag=Link; } } void InOrderThreading(BiThrTree Thrt,BiThrTree T) //中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点 { if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); Thrt-LTag=Link;//建头结点0 Thrt-RTag=Thread; Thrt-rchild=Thrt;//右指针回指 if(!T) Thrt-lchild=Thrt; else { Thrt-lchild=T; pre=Thrt; InThreading(T); pre-rchild=Thrt; pre-RTag=Thread; Thrt-rchild=pre; } } void InThreading(BiThrTree p) //线索化 { if(p) { InThreading(p-lchild); if(!p-lchild) { p-LTag = Thread; p-lchild = pre; } if(!pre-rchild) { pre-RTag = Thread; pre-rchild = p; } pre = p; InThreading(p-rchild); } } int Visit(char e) { printf(%c ,e); return OK; } int InOrderTraverse_Thr(BiThrTree T,int (*Visit)(char e) ) //中序遍历线索化后的二叉树 { BiThrTree p; p=T-lchild; while(p!=T) { while(p-LTag==Link) p=p-lchild; Visit(p-data); while(p-RTag==Thread p-rchild!=T) { p=p-rchild; Visit(p-data); } p=p-rchild; } coutendl; return OK; } //求后继 void InorderSuccessor(BinThrNode *p) { BinThrNode *q; coutp-data的后继为： ; if(p-RTag==Thread) { p=p-rchild; coutp-dataendl; } else { q=p-rchild; while(q-LTag==Link) q=q-lchild; coutq-dataendl; } } //求前驱 void Inorderpre(BinThrNode *p) { BinThrNode *q; coutp-data的前驱为： ; if(p-LTag==Thread) { p=p-lchild; coutp-dataendl; } else { q=p-lchild; while(q-RTag==Link) q=q-rchild; coutq-dataendl; } } //求所给结点的前驱和后继