中序线索二叉树算法解决把二元查找树转变成排序的双向链表

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; //把前驱后继指针标记看做链表的尾结点指针很恰当，所以命名为tail
14 
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 }

中序线索二叉树算法 解决 把二元查找树转变成排序的双向链表

中序线索二叉树算法解决把二元查找树转变成排序的双向链表