线索二叉树

秒速五厘米 2022-05-29 00:18 193阅读 0赞

二叉树的链式存储如下图，

![Image 1][]

不难发现，图中所示的左—右指针表示中，有一半以上的指针是空的。事实上，所有包括n个结点的二叉树的这种表示中，每个结点有两个指针，一共有2n个指针，其中除根结点外，每个结点都被一个指针所指，所以只有n-1个指针不为空，而另外的n+1和指针为空。

另外，遍历是二叉树许多操作的基础，经常使用，但是一般的遍历算法需要大约O（n）的时间代价，如此多次反复进行遍历也是时间的严重浪费。因此，如果在第一次遍历时，能够把遍历的信息保存在二叉树的空指针中，在重复遍历二叉树时就可以利用这些信息，节省大量的时间，也是空指针得到充分利用。

如何保存遍历的信息？就是对左—右指针表示法的一种修改。利用结点的空的左指针（llink）储存该结点在某种遍历序列中的前驱结点的位置；利用结点的空的右指针（rlink）储存该节点在同种遍历序列中的后继节点的位置。这种附加的指向前驱结点和后继节点的指针称作线索，这种二叉树即线索二叉树。

如何构造线索二叉树呢？可根据不同的遍历方法构造不同的线索二叉树，下面讨论中序遍历构造的二叉树。为了区分左、右指针和线索，需要对每个结点增加两个标志位ltag和rtag，定义如下，![Image 1][]

构造线索二叉树，即是非递归遍历一遍二叉树，这就需要一个栈结构，用来保存遍历过程中需要回溯的结点的指针。下面算法中，p指向正在访问的结点，pre指向它的中序前驱，即上一次刚访问过的结点，这里的“访问”是指把当前结点的左指针和中序前驱结点的右指针改为左线索和右线索。中序线索二叉树如下，

![Image 1][]

构造中序线索二叉树的意义在于，可以方便地从中找到指定结点在中序序列中的前驱和后继，而不必周游二叉树。而且，非递归地遍历二叉树时，不需要借用栈（需要借用栈的遍历方法见 http://blog.csdn.net/gnosed/article/details/78164272 ），具体算法和程序样例如下，

#include <iostream>
    #include <stack>
    #include <cstring>
    #include <cstdio>
    #define MAXN 100
    #define DataType char
    
    using namespace std;
    
    typedef struct ThrTreeNode* pThrTreeNode;
    typedef struct ThrTreeNode* pThrTree;
    struct ThrTreeNode{
        DataType info;
        pThrTreeNode llink,rlink;
        int ltag,rtag;
    };
    
    void Thread(pThrTree t)
    {
        stack<pThrTree> s;
        pThrTree p = t, pre = NULL;
        if(t == NULL)   return;
        do{
            while(p){                   //遇到结点压入栈，然后进入其左子树
                s.push(p);  p=p->llink;
            }
            p=s.top();  s.pop();
            if(pre){
                if(pre->rlink == NULL){ //修改前驱结点的右指针
                    pre->rlink = p;
                    pre->rtag = 1;
                }
                if(p->llink == NULL){   //修改该节点的左指针
                    p->llink = pre;
                    p->ltag = 1;
                }
            }
            pre = p; p=p->rlink;
        }while(!s.empty() || p);
    }
    
    void ThreadInOrder(pThrTree t)            //按中序遍历周游中序线索二叉树
    {
        pThrTree p =t;
        if(t == NULL)   return;
        while(p->llink !=NULL && p->ltag == 0)  p=p->llink;
                                        //顺左子树一直向下
        while(p != NULL){
            cout<<p->info;              //访问
            if(p->rlink !=NULL && p->rtag == 0){
                                        //右子树不是线索时
                p=p->rlink;
                while(p->llink !=NULL && p->ltag == 0)  p=p->llink;
                                        //顺右子树的左子树一直向下
            }
            else    p=p->rlink;         //顺线索向下
        }
    }
    
    pThrTree CreateBinTree(char seq[],int &i,int k){
                                        //创建普通二叉树
       if(i>k||seq[i]=='#')
           return NULL;
       pThrTreeNode p=new struct ThrTreeNode;
       if(p!=NULL){
           p->info=seq[i];
           p->ltag=p->rtag=0;           //初始化标志量
           i++;
           p->llink=CreateBinTree(seq,i,k);
           i++;
           p->rlink=CreateBinTree(seq,i,k);
           return p;
        }
        return NULL;
    }
    int main()
    {
        char seq[MAXN];
        scanf("%s",seq);
        int k=0;
        pThrTree t = CreateBinTree(seq, k, strlen(seq)-1);
        Thread(t);
        ThreadInOrder(t);
        return 0;
    }

INPUT:

ABC##D##EF#GH##I###

OUTPUT:

CBDAFHGIE

上面程序首先构造普通的二叉树（利用先序序列构建，具体说明 http://blog.csdn.net/gnosed/article/details/78462100 ），

然后，线索化二叉树，最后按中序遍历周游中序线索二叉树，通过验证，遍历的序列正确。

[Image 1]: