中序線索二叉樹

就是在中序遍歷的時候加上線索，為了區分線索和孩子，要多加兩個標志變量ltag，rtag如果標志為true就表明是線索，

如果為false就表示孩子；

一般規定是將做指針為空的指針域用來存放直接前驅；

將有指針為空的指針域用來存放直接後繼；當然如果不為空的話就不會用來存放前後繼，而是孩子了

意思就是存放前繼的是左指針，存放後繼的是右指針，一般規定這樣寫，

基本思路是新設兩個結點，一個頭結點Head，一個輔助結點pre;

頭結點左指針指向根結點，右指針指向某種遍歷順序的最後一個結點，最後一個結點的右指針指向頭結點

pre指針讓其一直指向當前結點的直接前驅；

下面是憑感覺寫的，給個思路和思想，沒有測試，如果有錯望指正：

[cpp] 
typedef char Elem;    
typedef struct Node 
{ 
    Elem data; 
    struct Node *lchild,*rchild; 
    bool rtag,ltag;    //左右標記 true代表線索,false代表孩子  
}*Tree;  
 
void XianSuoTree(Tree T) 
{ 
    Tree Head,pre; 
    Head =new struct Node;   //初始化頭結點  
    pre =new struct Node;//初始化pre結點  
    Head->ltag=false;   //初始化頭結點左標志  
    Head->rtag=true;    
    Head->lrchild=T;   //做指針指向根結點  
    head->rchild=head;    //又指針回指  
    pre=Head;       //是pre指針作為根結點的直接前驅  
    BianLi(T,pre);   //中序遍歷  
    pre->rtag=true;   //將遍歷中的最後一個結點右標志值為true  
    pre->lchild=Head;   //最後一個結點右孩子指向頭結點  
    Head->lchild=pre;  //頭結點的右孩子指向中序遍歷的最後一個結點，使之具有循環線索關系  
} 
 
void BianLi(Tree p,Tree pre)  //p為當前結點，pre為當前節點的直接前驅  
{ 
    BianLi(p->lchild,pre)   //中序遍歷左子樹  
    if(!p->lchild)    //判斷做孩子情況，如果為空則將左指針指向其直接前驅  
    { 
        p->ltag=true; 
        p->lchild=pre; 
    } 
    if(!pre->rchild)    //判斷pre的右孩子情況，如果為空則將其有指針指向其直接後繼  
    { 
        pre->rtag=true; 
        pre->rchild=p; 
    } 
    pre=p;  //保證pre始終為當前結點的直接前驅  
    BianLi(p->rchild,pre);  //中序遍歷右子樹  
} 

typedef char Elem;  
typedef struct Node
{
 Elem data;
 struct Node *lchild,*rchild;
 bool rtag,ltag;    //左右標記 true代表線索,false代表孩子
}*Tree;

void XianSuoTree(Tree T)
{
 Tree Head,pre;
 Head =new struct Node;   //初始化頭結點
 pre =new struct Node;//初始化pre結點
 Head->ltag=false;   //初始化頭結點左標志
 Head->rtag=true;  
 Head->lrchild=T;   //做指針指向根結點
 head->rchild=head;    //又指針回指
 pre=Head;       //是pre指針作為根結點的直接前驅
 BianLi(T,pre);   //中序遍歷
 pre->rtag=true;   //將遍歷中的最後一個結點右標志值為true
 pre->lchild=Head;   //最後一個結點右孩子指向頭結點
 Head->lchild=pre;  //頭結點的右孩子指向中序遍歷的最後一個結點，使之具有循環線索關系
}

void BianLi(Tree p,Tree pre)  //p為當前結點，pre為當前節點的直接前驅
{
 BianLi(p->lchild,pre)   //中序遍歷左子樹
 if(!p->lchild)    //判斷做孩子情況，如果為空則將左指針指向其直接前驅
 {
  p->ltag=true;
  p->lchild=pre;
 }
 if(!pre->rchild)    //判斷pre的右孩子情況，如果為空則將其有指針指向其直接後繼
 {
  pre->rtag=true;
  pre->rchild=p;
 }
 pre=p;  //保證pre始終為當前結點的直接前驅
 BianLi(p->rchild,pre);  //中序遍歷右子樹
}