二叉树中序线索化（递归）

68 阅读 0 评论 45 点赞

我是靠谱客的博主害怕面包，最近开发中收集的这篇文章主要介绍二叉树中序线索化（递归），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法：与中序遍历算法类似，只要将遍历算法中访问结点的操作具体为把当前访问的结点与其非空中序前驱结点线索化。

设置一前驱结点pre（初始值为NULL)，始终指向刚刚访问过的结点；设置p指针指向当前正在访问的结点。pre为p的前驱，而p为pre的后继。

 
     01typedef enum{Link,Thread}PointerTag;
 
     02typedef struct node{
 
     03        ElemType data;
 
     04        PointerTag ltag,rtag;
 
     05        struct node lchild,rchild;
 
     06} *BinTree;
 
     07BinTree pre=NULL;
 
     08void InOrderThreading(BinTree t)
 
     09{
 
     10    if(t)
 
     11    {
 
     12        InOrderThreading(t->lchild);//左子树线索化
 
     13        //以下建立正在访问结点与其前驱结点之间的线索
 
     14        t->ltag=(t->lchild)?Link:Thread;
 
     15        t->rtag=(t->rchild)?Link:Thread;
 
     16        if(pre)
 
     17        {
 
     18             if(pre->rtag==Thread)
 
     19                 pre->rchild=t;
 
     20             if(t->ltag==Thread)
 
     21                 t->lchild=pre;
 
     22        }
 
     23        pre=t;
 
     24        InOrderThreading(t->rchild);//右子树线索化
 
     25    }
 
     26}