数据结构二叉树线索化

  线索化二叉树指的是将二叉树中的结点进行逻辑意义上的“重排列”，使其可以线性的方式访问每一个结点。二叉树线索化之后每个结点都有一个线性下标，通过这个下标可以快速访问结点，而不需要遍历二叉树。

 

                   

           

            代码：

          

[cpp] view plain copy

1. void thread_via_left(BTreeNode* root, BTreeNode** pp)  
2. {  
3.     if((NULL!=root) && (NULL!=pp))  
4.     {  
5.         if(NULL != (*pp))  
6.         {  
7.             (*pp)->left = root;  
8.             *pp = NULL;  
9.         }     
10.           
11.         if(NULL == root->left)  
12.         {  
13.             *pp = root;  
14.         }  
15.           
16.         thread_via_left(root->left, pp);  
17.         thread_via_left(root->right, pp);  
18.     }  
19. }  

 

 

           代码：

           

[cpp] view plain copy

1. void thread_via_list(BTreeNode* root, SeqList* list)  
2. {  
3.     if((NULL!=root) && (NULL!=list))  
4.     {  
5.         SeqList_Insert(list, (SeqListNode*)root, SeqList_Length(list));  
6.           
7.         thread_via_list(root->left, list);  
8.         thread_via_list(root->right, list);  
9.     }  
10. }  

 

           最后做一下小结：