C/C++线索二叉树(二叉树线索化)

概述

在二叉链表存储结构中，只能找到一个结点的左右孩子，不能直接得到结点在任一遍历序列中的前驱和后继，这些信息只有在遍历的动态过程中才能得到，因此引入线索二叉树的目的是利用空闲空间来保存这些动态过程得到的信息，可以理解为废物利用，开源节流，哈哈。

若n个结点的二叉树采用二叉链表做存储结构，则链表中必然有n+1个空指针域。

为什么有n+1个空指针域呢？让我们来证明一下：

首先因为每个节点下有两个指针域，n个节点有2n个指针域。

又因为n个结点由n-1条边连接（两点之间一条线段）。

即必然有n-1个指针域是被用于指向孩子的。故有2n-（n-1）=n+1个空指针域。

我们可以利用这些空指针域来存放结点的前驱和后继信息。为此可以在结点中增加标志ltag和rtag,以区分指针域是否可以被线索化。

ltag=0 表示左节点指针域指向结点的左孩子，ltag=1 表示左节点指针域指向结点的直接前驱。

rtag=0 表示右节点指针域指向结点的右孩子， rtag=1 表示右节点指针域指向结点的直接后继。

实现

更新线索

pre记录当前遍历序列中的直接前驱。若当前结点左右指针域为空，则标志flag=1，表示可用于线索化。

若直接前驱的右孩子空间可用于直接后续线索化，则进行后续线索化。若当前结点的左孩子空间可用于直接前驱线索化，则进行前驱线索化。

template <typename ElementType>
void ClueBTree<ElementType>::UpdateClue(BTreeNode<ElementType> *_node)
{
    if (_node->lchild == nullptr)
    {
        _node->lflag = 1;
    }
    if (_node->rchild == nullptr)
    {
        _node->rflag = 1;
    }
    //pre记录直接前驱 
    if (pre != nullptr)
    {
        // 判断直接前驱的右孩子空间是否可用于直接后续线索化。
        if (pre->rflag == 1)
        {
            pre->rchild = _node;//记录pre的直接后续
        }
        // 判断当前结点的左孩子空间是否可用于直接前驱线索化。
        if (_node->lflag == 1)
        {
            _node->lchild = pre;
        }
    }
    pre = _node;
}

 访问线索二叉树

这里以以获取中序线索二叉树中某个结点的直接后继为例。

若发现右孩子域上有直接后继线索，则直接返回记录的线索值。否则动态运算找到直接后继。

中序序列中的直接后继是当前结点的右子树的左子树中的最后一个左孩子结点或这棵右子树结点（右孩子结点自身）。

/// @brief 获取中序遍历的直接后续
/// @tparam ElementType 
/// @param _node 
/// @return 
template <typename ElementType>
ElementType ClueBTree<ElementType>::GetNext_Inorder(BTreeNode<ElementType> *_node)
{
    //是否有线索
    if (_node->rflag == 1)
    {
        return _node->rchild->elemValue;
    }
    //中序序列的直接后继是右子树的左子树中的最后一个左孩子结点或这颗右子树（右孩子自身）。
    _node = _node->rchild;
    while (_node->lchild != nullptr && _node->lflag == 0)
    {
        _node = _node->lchild;
    }

    return _node->elemValue;
}

遍历

UpdateClue(_node);//更新当前序列中输出的结点的线索

template<typename ElementType>
void ClueBTree<ElementType>::PreorderTraverseByRecursion(BTreeNode<ElementType> *_node)
{
    if (_node==nullptr)
    {
        return;
    }
    UpdateClue(_node);
    printf("Value:%d/n",_node->elemValue);
    PreorderTraverseByRecursion(_node->lchild);
    PreorderTraverseByRecursion(_node->rchild);
}
template <typename ElementType>
void ClueBTree<ElementType>::InorderTraverseByRecursion(BTreeNode<ElementType> *_node)
{
    if (_node == nullptr)
    {
        return;
    }
    InorderTraverseByRecursion(_node->lchild);
    UpdateClue(_node);//更新当前序列中输出的结点的线索
    printf("Value:%d/n", _node->elemValue);
    InorderTraverseByRecursion(_node->rchild);
    
}
template <typename ElementType>
void ClueBTree<ElementType>::PostorderTraverseByRecursion(BTreeNode<ElementType> *_node)
{
    if (_node == nullptr)
    {
        return;
    }
    PostorderTraverseByRecursion(_node->lchild);
    PostorderTraverseByRecursion(_node->rchild);
    UpdateClue(_node);
    printf("Value:%d/n", _node->elemValue);
    
}

需要注意的是，因为我们采用n+1个指针域来进行线索化，必然其线索是不完整的。也就是说部分结点的前驱和后继信息还需进一步动态运算得到的。

示例下载