数据结构深入剖析（11）--线索化二叉树

一、      线索化二叉树

1.    问题提出

在一些项目中需要频繁的遍历二叉树，但是二叉树的遍历比单链表的遍历复杂的多了，并且递归总是会有额外的开销。。。

2.    线索化二叉树

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

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

3.    方法

方法一：利用结点中的空指针域，使其指向后继结点。

算法思想：

初始化位置指针：p = NULL；

前序遍历二叉树：

若p不为空，将p->left指向当前结点，并将p置为NULL

若当前结点的左子树为空时，将p指向当前结点。

实现：

BTreeNode* p = NULL;

void thread_via_left(BTreeNode* root)

{

  if(root != NULL){

        if(p != NULL){

             p->left = root;

             p = NULL;

        }

        if(root->left == NULL){

             p = root;

        }

        thread_via_left(root->left);

        thread_via_left(root->right);

  }

}

方法二：利用线性表保存二叉树的遍历顺序。

算法思想：

初始化顺序表s1

前序遍历二叉树

遍历过程中将当前结点插入顺序表s1。

实现：

void thread_via_list(BTreeNode* root,SeqList* list)

{

  if((root != NULL) && (list != NULL)){

        SeqList_Insert(list,(SeqListNode*)root,SeqList_Length(list));

       

        thread_via_list(root->left,list);

        thread_via_list(root->right,list);

  }

}

二、      总结

利用结点空指针线索化的方法会破坏树的结构。

利用结点空指针线索化二叉树之后不能够再恢复。

 这两个问题可以在树结点中加入一个线索化指针而得以解决

 然而线索化指针的加入又会浪费内存空间，不够灵活

 链表线索化方法不会破化树的结构，不需要时线索化时销毁链表即可。

链表线索化方法可以很容易的以任何一种遍历顺序对二叉树进行线索化。