线索二叉树的建立以及遍历（先序、中序、后序）

真的参考了很多 终于明白啦！！ 记录一下！

/* 测试main时 要分开测试三种建立线索二叉树的方法 在main函数建二叉树的时候用了三个变量建立三个二叉树 却还是不能同时测试 很迷**/ #include "stdio.h" #include "stdlib.h" #define NULL 0 #define OK 1 typedef char TElemType; typedef int Status; typedef enum{Link,Thread} PointerTag; typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; BiThrTree pre; //pre为全局变量 Status CreateBiTree(BiThrTree *T); Status PreThreading(BiThrTree t); Status PreorderThreading(BiThrTree *p, BiThrTree t); Status PreorderTraverse(BiThrTree p); Status InThreading(BiThrTree t); Status InorderThreading(BiThrTree *p, BiThrTree t); Status InorderTraverse(BiThrTree p); BiThrTree parent(BiThrTree thrt,BiThrTree p); Status PostThreading(BiThrTree t); Status PostorderThreading(BiThrTree *p, BiThrTree t); Status PostorderTraverse(BiThrTree p); //先序创建二叉树 Status CreateBiTree(BiThrTree *T){ /*按先序次序输入二叉树中结点的值，#字符表示空树，注意使每个结点的左右标志初始为Link(即为0)；*/ char ch; ch=getchar(); if (ch=='*') (*T)=NULL; else{ (*T)=(BiThrTree) malloc(sizeof(BiThrNode)); (*T)->data=ch; (*T)->LTag=(*T)->RTag=Link; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } return OK; } /**********************************************先序****************************/ //先序添加线索 Status PreThreading(BiThrTree t){ if(t){ if(t->lchild==NULL){ t->lchild = pre; t->LTag = Thread; } if(pre && pre->rchild == NULL){ pre->rchild = t; pre->RTag = Thread; } pre = t; if(t->LTag == Link) PreThreading(t->lchild); if(t->RTag == Link) PreThreading(t->rchild); } return OK; } //先序遍历二叉树，并将其中序线索化 Status PreorderThreading(BiThrTree *p, BiThrTree t){ (*p) = (BiThrTree)malloc(sizeof(BiThrNode)); (*p)->LTag = Link; (*p)->RTag = Thread; (*p)->rchild = (*p); if(!t){ (*p)->lchild = (*p); } else{ (*p)->lchild = t; pre = (*p); PreThreading(t); (*p)->rchild = pre; pre->RTag = Thread;///现在pre是最后一个节点啦 pre->rchild = (*p); } return OK; } //先序线索二叉树遍历 Status PreorderTraverse(BiThrTree p){ BiThrTree t; t = p->lchild; while(t!=p){ while(t->LTag == Link){ printf("%c ",t->data); t = t->lchild; } printf("%c ",t->data); while(t->RTag == Thread && t->rchild!=p){ t = t->rchild; printf("%c ",t->data); } t = t->rchild; } return OK; } /**********************************************中序****************************/ //中序添加线索 Status InThreading(BiThrTree p){ if(p){ InThreading(p->lchild); //p的左子树线索化 if(p->lchild==NULL){ //前驱线索 p->LTag=Thread; p->lchild=pre; } if(pre->rchild==NULL){ //后继线索 pre->RTag=Thread; pre->rchild=p; } pre=p; //保持pre为p的前驱 InThreading(p->rchild); //右子树线索化 } return OK; } //中序遍历建立线索二叉树 Status InorderThreading(BiThrTree *Thrt,BiThrTree T){ //中序遍历二叉树T，并将其中序线索化 (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode)); //这样写太多了吧 (*Thrt)->LTag=Link; (*Thrt)->RTag=Thread;(*Thrt)->rchild=(*Thrt); if(T==NULL) (*Thrt)->lchild=(*Thrt); else{ (*Thrt)->lchild=T;pre=(*Thrt); InThreading(T); pre->rchild=(*Thrt); pre->RTag=Thread; (*Thrt)->rchild=pre; } return OK; } //中序线索二叉树遍历 Status InorderTraverse(BiThrTree Thrt){ //中序遍历线索二叉树Thrt,Thrt指向头结点 BiThrTree p; p=Thrt->lchild; while(p!=Thrt){ while(p->LTag==Link) p=p->lchild; printf("%-2c",p->data); while(p->RTag==Thread &&p->rchild!=Thrt){ p=p->rchild; printf("%c ",p->data); } p=p->rchild; } return OK; } /**********************************************后序****************************/ //后序添加线索 Status PostThreading(BiThrTree p) { if (p){ PostThreading(p->lchild); PostThreading(p->rchild); if (p->lchild==NULL){ p->lchild = pre; p->LTag = Thread; } if (pre != NULL&&pre->rchild == NULL){ pre->rchild = p; pre->RTag = Thread; } pre = p; } return OK; } //后序遍历二叉树，并将其后序线索化 Status PostorderThreading(BiThrTree *H,BiThrTree T) //创建头节点,后序线索二叉树 { (*H) = (BiThrTree)malloc(sizeof(BiThrNode)); (*H)->rchild = (*H); (*H)->RTag = Link; if(!T) { (*H)->lchild = (*H); (*H)->LTag = Link; } else { pre = (*H); (*H)->lchild = T; (*H)->LTag = Link; PostThreading(T); (*H)->rchild = pre; } return 1; } //找双亲 BiThrTree parent(BiThrTree thrt,BiThrTree p) { BiThrTree temp; temp=thrt; if(temp->lchild==p) return temp;//父节点是头结点 else { temp=temp->lchild; while( temp->lchild!=p && temp->rchild!=p ) { if(Link==temp->RTag) temp=temp->rchild;//结点有右结点，往右 else temp=temp->lchild; } //如果结点没有右孩子，去左孩子，没有左孩子，去前驱 } return temp; } //后续线索二叉树遍历 Status PostorderTraverse(BiThrTree Thrt) { BiThrTree p; BiThrTree par; p=Thrt->lchild; while(1) { while(Link==p->LTag) p=p->lchild; if(Link==p->RTag) p=p->rchild; //p指向第一个被访问的结点 else break; } while(p!=Thrt) { printf("%c ",p->data); par=parent(Thrt,p);//parent是p的双亲: if(Thrt==par) p=Thrt;//若parent是thrt，即p是根结点，则无后继 else if(p==par->rchild||Thread==par->RTag) p=par;//若p是双亲的右孩子，或者是独生左孩子，则后继为双亲 else { while(par->RTag==Link) { //若p是有兄弟的左孩子，则后继为双亲的右子树上后序遍历访问的第一个节点。 par=par->rchild; while(par->LTag==Link) { par=par->lchild; } } p=par; } } return OK; } int main(){ BiThrTree T=NULL,Thrt=NULL; BiThrTree S=NULL,Thst=NULL; BiThrTree K=NULL,Thkt=NULL; /*测试先序线索算法*/ printf("\nCreate a Thread Binary Tree: "); CreateBiTree(&T); //建立二叉树T printf("\n二叉树创建完成!\n"); PreorderThreading(&Thrt, T); printf("\n二叉树先序线索化完成!\n\n"); printf("先序遍历线索二叉树: "); PreorderTraverse(Thrt); //先序遍历线索二叉树 printf("\n\n先序遍历线索二叉树完成!\n\n"); /*测试中序线索算法*/ printf("\nCreate a Thread Binary Tree: "); CreateBiTree(&S); //建立二叉树T printf("\n二叉树创建完成!\n"); InorderThreading(&Thst, S); printf("\n二叉树中序线索化完成!\n\n"); printf("中序遍历线索二叉树: "); InorderTraverse(Thst); //中序遍历线索二叉树 printf("\n\n中序遍历线索二叉树完成!\n\n"); /*测试后序线索算法*/ printf("\nCreate a Thread Binary Tree: "); CreateBiTree(&K); //建立二叉树T printf("\n二叉树创建完成!\n"); PostorderThreading(&Thkt, K); printf("\n二叉树后序线索化完成!\n\n"); printf("后序遍历线索二叉树: "); PostorderTraverse(Thkt); //后序遍历线索二叉树 printf("\n\n后序遍历线索二叉树完成!\n\n"); return OK; }