【霍罗维兹数据结构】线索二叉树 | THREADED BINARY TREES

前言

最近在读霍罗维兹的《数据结构基础》（Fundamentals of Data Structures in C），本篇博客为阅读笔记和知识总结。

0x00 线索（threads）

具有 个结点的二叉链表共有 个链域，其中 为空链域。

A.J.Perlis 与 C.Thornton 提出一种方法，用用原来的空链域存放指针，指向树中的其他结点。

这种指针就被称为 线索（threads），记 ptr 指向二叉链表中的一个结点，一下是建线索的规则：

① 如果 ptr->leftChild 为空，则存放指向中序遍历排列中该节点的前驱结点。该节点成为 ptr 的 中序前驱（inorder predecessor）。

② 如果 ptr->rightChild 为空，则存放指向中序遍历序列中该结点的后继节点。这个节点称为 ptr 的中序后继（inorder successor）。

当我们在内存中表示树时，我们必须能够区分线程和普通指针。

这是通过在节点结构中添加两个额外的字段来实现的，即 left_thread 和 right_thread 。

typedef struct threaded_tree* threaded_pointer;
typedef struct threaded_tree {
  short int left_thread;
  threaded_pointer left_child;
  char data;
  threaded_pointer right_child;
  short int right_thread;
};

我们假设所有线程二叉树都有一个头结点。

线程二叉树的无序遍历 确定一个节点的无序继承者。

[Program 5.10]  Finding the inorder successor of a node.

threaded_pointer insucc(threaded_pointer tree)
{
  /* find the inorder successor of tree
  in a threaded binary tree */
  threaded_pointer temp;
  temp = tree->right_child;
  if (!tree->right_thread)
    while (!temp->left_thread)
      temp = temp->left_child;
  return temp;
}

为了进行中序遍历，我们反复调用 insucc

[Program 5.11]  Inorder traversal of a threaded binary tree.

void tinorder(threaded_pointer tree)
{
  /* traverse the threaded binary tree inorder */
  threaded_pointer temp = tree;
  for (; ; ) {
    temp = insucc(temp);
    if (temp == tree) break;
    printf("%3c", temp->data);
  }
}

向线程二叉树插入一个节点，假设我们有一个节点，即 parent，它的右子树是空的。我们希望插入child 作为父节点的右子节点。

要做到这一点，我们必须：

① 将 parent-> right_thread 改为 FALSE

② 将 child->left_thread 和 child->right_thread 改为 TRUE

③ 将 child->left_child 改为指向 parent

④ 将 child->right_child 改为 parent->right_child

⑤ 将 parent->right_child 改为指向 child

对于 parent 具有非空右子树的情况：

处理这两种情况的 C 代码如下：

[Program 5.12] : Right insertion in a threaded binary tree

void insert_right(threaded_pointer parent, threaded_pointer child) {
  /* insert child as the right child of parent in a threaded binary tree */
  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;
  }
}

参考资料

Fundamentals of Data Structures in C