遍歷-如何把它改為先序線索？

如何把它改為先序線索？

#include
#include

typedef enum{Link,Thread} Pointag;//Link = 0表示指向左右孩子指針,Thread = 1表示指向前驅或後繼的線索
typedef char ElemType;

typedef struct BiThNode
{
ElemType data;
struct BiThNode *lchild,*rchild;
Pointag ltag,rtag;
}BiThNode,*BiThTree;

BiThTree Pre; //定義一個全局變量作為節點的前驅指針

//創建一顆線索二叉樹
void CreateBiThTree(BiThTree *T)
{
char c;

scanf("%c",&c);
if(' ' == c)
{
    *T = NULL;
}
else
{
    *T = (BiThTree)malloc(sizeof(BiThNode));
    (*T)->data = c;
    (*T)->ltag = (*T)->rtag = Link;                  //默認存左子樹和右子樹
    CreateBiThTree(&(*T)->lchild);
    CreateBiThTree(&(*T)->rchild);
}

}

//訪問數結點
void visit(char c)
{
printf("%c ",c);
}

//采用中序遍歷
void InTraverse(BiThTree T)
{
if(T)
{
InTraverse(T->lchild);
if(!T->lchild)

{
T->ltag = Thread;
T->lchild = Pre; //如果沒有左孩子，則讓左子樹指針指向前一個訪問的結點
}
if(!Pre->rchild)

{
Pre->rtag = Thread;
Pre->rchild = T; //前驅右孩子指針指向後繼(當前結點T)
}

    Pre = T;                          //記下當前結點
    InTraverse(T->rchild);
}

}

//設置Pre指針
void InOrderThreading(BiThTree *p,BiThTree T)
{
*p = (BiThTree)malloc(sizeof(BiThNode));
(*p)->ltag = Link;
(*p)->rtag = Thread;
(*p)->rchild = *p;

if(!T) //如果樹為空
{
(*p)->lchild = *p;
}
else
{
(*p)->lchild = T;
Pre = *p;
InTraverse(T);
Pre->rchild = *p;
Pre->rtag = Thread;
(*p)->rchild = Pre;
}
}

//中序遍歷，非遞歸
void InOrderTraversing(BiThTree T)
{
BiThTree p;
p = T->lchild; //p指向根接結點
while(p != T) //空樹或遍歷結束時 p == T
{
while(p->ltag == Link) //遍歷左子樹
{
p = p->lchild;
}
visit(p->data); //訪問結點數據
while( p->rtag == Thread && p->rchild != T)
{
p = p->rchild;
visit(p->data);
}
p = p->rchild;
}
}

int main()
{
BiThTree P,T = NULL;

CreateBiThTree(&T);

InOrderThreading(&P,T);

printf("中序輸出結果為：");

InOrderTraversing(P);

printf("\n");

return 0;

}

最佳回答：

http://blog.sina.com.cn/s/blog_7f0a4c7501017rrk.html