#include
#include
#include
typedef char DataType;/*定義DataType類型*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
DataType data;
struct node *lchild, *rchild;/*左右孩子子樹*/
PointerTag LTag,RTag;
}BiThrNode; /*結(jié)點(diǎn)類型*/
typedef BiThrNode *BiThrTree ;/*二叉樹類型*/
void CreatBinTree(BiThrTree *T)
{ /*構(gòu)造二叉鏈表,注意:輸入序列是先序序列*/
char ch;
if ((ch=getchar())==' ')
*T=NULL;
else{ /*讀入非空格*/
*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成結(jié)點(diǎn)*/
(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
CreatBinTree(&(*T)->lchild); /*構(gòu)造左子樹 */
CreatBinTree(&(*T)->rchild); /*構(gòu)造右子樹*/
}
}
BiThrTree pre;/*全局變量*/
void InThreading(BiThrTree p)
{
if(p)
{InThreading(p->lchild);/*左子樹線索化*/
if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驅(qū)線索*/
if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后繼線索*/
pre=p;/*保持pre指向p*/
InThreading(p->rchild);/*右子樹線索化*/
}
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
/*中序遍厲二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建頭結(jié)點(diǎn)*/
(*Thrt)->rchild=*Thrt;/*右指針回指*/
if(!T) (*Thrt)->lchild=*Thrt;
else
{ (*Thrt)->lchild=T;pre=*Thrt;
InThreading(T);/*中序遍歷進(jìn)行中序線索化*/
pre->rchild=*Thrt;pre->RTag=Thread;/*最后一個結(jié)點(diǎn)線索化*/
(*Thrt)->rchild=pre;
}
return 1;
}
int print(BiThrTree e)
{printf("%d %c %d\n",e->LTag,e->data,e->RTag);return 1;}
int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
/*T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍厲二叉樹*/
{BiThrTree p;
p=T->lchild;/*p指向根結(jié)點(diǎn)*/
while(p!=T)/*空樹或遍厲結(jié)束時，p==T*/
{while(p->LTag==Link) p=p->lchild;
if(!visit(p)) return 0;/*打印*/
while(p->RTag==Thread&&p->rchild!=T)
{p=p->rchild;visit(p);}/*訪問后繼結(jié)點(diǎn)*/
p=p->rchild;
}
return 1;
}
void main()
{ /*測試程序*/
BiThrTree T,Thrt;
CreatBinTree(&T);
InOrderThreading(&Thrt,T);
InOrderTraverse(Thrt,print);
}
/*可輸入"-+a *b -c d /e f "來測試(注意空格)*/
#include
#include
typedef char DataType;/*定義DataType類型*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
DataType data;
struct node *lchild, *rchild;/*左右孩子子樹*/
PointerTag LTag,RTag;
}BiThrNode; /*結(jié)點(diǎn)類型*/
typedef BiThrNode *BiThrTree ;/*二叉樹類型*/
void CreatBinTree(BiThrTree *T)
{ /*構(gòu)造二叉鏈表,注意:輸入序列是先序序列*/
char ch;
if ((ch=getchar())==' ')
*T=NULL;
else{ /*讀入非空格*/
*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成結(jié)點(diǎn)*/
(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
CreatBinTree(&(*T)->lchild); /*構(gòu)造左子樹 */
CreatBinTree(&(*T)->rchild); /*構(gòu)造右子樹*/
}
}
BiThrTree pre;/*全局變量*/
void InThreading(BiThrTree p)
{
if(p)
{InThreading(p->lchild);/*左子樹線索化*/
if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驅(qū)線索*/
if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后繼線索*/
pre=p;/*保持pre指向p*/
InThreading(p->rchild);/*右子樹線索化*/
}
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
/*中序遍厲二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建頭結(jié)點(diǎn)*/
(*Thrt)->rchild=*Thrt;/*右指針回指*/
if(!T) (*Thrt)->lchild=*Thrt;
else
{ (*Thrt)->lchild=T;pre=*Thrt;
InThreading(T);/*中序遍歷進(jìn)行中序線索化*/
pre->rchild=*Thrt;pre->RTag=Thread;/*最后一個結(jié)點(diǎn)線索化*/
(*Thrt)->rchild=pre;
}
return 1;
}
int print(BiThrTree e)
{printf("%d %c %d\n",e->LTag,e->data,e->RTag);return 1;}
int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
/*T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍厲二叉樹*/
{BiThrTree p;
p=T->lchild;/*p指向根結(jié)點(diǎn)*/
while(p!=T)/*空樹或遍厲結(jié)束時，p==T*/
{while(p->LTag==Link) p=p->lchild;
if(!visit(p)) return 0;/*打印*/
while(p->RTag==Thread&&p->rchild!=T)
{p=p->rchild;visit(p);}/*訪問后繼結(jié)點(diǎn)*/
p=p->rchild;
}
return 1;
}
void main()
{ /*測試程序*/
BiThrTree T,Thrt;
CreatBinTree(&T);
InOrderThreading(&Thrt,T);
InOrderTraverse(Thrt,print);
}
/*可輸入"-+a *b -c d /e f "來測試(注意空格)*/