您的位置: 首页  >  文章  >  线索二叉树

线索二叉树

分类: 文章 • 2025-02-24 13:33:28

一、线索二叉树

       如果二叉树的节点包含数据域和两个指针域( lchild 和 rchild )，当节点没有下一个节点时，将指针域赋值为空(NULL)，但有时会造成很大的浪费，所以可以将空指针域利用起来，存放其他节点的地址，这样就便于索引，像二叉树遍历，查找之类就会变得相对容易。

线索二叉树

像上面的二叉树就会造成很大的浪费。当该二叉树以中序遍历输出时，为FDGBACE，红色表示有两个指针域可以利用，蓝色表示有一个指针域可以利用，而黑色表示没有多余的指针域可以利用，若果将一个节点的lchild(如果可以使用)指向它前一个节rchlid(如果可以使用)指向它的后一个节点(这里的前后是针对于FDGBACE这个序列而言的)。而假若在最前面增加一个头结点，数据域为data，那么会更加便捷。最终它们的指向会变为：

线索二叉树

这样的对于中序遍历二叉树就会变得很容易。

然而，机器怎么判断一个节点到底有多少个指针域可以使用呢？这样就需要一个标志，指示该节点的两个指针域是否可以被利用，于是，我们把节点扩容，变为：

线索二叉树

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

这样就能分别指示左右指针域是否可以利用。虽然牺牲了一点空间，但换来的是效率的提高。

二、代码实现

[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.   
  4. typedef char ElemType;  
  5.   
  6. // 线索存储标志位  
  7. // Link(0)：表示指向左右孩子的指针  
  8. // Thread(1)：表示指向前驱后继的线索  
  9. typedef enum {Link, Thread} PointerTag;  
  10.   
  11. typedef struct BiThrNode  
  12. {  
  13.     char data;  
  14.     struct BiThrNode *lchild, *rchild;  
  15.     PointerTag ltag;  
  16.     PointerTag rtag;  
  17. } BiThrNode, *BiThrTree;  
  18.   
  19. // 全局变量，始终指向刚刚访问过的结点  
  20. BiThrTree pre;  
  21.   
  22. // 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据  
  23. void CreateBiThrTree( BiThrTree *T )  
  24. {  
  25.     char c;  
  26.   
  27.     scanf("%c", &c);  
  28.     if( ' ' == c )  
  29.     {  
  30.         *T = NULL;  
  31.     }  
  32.     else  
  33.     {  
  34.         *T = (BiThrNode *)malloc(sizeof(BiThrNode));  
  35.         (*T)->data = c;  
  36.         (*T)->ltag = Link;  
  37.         (*T)->rtag = Link;  
  38.   
  39.         CreateBiThrTree(&(*T)->lchild);  
  40.         CreateBiThrTree(&(*T)->rchild);  
  41.     }  
  42. }  
  43.   
  44. // 中序遍历线索化  
  45. void InThreading(BiThrTree T)  
  46. {  
  47.     if( T )  
  48.     {  
  49.         InThreading( T->lchild );        // 递归左孩子线索化  
  50.   
  51.         if( !T->lchild ) // 如果该结点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点。  
  52.         {  
  53.             T->ltag = Thread;  
  54.             T->lchild = pre;  
  55.         }  
  56.   
  57.         if( !pre->rchild )  
  58.         {  
  59.             pre->rtag = Thread;  
  60.             pre->rchild = T;  
  61.         }  
  62.   
  63.         pre = T;  
  64.   
  65.         InThreading( T->rchild );        // 递归右孩子线索化  
  66.     }  
  67. }  
  68.   
  69. void InOrderThreading( BiThrTree *p, BiThrTree T )  
  70. {  
  71.     *p = (BiThrTree)malloc(sizeof(BiThrNode));  
  72.     (*p)->ltag = Link;  
  73.     (*p)->rtag = Thread;  
  74.     (*p)->rchild = *p;  
  75.     if( !T )  
  76.     {  
  77.         (*p)->lchild = *p;  
  78.     }  
  79.     else  
  80.     {  
  81.         (*p)->lchild = T;  
  82.         pre = *p;  
  83.         InThreading(T);  
  84.         pre->rchild = *p;  
  85.         pre->rtag = Thread;  
  86.         (*p)->rchild = pre;  
  87.     }  
  88. }  
  89.   
  90. void visit( char c )  
  91. {  
  92.     printf("%c", c);  
  93. }  
  94.   
  95. // 中序遍历二叉树，非递归  
  96. void InOrderTraverse( BiThrTree T )  
  97. {  
  98.     BiThrTree p;  
  99.     p = T->lchild;  
  100.   
  101.     while( p != T )  
  102.     {  
  103.         while( p->ltag == Link )  
  104.         {  
  105.             p = p->lchild;  
  106.         }  
  107.         visit(p->data);  
  108.   
  109.         while( p->rtag == Thread && p->rchild != T )  
  110.         {  
  111.             p = p->rchild;  
  112.             visit(p->data);  
  113.         }  
  114.           
  115.         p = p->rchild;  
  116.     }  
  117. }  
  118.   
  119. int main()  
  120. {  
  121.     BiThrTree P, T = NULL;  
  122.   
  123.     CreateBiThrTree( &T );  
  124.   
  125.     InOrderThreading( &P, T );  
  126.   
  127.     printf("中序遍历输出结果为: ");  
  128.   
  129.     InOrderTraverse( P );  
  130.   
  131.     printf("\n");  
  132.   
  133.     return 0;  
  134. }  

三、效果展示

线索二叉树

相关推荐