线索二叉树

一、线索二叉树由来

由于普通的二叉树的缺陷导致了空间的巨大浪费，如：

数序题：请问以下有多少个“^”？总共浪费了多少字节的空间？(32bit的机器)

普通二叉树的空间浪费.png

我们知道通过对二叉树的约定遍历方式，可以得到一个固定的遍历顺序，那么请问哪种遍历方式可以节省“^{”所浪费的空间？（利用“}”记录该结点的前驱后继）

普通二叉树的空间浪费.png

经过分析可以得出，上图经过中序遍历后结果是：HDIBEAFCG

我们发现红色的结点都是刚才“^{”造成浪费的结点，利用中序遍历刚好它们均处于字符中间，可以很好地利用“}”来存放前驱和后继的指针。

如图：黑色曲线存放前驱，红色直线存放后继。

使null利用起来.png

但不是所有的二叉树的中序遍历都能得到刚好只隔一个结点就有一个结点属于前驱和后继都为空的情况，如图：

特殊情况.png

上图经过中序遍历后结果是：FDGBACE

如果是这样的话我们就面临一个问题：机器怎么识别到底是存放指针还是线索？
机器此时只需要一点提示，为此我们将已经定义好的结构进行“扩容”：

扩容结点结构.png

• ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
• rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

二、线索二叉树代码实现

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

// 线索存储标志位
// Link(0)：表示指向左右孩子的指针
// Thread(1)：表示指向前驱后继的线索
typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode
{
    char data;
    struct BiThrNode *lchild, *rchild;
    PointerTag ltag;
    PointerTag rtag;
} BiThrNode, *BiThrTree;

// 全局变量，始终指向刚刚访问过的结点
BiThrTree pre;

// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiThrTree( BiThrTree *T )
{
    char c;

    scanf("%c", &c);
    if( ' ' == c )
    {
        *T = NULL;
    }
    else
    {
        *T = (BiThrNode *)malloc(sizeof(BiThrNode));
        (*T)->data = c;
        (*T)->ltag = Link;
        (*T)->rtag = Link;

        CreateBiThrTree(&(*T)->lchild);
        CreateBiThrTree(&(*T)->rchild);
    }
}

// 中序遍历线索化
void InThreading(BiThrTree T)
{
    if( T )
    {
        InThreading( T->lchild );       // 递归左孩子线索化

        if( !T->lchild )    // 如果该结点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点。
        {
            T->ltag = Thread;
            T->lchild = pre;
        }

        if( !pre->rchild )
        {
            pre->rtag = Thread;
            pre->rchild = T;
        }

        pre = T;

        InThreading( T->rchild );       // 递归右孩子线索化
    }
}

void InOrderThreading( BiThrTree *p, BiThrTree T )
{
    *p = (BiThrTree)malloc(sizeof(BiThrNode));
    (*p)->ltag = Link;
    (*p)->rtag = Thread;
    (*p)->rchild = *p;
    if( !T )
    {
        (*p)->lchild = *p;
    }
    else
    {
        (*p)->lchild = T;
        pre = *p;
        InThreading(T);
        pre->rchild = *p;
        pre->rtag = Thread;
        (*p)->rchild = pre;
    }
}

void visit( char c )
{
    printf("%c", c);
}

// 中序遍历二叉树，非递归
void InOrderTraverse( BiThrTree T )
{
    BiThrTree p;
    p = T->lchild;

    while( p != T )
    {
        while( p->ltag == Link )
        {
            p = p->lchild;
        }
        visit(p->data);

        while( p->rtag == Thread && p->rchild != T )
        {
            p = p->rchild;
            visit(p->data);
        }
        
        p = p->rchild;
    }
}

int main()
{
    BiThrTree P, T = NULL;

    CreateBiThrTree( &T );

    InOrderThreading( &P, T );

    printf("中序遍历输出结果为: ");

    InOrderTraverse( P );

    printf("\n");

    return 0;
}