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

#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;

// 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;
}

// 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));
}

// 3，中序遍历二叉树，将其循环线索化
void circleThreadBinaryTree(BinaryTree *circleThreadedTree, BinaryTree *tree) {
  // 创建头结点
  *circleThreadedTree = malloc(sizeof(BinaryTreeNode));

  // 头结点的左子节点设置为根节点
  (*circleThreadedTree)->leftChild = *tree;
  (*circleThreadedTree)->leftChildType = link;

  // 在线索化二叉树之前设置preNode的初始值，以将二叉树的第一个遍历到的节点的前驱设置为叶子节点
  preNode = *circleThreadedTree;

  // 对二叉树进行线索化
  threadBinaryTree(tree);

  // 头结点的右子节点线索化为二叉树的最后一个叶子节点
  (*circleThreadedTree)->rightChild = preNode;
  (*circleThreadedTree)->rightChildType = thread;

  // 二叉树的最后一个叶子节点的后继设置为头结点
  preNode->rightChild = *circleThreadedTree;
  preNode->rightChildType = thread;
}

// 4，遍历线索化后的二叉树
void printBinaryNodeValue(ElementValueType element) {
  printf("%d", element);
}


void traverseCircleThreadedBinaryTree(BinaryTree tree) {
  struct BinaryTreeNode *tempNode = tree->leftChild; // 一开始指向根节点，自根节点开始遍历

  while (tempNode != tree) { // 经过一轮遍历之后最终会重新回到头结点，此时结束遍历
    // 找到当前未遍历到的最前面的节点
    while (tempNode->leftChildType == link) {
      tempNode = tempNode->leftChild;
    }

    // 打印当前节点信息
    printBinaryNodeValue(tempNode->data);

    // 通过后继指针依次找到接下来的节点
    while (tempNode->rightChildType == thread && tempNode->rightChild != tree) { // 有后继节点的时候则打印后继节点
      tempNode = tempNode->rightChild;
      printBinaryNodeValue(tempNode->data);
    }

    // 有右子节点的时候，则进行新一轮遍历
    tempNode = tempNode->rightChild;
  }
}

000 001 010 011 100 101 110……

001 000 011 010 000 011 101 100 100 011

A——01
B——1001
C——101
D——00
E——11
F——1000

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

// 权重最大值
#define MaxWeight 10000

// 哈夫曼节点结构
typedef struct HaffTreeNode {
  int weight; // 权重值
  int parentIndex; // 父节点坐标
  int leftChildIndex; // 左子节点坐标
  int rightChildIndex; // 右子节点坐标
  bool isAddedIntoTree; // 是否已经加入进了二叉树中
} HaffTreeNode;

// 哈夫曼树结构类型
typedef struct HaffTreeNode * HaffTree;

// 构建哈夫曼树
/*
 ①采用顺序存储的方式
 ②需要从外界传入权重数组相关信息
 */
void createHaffTree(int *weights, int weighttCount, HaffTree tree) {
  // 1，首先初始化所有的节点
  /*
   ①如果叶子节点的个数是n，则该哈夫曼树中就会有2n-1个节点
   ②将n个叶子节点都存放在数组的前n个位置
   ③将所有的叶子节点都赋予指定的权重值，所有的非叶子节点的权重值都赋值为0
   ④将所有节点的父节点坐标都初始化为0，子节点坐标都初始化为-1（代表没有子节点），isAddedIntoTree均设置为false代表未加入到二叉树中
   */
  for (int i = 0; i < 2*weighttCount-1; i++) {
    if (i < weighttCount) { // 当是叶子节点的时候
      tree[i].weight = weights[i];
    } else { // 当是非叶子节点的时候
      tree[i].weight = 0;
    }
    tree[i].parentIndex = 0;
    tree[i].leftChildIndex = -1; // 默认左右子节点都不存在
    tree[i].rightChildIndex = -1;
    tree[i].isAddedIntoTree = false; // 默认未加入到二叉树中
  }

  // 2，循环遍历所有节点，处理其相互关系
  int theMinWeight = MaxWeight; // 最小权重值
  int theSecondToTheMinWeight = MaxWeight; // 倒数第二小权重值
  int indexOfMin = 0; // 最小权重的节点坐标
  int indexOfSecondToMin = 0; // 倒数第二小权重的节点坐标
  /*
   如叶子节点有n个，则总共会有2n-1个节点，所以非叶子节点的个数为n-1
   */
  for (int i = 0; i < weighttCount - 1; i++) {
    // （1）寻找权重最小的俩节点
    /*
     寻找的区间是0~weighttCount+i之间。
     一定要记住，每一次都是找到俩权重最小的节点，然后构建一个新的双亲结点并加入到节点数组中。
     */
    for (int j = 0; j < weighttCount + i; j++) {
      if (tree[j].weight < theMinWeight && !tree[j].isAddedIntoTree) {
        theSecondToTheMinWeight = theMinWeight;
        indexOfSecondToMin = indexOfMin;

        theMinWeight = tree[j].weight;
        indexOfMin = j;
      } else if (tree[j].weight < theSecondToTheMinWeight && !tree[j].isAddedIntoTree) {
        theSecondToTheMinWeight = tree[j].weight;
        indexOfSecondToMin = j;
      }
    }

    // （2）将权重最小的俩节点加入到二叉树中
    /*
     找到权重最小的俩节点之后，将这俩节点组合成一个小树，所以需要生成一个双亲结点，这个双亲结点就存储在节点数组的接下来的位置上。
     一定要注意哦，这里的双亲结点的存储位置是我自己定义的哦，这跟我们之前说的按照层序遍历的次序进行存储是不一样的哦~
     */
    // 处理俩子节点的双亲结点指针指向
    tree[indexOfMin].parentIndex = weighttCount + i;
    tree[indexOfSecondToMin].parentIndex = weighttCount + i;

    // 将俩子节点标记为已经加入到二叉树中
    tree[indexOfMin].isAddedIntoTree = true;
    tree[indexOfSecondToMin].isAddedIntoTree = true;

    // 给父节点权重赋值，并且设置父节点的俩子节点指针
    tree[weighttCount + i].weight = tree[indexOfMin].weight + tree[indexOfSecondToMin].weight;
    tree[weighttCount + i].leftChildIndex = indexOfMin;
    tree[weighttCount + i].rightChildIndex = indexOfSecondToMin;
  }
}

// 哈弗曼编码的最大位数
#define MaxHaffCodeSize 100

// 哈夫曼编码结构
typedef struct HaffCode {
  int bits[MaxHaffCodeSize]; // 承载哈弗曼编码的数组
  int finalBitIndex; // 哈弗曼编码在bits数组中占用的结束位置
  int weight; // 当前字母的权重
} HaffCode;

// 根据哈夫曼树来求出哈夫曼编码
void haffCode(HaffTree tree, int count, HaffCode *haffCodes) {
  struct HaffCode *tempHaffCode = malloc(sizeof(HaffCode));
  int childIndex;
  int parentsIndex;

  // 依次遍历各个叶子节点，以获取到每一个叶子节点的哈弗曼编码，并保存在haffCodes中
  for (int i = 0; i < count; i++) {
    // 1，获取当前遍历到的叶子节点的哈弗曼编码，并通过临时变量tempHaffCode来记录
    tempHaffCode->finalBitIndex = 0;
    tempHaffCode->weight = tree[i].weight;

    childIndex = i;
    parentsIndex = tree[childIndex].parentIndex;
    // 自叶子节点一直遍历到根节点
    while (parentsIndex != 0) {
      // 左孩子节点编码为0，右孩子节点编码为1
      tempHaffCode->bits[tempHaffCode->finalBitIndex] = tree[parentsIndex].leftChildIndex == childIndex ? 0 : 1;

      // 将节点在二叉树中位置上移一层
      tempHaffCode->finalBitIndex++;
      childIndex = parentsIndex;
      parentsIndex = tree[childIndex].parentIndex;
    }

    // 2，将临时编码变量tempHaffCode的数据赋值到haffCodes[i]中
    // （1）tempHaffCode中记录的编码是逆序的，因此需要给正序过来
    for (int j = 0; j < tempHaffCode->finalBitIndex - 1; j++) {
      haffCodes[i].bits[j] = tempHaffCode->bits[tempHaffCode->finalBitIndex-j-1];
    }
    // （2）将tempHaffCode中的编码结束位置和权重赋值给haffCodes[i]
    haffCodes[i].finalBitIndex = tempHaffCode->finalBitIndex;
    haffCodes[i].weight = tempHaffCode->weight;
  }
}