5.5 线索二叉树

  • 为了解决二叉树中空链数目大于非空链的数目问题,将这些空链指向二叉树中的其他结点,称为 「线索 thread」。为了建立这些线索,使用下面的规则:
    1. 如果结点的左儿子 ptr->left_child 为空,则将它指向 ptr「中序遍历的前驱结点 inorder predecessor of ptr
    2. 如果结点的右儿子 ptr->right_child 为空,则将它指向 ptr「中序遍历的后继结点 inorder successor of ptr

下图给出了 5.2 二叉树 中的完全二叉树 对应的线索树,其中的线索用虚线表示。

5-14

5.2 二叉树 的完全二叉树 对应的线索树

如图,有两个线索是不确定的:一个是结点 8 的左儿子,另一个是结点 7 的右儿子。由于结点 8 是在中序遍历中第一个被访问的结点,所以不能用指向其前驱结点的线索代替其左空链域。结点 7 是中序遍历最后被访问的结点同理。因此,假设所有的线索二叉树都有一个头结点,所有不确定的空线索都指向头结点,并且空的线索二叉树总包含一个结点。

在内存中表示线索二叉树时,必须能够区分是线索还是正常指针。为此,在结点结构中增加两个附加域:left_threadright_thread。某个结点的 left_thread 域是 true,则它的 left_child 是一个线索;否则,它是一个指向左儿子的指针。right_thread 同理。

5-15

空的线索树

5-16

线索树的存储表示

  • 『中序遍历线索二叉树』 通过使用线索,可以简化中序遍历算法。可以看到,在线索二叉树中,对每一个结点 ptr,如果 ptr->right_thread = true,那么根据线索定义,结点 ptr 的中序后继结点是 ptr->right_child。否则,结点 ptr 的中序后继结点是从其右儿子开始,沿着左儿子链到达 left_thread = true 的结点。在不使用栈的情况下,函数 insucc 在线索树中找到任意结点的中序后继结点。
threaded_pointer insucc(threaded_pointer tree)
{
    threaded_pointer temp;
    temp = tree->right_child;
    if (!tree->right_thread)
        while (!temp->left_thread)
            temp = temp->left_child;
    return temp;
}

为了进行中序遍历,重复调用函数 insucc。遍历算法实现为函数 tinorder。该函数假定头结点的左链指向二叉树,并且头结点的右线索标志为 false

void tinorder(threaded_pointer tree)
{
    threaded_pointer temp = tree;
    for (;;) {
        temp = insucc(temp);
        if (temp == tree) break;
        printf("%d", temp->data);
    }
}
  • 『向线索二叉树中插入结点』 假设有一个结点 parent,其右子树为空。想要插入结点 child,作为结点 parent 的右儿子。为此,应该:

    1. parent->right_thread 改为 false
    2. child->left_threadchild->right_thread 置为 true
    3. 设置 child->left_child 指向 parent
    4. child->right_child 置为 parent->right_child
    5. 修改 parent->right_child,使其指向 child

      如果结点 parent 右非空右子树,插入操作就要稍微困难一些,因为在插入后,结点 parent 的右子树变为结点 child 的右子树。此时,结点 child 成为原来 parent 结点的中序后继结点的中序前驱结点。如下图。函数 insert_right 能够同时对以上这两种情况进行处理。

结点 parent 的右子树为空的插入操作

结点 parent 有非空右子树的插入操作

void insert_right(threaded_pointer parent, threaded_pointer child)
{
    threaded_pointer temp;
    child->right_child = parent->right_child;
    child->right_thread = parent->right_thread;
    child->left_child = parent;
    child->left_thread = true;
    parent->right_child = child;
    parent->right_thread = false;
    if (!child->right_thread) {
        temp = insucc(child);
        temp->left_child = child;
    }
}

results matching ""

    No results matching ""