数据结构与算法（十一）——线索化二叉树&哈夫曼树

一、线索化二叉树

1，产生的背景

如上图所示，是一个二叉树。可以看到，每一个节点都有三个元素：左子指针域、右子指针域、值域。对于存在左右子树的节点，其左右指针域指向的分别是各自的左右子节点；而对于未存在左子树，或者未存在右子树，或者左右子树均未存在的节点，该节点的左子指针域、右子指针域、左右指针域就会指向为空，此时就会存在指针域空间浪费的情况。而线索化二叉树就可以将这些浪费的指针域空间给利用起来，这是第一个背景。

第二个背景就是，可以更加快速和便捷地查找到某个节点的前驱和后继节点。

2，对二叉树进行线索化的逻辑

二叉树的线索化，实际上就是将某个节点的未利用到的指针域空间指向某种遍历次序（前序、中序、后序）下的前驱或者后继节点。如下图所示，实线指向的就是子节点，虚线指向的就是前驱结点或者后序节点：

需要注意的是，前驱或者后继的指向是跟遍历次序有关的，某一个节点的前驱和后继在不同的遍历次序下是不一样的。比如，在前序、中序以及后序遍历的次序下，某个节点的前驱或者后继的指向都是不一样的。

与一般的二叉树相比，线索化的二叉树无非就是将空余的指针域给利用了起来，然后将这些空余的指针域指向某种遍历次序下的前驱或者后继。线索化的目的其实就是为了能够快速找到某一个节点的前驱和后继节点。

并不是所有的二叉树节点都可以线索化的，只有当前节点的左子节点或者右子节点为空的时候，当前节点才可以被线索化。若某节点的左子树为空，则该节点的左子指针域指向前驱节点；若某节点的右子树为空，则该节点的右子指针域指向后继节点。

如上图所示，是中序遍历次序下的二叉树中各个前驱后继指针的指向。实际上，我们在对二叉树进行线索化的时候，肯定是需要进行一次遍历的，分析遍历到的每一个节点，如果有无用的指针域，那么就为其设置前驱或者后继。

3，如何判断某节点的左子节点指针指向的是左子节点还是前驱结点

线索化之后，二叉树的某一个节点的左子指针域和右子指针域就都指向了某一个节点，那么我们该如何区分左子指针域指向的是该节点的左子节点还是前驱结点呢？

可以通过在节点结构中加一个左标识（右标识）来判断左子指针域（右子指针域）指向的是左子节点（右子节点）还是前驱节点（后继节点）。

如下图所示，就是加了标识位的线索化了的二叉树：

可以看到，此时的节点结构中包含五个元素：值域、左右子节点指针域、左右子节点指针类型。

4，代码

（1）二叉树的结构

代码语言：javascript复制

#include <stdio.h>
#include "string.h"
#include "stdio.h"
#include "stdlib.h"


#include "math.h"
#include "time.h"
#include <stdbool.h>


// 操作的状态
typedef enum : int {
  Success,
  Error,
} Status;


// 指针域指向的类型
typedef enum : int {
  link, // 左子节点、右子节点
  thread, // 线索化，前驱节点、后继节点
} PointerType;


// 节点值的类型
typedef char ElementValueType;
#define Nil '#' // 定义元素的空值


// 节点构造
typedef struct BinaryTreeNode {
  // 值域
  ElementValueType data;

  // 指针域
  struct BinaryTreeNode *leftChild;
  struct BinaryTreeNode *rightChild;

  // 指针域类型
  PointerType leftChildType;
  PointerType rightChildType;
} BinaryTreeNode;


// 二叉树类型
typedef struct BinaryTreeNode * BinaryTree;

（2）二叉树的构造

代码语言：javascript复制

// 1，二叉树的构造
char *initialString = "ABDH##I##EJ###CF##G##";
int initialIndex = 0;
void createBinaryTree(BinaryTree *tree) {
  // 递归结束条件
  ElementValueType currentValue = initialString[initialIndex];
  if (currentValue == Nil) { // 当前节点值为空值
    return;
  }

  // 为当前节点开辟空间
  *tree = malloc(sizeof(BinaryTreeNode));

  // 给当前节点值域赋值
  (*tree)->data = initialString[initialIndex  ];

  // 递归构造左子节点
  createBinaryTree(&((*tree)->leftChild));
  (*tree)->leftChildType = (*tree)->leftChild ? link : thread;

  // 递归构造右子节点
  createBinaryTree(&((*tree)->rightChild));
  (*tree)->rightChildType = (*tree)->rightChild ? link : thread;
}

（3）二叉树的线索化

我们这里采用中序遍历的次序进行线索化。

使用preNode来记录当前遍历到的节点的上一个节点。

代码语言：javascript复制

// 2，中序遍历二叉树，将其线索化
struct BinaryTreeNode *preNode;
void threadBinaryTree(BinaryTree *tree) {
  // 递归结束的条件
  if (!(*tree)) {
    return;
  }

  // 处理左子树
  threadBinaryTree(&((*tree)->leftChild));

  // 左子节点指针域
  if (!(*tree)->leftChild) {
    // 前驱结点
    (*tree)->leftChild = preNode;
    (*tree)->leftChildType = thread;
  } else {
    (*tree)->leftChildType = link;
  }

  // 前驱节点的右子节点指针域
  if (preNode && !preNode->rightChild) {
    preNode->rightChild = *tree;
    preNode->rightChildType = thread;
  } else if (preNode) {
    preNode->rightChildType = link;
  }

  // 更新上一个节点
  preNode = *tree;

  // 处理右子树
  threadBinaryTree(&((*tree)->rightChild));
}

（4）中序遍历二叉树，将其循环线索化

上面