线索二叉树

旧城等待， 2022-02-23 08:36 248阅读 0赞

本文主要介绍**线索二叉树**和**树、二叉树、森林**三者之间的相互转换。

对于线索二叉树，这里只做简单介绍，着重还是要理解上篇博文中二叉树的各种遍历算法。

## 线索二叉树 ##

### 基本概念 ###

遍历二叉树的**实质就是对一个非线性结构进行线性化操作**，使在这个访问序列中每一个结点（除第一个和最后一个）都有一个**直接前驱和直接后继**。

传统的链式存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱和后继。通过观察，我们发现在二叉链表表示的二叉树中存在大量的空指针，若利用这些空链域存放指向其直接前驱或后继的指针，则可以方便的运用某些二叉树操作算法。**引入线索二叉树的目的是为了加快查找结点前驱和后继的速度**。

在二叉树线索化时，通常规定：

1.  若无左子树，令 l c h i l d lchild lchild指向其前驱结点，若无右子树，令 r c h i l d rchild rchild指向其后继结点
2.  还需增加两个标志域表明当前指针域所指的对象是指向左（右）子结点还是直接前驱（后继）

![1.jpg][]

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

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

### 线索二叉树的构造 ###

对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左、右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。

下面以**中序线索二叉树**建立为例，指针 p r e （ s u c ） pre（suc） pre（suc）指向中序遍历时上一个刚访问过（下一个访问）的结点，如下图所示（**中序遍历为 B D A E C**）：

![2.jpg][]

**下面给出中序遍历时对二叉树线索化的递归算法**

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

**调用上述方法，建立中序线索二叉树的主过程**

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

## 树、森林、二叉树的相互转换 ##

在介绍转换方法前，我们先来看一下树的存储结构

![3.jpg][]

### 树 -----> 二叉树 ###

![4.jpg][]

### 森林 -----> 二叉树 ###

![5.jpg][]

### 二叉树 -----> 树 ###

![6.png][]  
![7.jpg][]

### 二叉树 -----> 森林 ###

![8.jpg][]

**树和森林的遍历可采用对应二叉树遍历算法实现**，与二叉树遍历的对应关系如下表所示：

[1.jpg]: /images/20220223/eaae1a7089624e1cbd314e33e11634fa.png
[2.jpg]: /images/20220223/7d5c345951654f38990b07b4719c8788.png
[3.jpg]: /images/20220223/4c6e773d9cae48a0b34da6e8bf7aedbe.png
[4.jpg]: /images/20220223/1d2404f017fb4642ba0531cdff873c85.png
[5.jpg]: /images/20220223/bba8504737394e99b493c2bd992dd8b3.png
[6.png]: /images/20220223/7223b0094b9548db8a8a8a87d457e98c.png
[7.jpg]: /images/20220223/fc92c4867f9d43b8a28c320a6a0626ae.png
[8.jpg]: /images/20220223/80f0af340b904551b3f01d87e26c4192.png