2011年软考程序员考试复习笔试知识点整理(18)2

 voidInOrderThreading(BiThrTree & Thrt,BiThrTree T)

　　{

　　Thrt=new BiThrNode;

　　Thrt->LTag=Link;

　　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;

　　}

　　}

　　voidInThreading(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);

　　}

　　}

　　boolPreOrderCreatBiTree(BiThrTree &T)

　　{//该节点非空返回true，双亲节点对应标志Link，空时返回false，双亲节点对应标志应为Thread

　　char ch;

　　scanf("%c",&ch);

　　if(ch=='#')

　　{

　　T=NULL;

　　return false;

　　}else {

　　T=new BiThrNode;

　　T->data=ch;

　　if(PreOrderCreatBiTree(T->lchild))T->LTag=Link; //左孩子存在则左标志为Link

　　else T->LTag=Thread;

　　if(PreOrderCreatBiTree(T->rchild))T->RTag=Link; //右孩子存在则右标志为Link

　　else T->RTag=Thread;

　　}

　　return true;

　　}

　　voidInOrderTraverse_Thr(BiThrTree T)

　　{

　　BiThrNode *p;

　　p=T->lchild;

　　while(p!=T)

　　{

　　while(p->LTag==Link) p=p->lchild;

　　printf("%c", p->data);

　　while(p->RTag==Thread &&p->rchild!=T) //if(p->RTag==Thread && p->rchild!=T)

　　{

　　p=p->rchild;

　　printf("%c", p->data);

　　}

　　p=p->rchild;

　　}

　　}