Chinaunix首页 | 论坛 | 博客
  • 博客访问: 251540
  • 博文数量: 52
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1538
  • 用 户 组: 普通用户
  • 注册时间: 2013-04-24 07:45
个人简介

生活就像海洋,只有意志坚强的人,才能到达彼岸。

文章存档

2013年(52)

分类: C/C++

2013-09-04 08:58:15

    线索化二叉树指的是将二叉树中的结点进行逻辑意义上的“重排列”,使其可以线性的方式访问

每一个结点。二叉树线索化之后每个结点都有一个线性下标,通过这个下标可以快速访问结点,而不

需要遍历二叉树。线索化二叉树有两种方法:

1、利用结点中的空指针域,使其指向后继结点。



算法思想:
    
    初始化位置指针:p = NULL

    前序遍历二叉树:若p不为空,将p->left指向当前结点,并将p置为NULL;若当前结点的左子树为空时,将p指向当前结点
    

2、利用线性表保存二叉树的遍历顺序


算法思想:

    初始化顺序表s1;

    前序遍历二叉树:遍历过程中将当前结点插入顺序表s1(借助之前实现的顺序表)


点击(此处)折叠或打开

  1. /**实现代码ThreadBTree.c**/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include "BTree.h"
  5. #include "SeqList.h"

  6. /* run this program using the console pauser or add your own getch, system("pause") or input loop */

  7. struct Node
  8. {
  9.     BTreeNode header;
  10.     char v;
  11. };

  12. void printf_data(BTreeNode* node)
  13. {
  14.     if( node != NULL )
  15.     {
  16.         printf("%c", ((struct Node*)node)->v);
  17.     }
  18. }


  19. void thread_via_left(BTreeNode* root, BTreeNode** pp)
  20. {
  21.     if( (root != NULL) && (pp != NULL) )
  22.     {
  23.         if( *pp != NULL )
  24.         {
  25.             (*pp)->left = root;
  26.             
  27.             *pp = NULL;
  28.                 
  29.         }
  30.         
  31.         if( root->left == NULL )
  32.         {
  33.             *pp = root;
  34.         }
  35.         
  36.         thread_via_left(root->left,pp);
  37.         thread_via_left(root->right,pp);
  38.     }
  39. }

  40. void thread_via_list(BTreeNode* root, SeqList* list)
  41. {
  42.     if( (root != NULL) && (list != NULL))
  43.     {
  44.         SeqList_Insert(list,(SeqListNode*)root,SeqList_Length(list));
  45.         thread_via_list(root->left,list);
  46.         thread_via_list(root->right,list);
  47.     }
  48.         
  49. }

  50. int main(int argc, char *argv[])
  51. {
  52.     BTree* tree = BTree_Create();
  53.     BTreeNode* current = NULL;
  54.     BTreeNode* p = NULL;
  55.     SeqList* list = NULL;
  56.     int i = 0 ;
  57.     
  58.     struct Node n1 = {{NULL, NULL}, 'A'};
  59.     struct Node n2 = {{NULL, NULL}, 'B'};
  60.     struct Node n3 = {{NULL, NULL}, 'C'};
  61.     struct Node n4 = {{NULL, NULL}, 'D'};
  62.     struct Node n5 = {{NULL, NULL}, 'E'};
  63.     struct Node n6 = {{NULL, NULL}, 'F'};
  64.     
  65.     BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);
  66.     BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);
  67.     BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);
  68.     BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);
  69.     BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);
  70.     BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);
  71.     
  72.     printf("Full Tree: \n");
  73.     
  74.     BTree_Display(tree, printf_data, 4, '-');
  75.     
  76.     printf("Thread via list: \n");
  77.     
  78.     list = SeqList_Create(BTree_Count(tree));
  79.     
  80.     thread_via_list(BTree_Root(tree),list);
  81.     
  82.     for(i=0; i<SeqList_Length(list);i++)
  83.     {
  84.         printf("%c,", ((struct Node*)SeqList_Get(list,i))->v);
  85.     }
  86.     
  87.     printf("\n");
  88.     
  89.     printf("Thread via Left: \n");
  90.     
  91.     current = BTree_Root(tree);
  92.     
  93.     thread_via_left(current,&p);
  94.     
  95.     while( current != NULL )
  96.     {
  97.          printf("%c,", ((struct Node*)current)->v);
  98.          
  99.          current = current->left;
  100.     }
  101.     
  102.     printf("\n");
  103.     
  104.     BTree_Destroy(tree);
  105.     printf("please enter to continue...");
  106.     getchar();
  107.     return 0;
  108. }




小结:
1>利用结点空指针线索化的方法会破坏树的结构;利用结点空指针线索化二叉树之后不能够再恢复,

这两个问题可以在树结点中加入一个线索化指针而得以解决,然而线索化指针的加入又会浪费内存空

间,不够灵活;

2>链表线索化方法不会破坏树的结构不需要时线索化时销毁链表即可;链表线索化方法可以很容易的

以任何一种遍历顺序对二叉树进行线索化。
阅读(2328) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~