数据结构什锦（四）

线索二叉树

在先前的笔记中，我们讨论了普通的二叉树。但是普通二叉树的非递归遍历依赖于栈和队列的辅助，而这两者占用的空间过大。且在普通二叉树的大部分指针为空指针。例如，一棵有n个节点的二叉树就包含n+1个空指针，会造成储存空间的浪费。

现在我们来介绍线索二叉树/threaded binary tree traversal，这种二叉树的遍历不需要栈或者队列，而是在空指针中储存一些信息称为线索/thread来辅助遍历。

线索二叉树的动机

容易知道，我们之所以在之前需要用栈或者队列去储存节点，是因为我们需要在遍历完该节点左子树后再遍历其右子树。如果我们把这些信息储存在空指针里，就不需要栈和队列了。那么我们要怎么储存信息呢？

通常我们会储存节点的前驱/后继节点。如果我们处理的是先序遍历，那么对于给定的节点，它的左空指针存放该节点的先序前驱节点信息，右空指针储存该节点的先序后继节点的信息。

线索二叉树的分类

我们将是否在左右指针中均存有有用信息还是只在其中一个空指针中存储信息来将线索二叉树进行分类。

左线索二叉树/left threaded binary tree。只在左空指针中存储前驱节点信息。
右线索二叉树/right threaded binary tree。只在右空指针中存储后继节点信息。
满线索二叉树/full threaded binary tree。两个空指针域中都储存信息。

下面我们默认只讨论满线索二叉树。

线索二叉树的类型

基于上面的讨论，我们还能给出线索二叉树的三种表示。

先序线索二叉树/preorder threaded binary tree。左右空指针域分别储存先序遍历序列中前驱/后继节点的信息。
中序线索二叉树/inorder threaded binary tree。左右空指针域分别储存中序遍历序列中前驱/后继节点的信息。
后序线索二叉树/postorder threaded binary tree。左右空指针域分别储存后序遍历序列中前驱/后继节点的信息。

这三种看起来都差不多，所以接下来我们只讨论中序线索二叉树来展开讨论。

线索二叉树的结构

线索二叉树必须要区分清楚线索和常规左右指针，所以我们添加了两个辅助域。

struct ThreadedBinaryTreeNode{
    struct ThreadedBinaryTreeNode*left;
    int LTag;
    int data;
    int RTag;
    struct ThreadedBinaryTreeNode*right;
};

具体的信息整理了如下表格。

	常规二叉树	线索二叉树
如果LTag==0	空	指向中序序列前驱节点的左线索
如果LTag==1	指向左孩子的指针	指向中序序列后继节点的左线索
如果RTag==0	空	指向中序序列前驱节点的右线索
如果RTag==1	指向右孩子的指针	指向中序序列后继节点的右线索

  graph TB;
1((1))-->2((2))
1((1))-->3((3))
2((2))-->4((4))
3((3))-->6((6))
3((3))-->7((7))
4((4)).->8((NULL))
4((4)).->2((2))
2((2)).->1((1))
6((6)).->3((3))
6((6)).->1((1))
7((7)).->3((3))
7((7)).->9((NULL))

我们可以注意到线索二叉树的最左边和最右边两个节点的空指针是悬挂的，那么他们指向哪里呢？

为了方便，我们定义一个特殊节点Dummy。该节点总是存在，即使对于一个空的树他也存在。且Dummy节点的右标识为1，其右孩子节点指向它自己。

struct ThreadedBinaryTreeNode Dummy={
    &Dummy,
    0,
    -1,//任何不存在的值
    1,
    &Dummy
};

  graph TB
    left --- LTag:1
    left --> 1
    LTag:1 --- None
    None --- RTag:1
    RTag:1 --- right
    right .-> right

1((1))-->2((2))
1((1))-->3((3))
2((2))-->4((4))
3((3))-->6((6))
3((3))-->7((7))
4((4)).->left
4((4)).->2((2))
2((2)).->1((1))
6((6)).->3((3))
6((6)).->1((1))
7((7)).->3((3))
7((7)).->right

线索二叉树的操作

在中序遍历中查找中序后继节点

假设我们给定的节点是P，要查询该节点的后继节点。如果P没有又子树，就返回P的右孩子指针，此时该指针指向的元素即为后继节点；倘若P存在右子树，就返回指向其右子树最左下的节点的指针。（主要是由于这是中序遍历，先遍历左子树再读取节点。此时该节点右子树的最左下节点是该节点的后继节点）

代码实现如下：

struct ThreadedBinaryTreeNode*InorderSuccessor(struct ThreadedBinaryTreeNode*P){
    struct ThreadedBinaryTreeNode*Position;
    if(P->RTag==0)//判断是否存在右子树
        return P->right;
    else{
        Position=P->right;
        while (Position->LTag==1)//遍历至节点右子树最左边的元素
            Position=Position->left;
        return Positionl;
    }
}

基于中序线索二叉树的中序遍历

我们可以从Dummy节点开始调用InorderSuccessor()来访问每个节点直到回到Dummy节点为止。

代码实现如下。

void InorderTraversal(struct ThreadedBinaryTreeNode*root){
    //root即为Dummy节点，此时调用InorderSuccessor函数传入Dummy节点
    //判断Dummy节点的右子树是否存在，Dummy节点的右子树始终存在且指向自己
    //于是这里返回的是Dummy节点右子树最左侧的节点，也就是其自身的左子树的最左侧节点
    //然后沿着树一路北上知道从另一侧重新回到Dummy节点
    struct ThreadedBinaryTreeNode*P= root;
    while (1){
        P= InorderSuccessor(P);
        if(P==root)
            return;
        printf("%d",P->data);
    }
}

在中序遍历中查找先序后继节点

策略和查找中序后继节点的方法类似。首先检查给定节点的左子树：若存在左子树，则返回P的左孩子指针；否则，返回右子树包含P的最近节点的右孩子。

代码实现如下。

struct ThreadedBinaryTreeNode*PreorderSuccessor(struct ThreadedBinaryTreeNode*P){
    struct ThreadedBinaryTreeNode*Position;
    if(P->LTag==1)
        return P->left;//如果左子树存在，返回指向的左孩子。
    else{
        Position=P;
        while (Position->RTag==0)//一直遍历到该节点的右子树最右端
            Position=Position->right;
        
        return Position->right;//此时返回的是右子树的最右端节点后继节点，当然，按照的是中序规则。
    }
}

基于中序线索二叉树的先序遍历

和中序遍历一样，从Dummy节点开始调用PreorderSuccessor()遍历每个节点直到回到Dummy节点为止。

代码实现如下。

void PreorderTraversal(struct ThreadedBinaryTreeNode*root){
    struct ThreadedBinaryTreeNode*P=root;
    while (1){
        P= PreorderSuccessor(P);
        if(P==root)
            return;
        printf("%d",P->data);
    }
}