其中标志域含义如下：

• ltag
  • 0 lchild域指示结点的左孩子
  • 1 lchild域指示结点的前驱
• rtag
  • 0 rchild域指示结点的右孩子
  • 1 rchild域指示结点的后继

线索二叉树的存储结构描述如下：

typedef struct ThreadNode {
    ElemType data; //数据元素
    struct ThreadNode *lchild,*rchild; //左、 右孩子指针
    int ltag,rtag; //左、 右线索标志
} ThreadNode,*ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。
其中指向结点前驱和后继的指针，叫做线索。
加上线索的二叉树称为线索二叉树。
对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

（2）线索二叉树的构造

对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检査当前结点左、右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。
以中序线索二叉树的建立为例，指针 pre 指向中序遍历时上一个刚刚访问过的结点，用它来表示各结点访问的前后关系，如图 4-10 所示。

通过中序遍历对二叉树线索化的递归算法如下：

void InThread(ThreadTree Sp,ThreadTree &pre) {
//中序遍历对二叉树线索化的递归算法
    if(p != NULL) {
        InThread(p->lchild,pre); //递归，线索化左子树
        if(p->lchild == NULL){ //左子树为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != NULL && pre->rchild==NULL) {
            pre->rchild = p; //建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = p; //标记当前结点成为刚刚访问过的结点
        InThread(p->rchild,pre); //递归，线索化右子树
    }//if(p!=NULL)
}

通过中序遍历建立中序线索二叉树的主过程算法如下：

void CreatelnThread(ThreadTree T) {
    ThreadTree pre NULL;
    if(T != NULL){ //非空二叉树，线索化
        InThread(T,pre); //线索化二叉树
        pre->rchild = NULL; //处理遇历的最后一个结点
        pre->rtag = 1;
    }
}

有时为了方便，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点（见图 4-11），并令其 lchild 域的指针指向二叉树的根结点，其 rchild 域的指针指向中序遍历时访问的最后一个结点；
反之，令二叉树中序序列中的第一个结点的 lchild 域的指针和最后一个结点 rchild域的指针均指向头结点。
这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。

（3）线索二叉树的遍历

中序线索化二叉树主要是为访问运算服务的，这种遍历不再需要借助栈，因为它的结点中隐含了线索二叉树的前驱和后继信息。
利用线索二叉树，可以实现二叉树遍历的非递归算法。
不含头结点的线索二叉树的遍历算法如下：

1. 求中序线索二叉树中中序序列下的第一个结点：
   ThreadNode *Firstnode(ThreadNode *p) { while(p->ltag==0) p=p->lchild; //最左下结点（不一定是叶结点） return p； }
2. 求中序线索二叉树中结点 p 在中序序列下的后继结点：
   ThreadNode *Nextnode(ThreadNode *p) { if(p_>rtag==0) return Firstnode(p->rchild); else return p->rchild; //rtag~l 直接返回后继线索 }
   请读者自行分析并完成求中序线索二叉树的最后一个结点和结点 p 前驱结点的运算。
3. 利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法：
   void Inorder(ThreadNode *T) { for(ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p)) visit(p); }

4.4 树、森 林

4.4.1 树的存储结构

树的存储方式有多种，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映出树中各结点之间的逻辑关系，这里介绍 3 种常用的存储结构。

1. 双亲表示法
   这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。
   如图 4-13 所示，根结点下标为 0,其伪指针域为 -1。
   

   

（编辑：南平站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!