#include<stdio.h>
#include<stdlib.h>
#define elemType char
//線索二叉樹結點?
typedef struct ThreadNode{
?? ?elemType data;
?? ?struct ThreadNode *lchild,*rchild;
?? ?int ltag,rtag;//用來判斷一個結點是否有線索?
}ThreadNode,*ThreadTree;
//全局變量pre,指向當前結點的前驅
ThreadNode* pre=NULL;?
//初始化一顆二叉樹?
bool initTree(ThreadNode** root,elemType data){
?? ?*root=(ThreadNode*)malloc(sizeof(ThreadNode));
?? ?if((*root)==NULL){
?? ??? ?return false;
?? ?}
?? ?(*root)->data=data;
?? ?(*root)->lchild=NULL;
?? ?(*root)->rchild=NULL;
?? ?(*root)->ltag=0;
?? ?(*root)->rtag=0;
?? ?return true;
}
//回收動態開辟的內存?
void destroyTree(ThreadNode* root){
?? ?if(root!=NULL){
?? ??? ?if(root->ltag==0){//確保其左孩子不是線索?
?? ??? ??? ?destroyTree(root->lchild);
?? ??? ?}
?? ??? ?if(root->rtag==0){//確保其右孩子不是線索?
?? ??? ??? ?destroyTree(root->rchild);
?? ??? ?}
?? ??? ?free(root);
?? ?}
}
//給指定結點增添左孩子
bool addLeftNode(ThreadNode* curRoot,elemType data){
?? ?ThreadNode* addNode=(ThreadNode*)malloc(sizeof(ThreadNode));
?? ?if(addNode==NULL){
?? ??? ?return false;
?? ?}
?? ?addNode->data=data;
?? ?addNode->lchild=NULL;
?? ?addNode->rchild=NULL;
?? ?addNode->ltag=0;
?? ?addNode->rtag=0;
?? ?curRoot->lchild=addNode;
?? ?return true;
}
//給指定結點增添右孩子
bool addRightNode(ThreadNode* curRoot,elemType data){
?? ?ThreadNode* addNode=(ThreadNode*)malloc(sizeof(ThreadNode));
?? ?if(addNode==NULL){
?? ??? ?return false;
?? ?}
?? ?addNode->data=data;
?? ?addNode->lchild=NULL;
?? ?addNode->rchild=NULL;
?? ?addNode->ltag=0;
?? ?addNode->rtag=0;
?? ?curRoot->rchild=addNode;
?? ?return true;
}
//先序遍歷?
void preOrder(ThreadNode* curRoot){
?? ?if(curRoot!=NULL){
?? ??? ?printf("%c ",curRoot->data);
?? ??? ?preOrder(curRoot->lchild);
?? ??? ?preOrder(curRoot->rchild);
?? ?}
}
void visit(ThreadNode* p){
?? ?if(p->lchild==NULL){
?? ??? ?p->lchild=pre;
?? ??? ?p->ltag=1;
?? ?}
?? ?if(pre!=NULL&&pre->rchild==NULL){
?? ??? ?pre->rchild=p;
?? ??? ?pre->rtag=1;
?? ?}
?? ?pre=p;
}
//先序遍歷二叉樹，一邊遍歷一邊線索化
void preThread(ThreadTree T){
?? ?if(T!=NULL){
?? ??? ?visit(T);//先處理根節點?
?? ??? ?if(T->ltag==0){//確保lchild不是前驅線索，避免出現死循環?
?? ??? ??? ?preThread(T->lchild);
?? ??? ?}
?? ??? ?if(T->rtag==0){
?? ??? ??? ?preThread(T->rchild);?? ??? ??? ?
?? ??? ?}

?? ?}
}?
//先序線索化二叉樹
void createPreThread(ThreadTree T){
?? ?pre=NULL;//pre初始化為NULL?
?? ?if(T!=NULL){//非空二叉樹才能線索化?
?? ??? ?preThread(T);//先序線索化二叉樹?
?? ??? ?if(pre->rchild==NULL){
?? ??? ??? ?pre->rtag=1;//處理遍歷最后一個結點?
?? ??? ?}
?? ?}
?? ?
}
//-----------------------------------------在先序線索二叉樹中找到指定結點p的先序后繼next----------------------------------------
ThreadNode* firstAfterRoot(ThreadNode* p){
?? ?if(p!=NULL){
?? ??? ?if(p->ltag==1){//表明左指針被線索化，沒有左子樹?
?? ??? ??? ?return p->rchild;
?? ??? ?}
?? ??? ?else{
?? ??? ??? ?return p->lchild;
?? ??? ?}
?? ?}
}
ThreadNode* findPreNext(ThreadNode* p){
?? ?if(p!=NULL){
?? ??? ?if(p->rtag==0) return firstAfterRoot(p);
?? ??? ?else return p->rchild;
?? ?}
}
//-----------------------------------------在先序線索二叉樹中找到指定結點p的先序后繼next----------------------------------------

//利用先序線索二叉樹實現非遞歸先序遍歷
void PreOrder(ThreadNode* root){
?? ?for(ThreadNode* cur=root;cur!=NULL;cur=findPreNext(cur)){
?? ??? ?printf("%c ",cur->data);
?? ?}
}
int main(){
?? ?ThreadTree root;
?? ?initTree(&root,'A');
?? ?addLeftNode(root,'B');
?? ?addRightNode(root,'C');
?? ?addRightNode(root->lchild,'D');
?? ?addLeftNode(root->rchild,'E');
?? ?printf("普通的先序遍歷:\n");
?? ?preOrder(root);
?? ?printf("\n");
?? ?
?? ?createPreThread(root);
?? ?printf("非遞歸的先序遍歷:\n");
?? ?PreOrder(root);
?? ?printf("\n");
?? ?destroyTree(root);
?? ?return 0;
}