線索二叉樹即從前、中、后序三種遍歷中其中一種來看，樹中的左右孩子都不會是空著的，都會指向對應的前驅和后驅。 以中序遍歷為例，二叉樹線索化過程如下： 先是樹的結構

typedef struct ThreadNode{Elemetype data;struct ThreadNode *lchild,*rchild;int ltag,rtag;
}ThreadNode,*ThreadTree;

void InThread(ThreadTree &p,ThreadTree &pre){//記錄當前節點和前驅節點if(p!=NULL){InThread(p->lchild,pre);//先看左子樹if(p->lchild==NULL){//對左孩子進行修改p->lchild=pre;p->ltag = 1;}if(pre!=NULL&&pre->rchild==NULL){//對右孩子進行修改pre->rchild=p;pre->rtag=1;}pre = p;//在下次搜索前及時修改前驅InThread(p->rchild,pre);//看右子樹}
}

將樹進行線索化

void CreateInThread(ThreadTree T){ThreadTree pre = NULL;if(T!=NULL){InThread(T,pre);pre->rchild = NULL;pre->rtag = 1;//對最后一個節點進行修改}
}

接下來是遍歷線索樹

ThreadNode *Firstnode(ThreadNode *p){while(p->ltag==0) p = p->lchild;return p;
}//找出左下第一個節點ThreadNode *Nextnode(ThreadNode *p){if(p->rtag = 0) return Firstnode(p->rchild);else return p->rchild;
}//尋找下一個節點void vist(ThreadNode *p){printf("%d",p->data);
}void Inorder(ThreadNode *T){for(ThreadNode *p = Firstnode(T);p!=NULL;p = Nextnode(p))vist(p);
}

本文由博客一文多發平臺 OpenWrite 發布！