数据结构(13)-线索化二叉树

首先我们来看一张图，这是我们上一篇二叉树的链式存储结构示意图。

二叉树链式结构.png

从图中可以看出来，有很多指针域是用^表示的，这是因为对应的指针域并没有指向，这样对内存空间确实是一个很大的浪费。对于一个有n个结点的二叉树，一共会有2n个结点，而n个结点有n-1条分支，所以会有2n-(n-1) = n+1个空指针域。

当我们想要知道一个结点在前序遍历序列中的前驱结点和后继结点的时候只能通过遍历二叉树才能知道，那么我们是否可以通过这些空指针域来做记录从而达到节省内存空间的目的呢？答案是肯定的，我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。对二叉树进行某种次序的遍历，使其变为线索二叉树的过程称为线索化。下面我们就通过对中序遍历的二叉树示意图进行分析来看看如何线索化二叉树。

线索化二叉树中序.png

这样就会存在一个问题，即如何区别某一个指针域是前驱还是左孩子、是后继还是右孩子。所以我们还需要使用一个标志来区分，我们可以在每一个结点增设两个标志域leftTag和rightTag，这两个标志域只是布尔型变量，占用内存量比较小。结点结构如下：

            | `leftChild` | `leftTag` | `data` | `rightTag` | `rightChild` |

leftTag为0时，指向该结点的左孩子，为1时指向该结点的前驱
rightTag为0时，指向该结点的右孩子，为1时指向该结点的后继

修改之后就变成下面的样子：

线索二叉树2.png

可以看出，我们只需要在对二叉树进行中序遍历的时候就可以对其进行线索化处理。处理的方式就是判断当前结点是否有左孩子，如果没有就将其leftChild指向前驱结点，然后把leftTag标志为1，如果有就进行下一步；接着判断前驱结点是否有右孩子，如果没有则将rightChild指向其后继结点也就是当前结点，然后将rightTag置为1。下面我们来看看链式存储结构线索二叉树的相关代码。

首先结点的结构发生了变化，多了两个标志位。

typedef char ElementType;
typedef enum {
    isChild,  // 指针域保存的是左右孩子
    isThread  // 指针域保存的是前驱后继结点
} NodeTag;

typedef struct BinaryNode {
    ElementType data;
    struct BinaryNode *leftChild, *rightChild;
    NodeTag leftTag, rightTag;
} BinaryNode, *BinaryTree;

线索化二叉树必须是在树已经已经生成之后，线索化代码如下：

// 全局变量,始终指向刚刚访问过的结点
BinaryTree preTree;
void inOrderThreadBinaryTree(BinaryTree bt) {
    if (bt == NULL) {
        return;
    }
    
    inOrderTraverse(bt->leftChild);
    
    if (bt->leftChild) {
        // 存在左孩子
        bt->leftTag = isChild;
    } else {
        // 不存在左孩子 就将leftChild设置为前驱
        bt->leftTag = isThread;
        bt->leftChild = preTree;
    }
    
    if (!preTree->rightChild) {
        // 如果前驱不存在右孩子 将前驱的后继指向当前结点 修改标志位
        preTree->rightChild = bt;
        preTree->rightTag = isThread;
    } else {
        preTree->rightTag = isChild;
    }
    
    preTree = bt;

    inOrderTraverse(bt->rightChild);
}

可以看出先在遍历线索二叉树的时候，其操作类似于双向链表，所以我们可以为其添加一个头结点进行优化。这个头结点的左孩子指向根结点，而右孩子(后继)指向中序遍历的最后一个结点；中序遍历的第一个结点的左孩子(前驱)指向头结点；中序遍历的最后一个结点的右孩子(后继)指向头结点。

void inOrderThreadBinaryTree1(BinaryTree *p, BinaryTree bt) {
    // 创建一个头结点
    *p = (BinaryTree)malloc(sizeof(BinaryNode));
    if (!p) {
        exit(0);
    }
    
    // 头结点的左孩子指向根结点
    // 中序遍历的第一个结点的左孩子(前驱)指向头结点
    (*p)->leftTag = isChild;
    (*p)->rightTag = isThread;
    (*p)->leftChild = bt;
    
    if (!bt ) {
        return;
    } else {
        (*p)->leftChild = bt;
        preTree = (*p);
        
        inOrderThreadBinaryTree(bt);
        
        // 中序遍历的最后一个结点的右孩子(后继)指向头结点
        preTree->rightChild = (*p);
        preTree->rightTag = isThread;
        
        // 头结点的右孩子(后继)指向中序遍历的最后一个结点
        (*p)->rightChild = preTree;
    }
}

由于加入了头结点，我们就可以使用线索二叉树的特点来进行遍历，而不是递归方式。比如我们需要中序遍历，只需要从头结点开始遍历左子树，当左子树的leftTag == isThread，就说明到了左子树的最后一个叶子(即中序遍历的第一个结点)，开始打印输出，然后判断结点是否有后继，存在后继且后继不等于头结点的话，接着继续打印，依次循环。代码如下：

// 中序遍历打印
void inOrderPrintThreadBinaryTree(BinaryTree bt) {
    // 根结点
    BinaryTree p = bt->leftChild;
    // H D I B J E A F C G
    while (p != bt) {
        // 一直找到第一个结点 第一个结点的leftTag==isThread
        while (p->leftTag == isChild) {
            p = p->leftChild;
        }
        printf(" %c ", p->data); 
        
        while (p->rightTag == isThread && p->rightChild != bt) {
            p = p->rightChild;
            printf(" %c ", p->data);
        }
        p = p->rightChild;
    }
    printf("\n");
}

结合图形，可以看出，在第一次打印H之后，进入第二个循环，判断当前结点是否有后继且后继不是头结点，此时判断成立就是进入循环打印D，D不符合条件跳出循环，执行p = p->rightChild会将当前结点变成I，依次类推。

一般情况下，如果所用的二叉树需要经常遍历或者查找结点，或是需要某种遍历方式的前驱和后继，使用线索二叉树会大大的简化问题。