本文共 1526 字，大约阅读时间需要 5 分钟。

线索二叉树

       对二叉树以某种次序遍历使其变化线索二叉树的过程称作线索化。

typedef struct TBTNode{	char data;	int ltag,rtag;//ltag=0，则lchild指向左孩子  ltag=1,则lchild指向直接前驱 同理rtag 	struct TBTNode *lchild;	struct TBTNode *rchild;}TBTNode;//中序线索化二叉树void InThread(TBTNode *p,TBTNode *&pre){	if(p!=NULL)	{		InThread(p->lchild,pre);		if(p->lchild==NULL)		{			p->lchild=pre;			p->ltag=1;		}		if(pre!=NULL&&pre->lchild==NULL)		{			pre->rchild=p;			pre->rtag=1;		}        pre=p;	    InThread(p->rchild,pre);	}} //求中序序列下的第一个结点TBTNode *First(TBTNode *p){	while(p->ltag==0)		p=p->lchild;	return p;} //求中序序列下的后继结点TBTNode *Next(TBTNode *p){	if(p->rtag==0)		return First(p->rchild);	else		return p->rchild;}

前序线索化

typedef struct TBTNode{	char data;	int ltag,rtag;//ltag=0，则lchild指向左孩子  ltag=1,则lchild指向直接前驱 同理rtag 	struct TBTNode *lchild;	struct TBTNode *rchild;}TBTNode;//前序线索化二叉树void preThread(TBTNode *p,TBTNode *&pre){	if(p!=NULL)	{ 		if(p->lchild==NULL)		{			p->lchild=pre;			p->ltag=1;		}		if(pre!=NULL&&pre->lchild==NULL)		{			pre->rchild=p;			pre->rtag=1;		}		pre=p;		if(p->ltag==0)			preThread(p->lchild,pre);		if(p->rtag==0)			preThread(p->rchild,pre);	}}

后序线索化

typedef struct TBTNode{	char data;	int ltag,rtag;//ltag=0，则lchild指向左孩子  ltag=1,则lchild指向直接前驱 同理rtag 	struct TBTNode *lchild;	struct TBTNode *rchild;}TBTNode;//后序线索化二叉树void PostThread(TBTNode *p,TBTNode *&pre){	if(p!=NULL)	{ 		PostThread(p->lchild,pre);		PostThread(p->rchild,pre);		if(p->lchild==NULL)		{			p->lchild=pre;			p->ltag=1;		}		if(pre!=NULL&&pre->lchild==NULL)		{			pre->rchild=p;			pre->rtag=1;		}	}}

转载地址：https://codingchaozhang.blog.csdn.net/article/details/85259596 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！