1.中序线索二叉树算法，源自本科教材《数据结构》

 

typedef struct ThreadTNode{　　elemtype data；　　struct ThreadTNode *lchild, *rchild;　　int ltag, rchild;}ThreadTNode, *ThreadTree void CreateInThread ( ThreadTree T ){ 　　ThreadTree pre = NULL;　　 if( T != NULl )　　 {  　　　　InThread( T, pre ); 　　　　 pre->rchild = NULL;  　　　　pre->rtag = 1; 　　}}void InThread ( ThreadTree p, ThreadTree pre ){　　 if( p ) 　　{  　　　　InThread ( p->lchild, pre );//说pre是前驱标记是正确的，说它是后继标记也是正确的，  　　　　if( p->lchild == NULL ) 　　　　 {   　　　　　　p->lchild = pre;   　　　　　　p->ltag = 1;  　　　　} 　　　　 if( pre && pre->rchild == NULL ) 　　　　 {  　　　　　　 pre->rchild = p;  　　　　　　 pre->rtag = 1;  　　　　} 　　　　 pre = p;  　　　　InThread( p->rchild, pre ); 　　}}

 

2.把二元查找树转变成排序的双向链表，源自微软的笔试题

 

1 typedef struct BSTNode 2 { 3 　　elemtype data； 4  5 　　struct BSTNode *lchild, *rchild; 6  7 }BSTNode, *BSTree 8  9 void Convert( BSTree T ) 10 {11 　　 if( T )12 　　 {13  　　　　 BSTree tail = NULL; //把前驱后继指针标记看做链表的尾结点指针很恰当，所以命名为tail14 15   　　　　ConvertBST( tail, T ); // 把T转换成链表后连接到tail上，tail为链表当前尾结点指针16  17   　　　　tail->rchild = NULL;18 　　 }19 }20 21 void ConvertBST( BSTree tail, BSTree p )22 {23  　　if( p )24  　　{25  　　　　 ConvertBST( tail, p->lchild );26 27  　　　　 p->lchild = tail;28 29 30 　　　　  if( tail )31   　　　　　　tail->rchild = p;32   33   　　　　tail = p;34 35   　　　　ConvertBST( tail, p->rchild );36  　　}37 }