线索二叉树的实现

2017-10-27

我们知道，一棵二叉树，每个节点有两个指针域，分别指向该节点的左子树与右子树。现在，我们有一棵二叉树，我们假设这棵二叉树拥有n个节点，那么，空指针域有多少个呢？n个节点之间由n-1个指针连接起来，而n个节点，总共有2*n个指针域，所以，我们很容易算出，一棵拥有n个节点的二叉树，空指针的个数为n+1个。

在前一篇文章中，我们介绍了二叉查询书树的一些基本操作，其中，我们来看下遍历操作

//中序遍历
void PrintTreeMid(Tree tree) {
    if (tree) {
        PrintTreeMid(tree -> LeftTree);
        cout << tree -> data << " ";         
        PrintTreeMid(tree -> RightTRee);
    }
}

这是二叉树的中序遍历代码，通过这个代码，我们发现，节点的指针域存储着子节点的信息，但是父节点的呢？我们无从得知。如果有写过链表的话，我们知道有个双向链表，通过增加指针域，使得一个节点既有下一节点的信息，同时还是有上一节点的信息。因此，我们就想，树能不能也想双向链表一样，知道子节点的信息，同时还能知道上一节点的信息，因此，就有了线索二叉树这一特殊的树。

线索二叉树的实现是在普通二叉树的基础之上，通过利用空指针与两个标识符进行区分，该指针是指向子节点，还是指向上一节点，在这里，我们用一个枚举类型来区分，线索 thread = 0，子节点 link = 1

我先贴上二叉树线索化的代码

ThreadTree pre;
//二叉树线索化
void InThreading(ThreadTree threadTree) {
    if (threadTree) {
        InThreading(threadTree -> lchild);
        if (!threadTree -> lchild) {
             threadTree -> ltag = Thread;
             threadTree -> lchild = pre;
        }
        if (pre && !pre -> rchild) {
             pre -> rtag = Thread;
             pre -> rchild = threadTree;
        }
        pre = threadTree;
        InThreading(threadTree -> rchild);
    }
}

我们线索化的顺序是先线索化左子树，再线索化右子树。同时，我们还需要一个ThreadTree类型的空指针，用来一直指向当前节点的前驱节点，并且规定：所有为空的右孩子指针指向该节点的后继，所有为空的左孩子指针指向该节点的前驱。

2017-10-27 16-15-07屏幕截图

我们先通过递归调用，来到这棵树的最左节点，然后先看4这个节点的左指针，发现为空，因为我们让4这个节点的左指针指向前驱（此时的前驱为null），然后为这个指针加上标识符–thread，然后我们判断当前的pre前驱指针是否为空并且前驱的右子树是否存在，然后改变前驱指针，将当前指针赋给前驱指针，再递归，进入当前节点的右子树，发现4的右子树为空，函数执行完，返回上一层调用，然后在返回上一层，来到3这个节点，然后我们发现3的左子树不为空，连接这4这个节点，因为我们不改变3这个节点的左指针原来的含义，然后看前驱指针，也就是4这个节点，前驱节点的右子树为空，因此，前驱指针的后继就是当前节点—3这个节点，接着在替换前驱指针为当前节点，再接着进入当前3这个节点的右子树进行下一步的线索化，依次下去，我们会完成整棵树的线索化，就是下面这幅图：

2017-10-27 16-40-43屏幕截图

上面这幅图就是普通二叉树线索后的效果，我们可以发现，这就像双向链表，所以，我们在遍历树的时候，就由之前的较复杂的遍历轻松转变成了简单的线性遍历。下面是遍历线索二叉树的代码：

//线索二叉树的中序遍历
void InOrderTraverse(ThreadTree tree) {
    ThreadTree p = tree;
    while (p) {
        while (p -> ltag == Link) {
            p = p -> lchild;
        }
        cout << p -> data << " ";         
        while (p -> rtag == Thread && p) {
            p = p -> rchild;
            cout << p -> data << " ";
         }         
        p = p -> rchild;
    }
}

附上线索二叉树的数据类型定义

struct Tree; 
typedef struct Tree *ThreadTree; 

typedef enum { 
    Link = 0, Thread = 1 
}PointerThr;

struct Tree { 
    char data; 
    ThreadTree lchild; 
    ThreadTree rchild; 
    PointerThr ltag; 
    PointerThr rtag; 
};

下面是摘录的一些有关概念知识（摘录自C语言中文网——数据结构部分）

C语言中文网

一、在中序线索二叉树上查找任意结点的中序前驱结点
对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况：
（1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；
（2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1 时，它就是所要找的前驱结点。