数据结构的实践心得（二叉树的抽象数据结构和各种遍历的递归及非递归实现，以及哈夫曼算法应用：binaryTree）
头文件（binaryTree.h）：
#pragma once
#define BinaryTreeOrderBUFFER 128
typedef double binaryElemType;
typedef struct
{
int key; // 二叉树节点关键字（优先数）
binaryElemType *data; // 数据内容
int dataSize; // 数据内容的空间大小
struct binaryNode *parent; // 父节点
struct binaryNode *left; // 左节点
struct binaryNode *right; // 右节点
int length; // 二叉树的节点数量（包括所有子节点）
int isRight; // 如果是子节点，则是否为右节点（右：1；左：0）
}binaryNode;
// 创建二叉树节点
binaryNode* createBinaryNode(int dataSize);
// 设置二叉树节点的数据内容
void setBinaryNodeData(binaryNode *T, binaryElemType *e);
// 是否为叶子节点返回1，否则返回0
int isLeafBinaryNode(binaryNode *T);
// 二叉树的节点数量
int lengthBinaryList(binaryNode *T);
// 二叉树的节点数量（递归）
int lengthBinaryListRecursion(binaryNode *T);
// 取得二叉树节点的层级
int levelBinaryNode(binaryNode *T);
// 取得子节点的相对层级
int levelBinaryChildNode(binaryNode *T, binaryNode *child);
// 取得二叉树节点的根节点
binaryNode* getBinaryRoot(binaryNode *T);
// 插入二叉树的子节点（右：1；左：0）
binaryNode* insertBinaryNode(binaryNode *T, int isRight, int key);
// 添加二叉树的子节点（右：1；左：0）
binaryNode* addBinaryNode(binaryNode *T, int isRight, binaryNode *child);
// 移除二叉树的子节点
int removeBinaryNode(binaryNode *T, binaryNode *child);
// 清空二叉树列表（递归）
void clearBinaryList(binaryNode *T);
// 层次遍历（输出节点的排序数组）
int levelOrder(binaryNode *T, binaryNode **orderList);
// 前序遍历（递归）
int preOrderRecursion(binaryNode *T, binaryNode **orderList);
// 前序遍历（输出数据的排序数组）
int preOrder(binaryNode *T, binaryNode **orderList);
// 中序遍历（递归）
int middleOrderRecursion(binaryNode *T, binaryNode **orderList);
// 中序遍历（输出数据的排序数组）
int middleOrder(binaryNode *T, binaryNode **orderList);
// 后序遍历（递归）
int postOrderRecursion(binaryNode *T, binaryNode **orderList);
// 后序遍历（输出数据的排序数组）
int postOrder(binaryNode *T, binaryNode **orderList);
// 生成最优二叉树（哈夫曼算法），返回二叉树根节点，参数传出叶子节点关系
binaryNode* bestBinaryTree(binaryNode *dataListOutleaf, int dataLen);
// 取得哈夫曼编码（叶子节点列表），注意在外部释放每个hfCode的内存空间
char** getHuffmanCodeByLeaf(binaryNode *leafList, int leafLen, char **hfCodeList);
// 取得哈夫曼编码，注意在外部释放每个hfCode的内存空间
char** getHuffmanCode(binaryNode *dataList, int dataLen, char **hfCodeList);
程序文件（binaryTree.c）：
#include <stdlib.h>
#include "mystring.h"
#include "linkQueue.h"
#include "linkStack.h"
#include "binaryTree.h"
// 创建二叉树节点
binaryNode* createBinaryNode(int dataSize)
{
// 首先申请自己的内存空间
binaryNode *bn = (binaryNode *)malloc(sizeof(binaryNode));
if (!bn) return NULL;
if (dataSize > 0)
{
bn->data = (binaryElemType *)malloc(sizeof(binaryElemType) * dataSize);
if (!bn->data)
{
// 清空二叉树列表（递归）
clearBinaryList(bn);
return NULL;
}
bn->dataSize = dataSize;
}
else
{
bn->data = NULL;
bn->dataSize = 0;
}
bn->key = 0;
bn->parent = NULL;
bn->left = NULL;
bn->right = NULL;
bn->length = 1;
bn->isRight = 0;
return bn;
}
// 设置二叉树节点的数据内容
void setBinaryNodeData(binaryNode *T, binaryElemType *data)
{
if ((!T) || (!data)) return;
// 判断数据内容是否有效
if (T->data)
{
// 是否包含数据内容
int i;
// 设置数据内容
for (i = 0; i < T->dataSize; i++)
{
T->data[i] = data[i];
}
}
}
// 是否为叶子节点返回1，否则返回0
int isLeafBinaryNode(binaryNode *T)
{
if (!T) return -1;
return ((!T->left) && (!T->right));
}
// 二叉树的节点数量
int lengthBinaryList(binaryNode *T)
{
if (!T) return 0;
// 判断节点数量是否有效
if (T->length > 0)
{
return T->length;
}
else
{
// 二叉树的节点数量（递归）
return lengthBinaryListRecursion(T);
}
}
// 二叉树的节点数量（递归）
int lengthBinaryListRecursion(binaryNode *T)
{
if (!T) return 0;
// 二叉树的节点数量
int len = 1;
// 递归记录左子树数量
len += lengthBinaryList(T->left);
// 递归记录右子树数量
len += lengthBinaryList(T->right);
// 更新节点数量
T->length = len;
return len;
}
// 取得二叉树节点的层级
int levelBinaryNode(binaryNode *T)
{
if (!T) return -1;
// 从 0 开始
int level = 0;
binaryNode *bn = T;
// 判断父级节点
while (bn->parent)
{
level++;
// 递归父级节点
bn = bn->parent;
}
return level;
}
// 取得子节点的相对层级
int levelBinaryChildNode(binaryNode *T, binaryNode *child)
{
if ((!T) || (!child)) return -1;
// 从 0 开始
int level = 0;
binaryNode *bn = child;
// 判断节点
while (bn)
{
if (T == bn) return level;
level++;
// 递归父级节点
bn = bn->parent;
}
return -1;
}
// 取得二叉树节点的根节点
binaryNode* getBinaryRoot(binaryNode *T)
{
if (!T) return NULL;
binaryNode *bn = T;
// 判断父级节点
while (bn->parent)
{
// 递归父级节点
bn = bn->parent;
}
return bn;
}
// 插入二叉树的子节点（右：1；左：0）
binaryNode* insertBinaryNode(binaryNode *T, int isRight, int key)
{
if (!T) return NULL;
// 判断是否已有左节点或右节点
if (isRight > 0)
{
if (T->right) return NULL;
}
else
{
if (T->left) return NULL;
}
// 创建二叉树节点
binaryNode *child = createBinaryNode(T->dataSize);
if (!child) return NULL;
// 节点关键字（优先数）
child->key = key;
// 父级节点
child->parent = T;
// 判断插入左节点或右节点
if (isRight > 0)
{
T->right = child;
child->isRight = 1;
}
else
{
T->left = child;
child->isRight = 0;
}
// 维护节点数量
binaryNode *bn = T;
// 判断节点
while (bn)
{
bn->length++;
// 递归父级节点
bn = bn->parent;
}
return child;
}
// 添加二叉树的子节点（右：1；左：0）
binaryNode* addBinaryNode(binaryNode *T, int isRight, binaryNode *child)
{
if ((!T) || (!child)) return NULL;
// 判断是否已有左节点或右节点
if (isRight > 0)
{
if (T->right) return NULL;
}
else
{
if (T->left) return NULL;
}
// 避免嵌套死循环，相对层级 >= 0，则表示嵌套子级节点
if (levelBinaryChildNode(child, T) >= 0) return NULL;
// 移除原有的父级关系
removeBinaryNode(child->parent, child);
child->parent = T;
// 判断添加左节点或右节点
if (isRight > 0)
{
T->right = child;
child->isRight = 1;
}
else
{
T->left = child;
child->isRight = 0;
}
// 维护节点数量
binaryNode *bn = T;
// 判断节点
while (bn)
{
bn->length += child->length;
// 递归父级节点
bn = bn->parent;
}
return child;
}
// 移除二叉树的子节点
int removeBinaryNode(binaryNode *T, binaryNode *child)
{
if ((!T) || (!child)) return -1;
// 判断父级关系是否匹配
if (T != child->parent) return -1;
int result = -1;
// 判断是否移除左节点
if (T->left == child)
{
T->left = NULL;
result = 1;
}
// 判断是否移除右节点
if (T->right == child)
{
T->right = NULL;
result = 1;
}
if (result > 0)
{
child->parent = NULL;
// 维护节点数量
binaryNode *bn = T;
// 判断节点
while (bn)
{
bn->length -= child->length;
// 递归父级节点
bn = bn->parent;
}
}
return result;
}
// 清空二叉树列表（递归）
void clearBinaryList(binaryNode *T)
{
if (!T) return;
// 递归清空左节点
clearBinaryList(T->left);
// 递归清空右节点
clearBinaryList(T->right);
// 释放数据空间
if (T->data) free(T->data);
// 释放自己
free(T);
}
// 层次遍历（输出数据的排序数组）
int levelOrder(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
linkQueue que;
// 初始化队列
initializeLinkQueue(&que);
// 根节点进队
pushQueue(&que, (int)T);
int index = 0;
binaryNode *bn;
// 进行队列操作
while (!isEmptyLinkQueue(que))
{
// 取得队首元素
bn = (int)front(que);
// 将队首元素出队
popQueue(&que);
// 判断元素是否有效
if (!bn) break;
// 排序数组赋值
orderList[index++] = bn;
// 左节点进队
if (bn->left) pushQueue(&que, (int)bn->left);
// 右节点进队
if (bn->right) pushQueue(&que, (int)bn->right);
}
// 清空队列
clearLinkQueue(&que);
return index;
}
// 前序遍历（递归）
int preOrderRecur(binaryNode *T, binaryNode **orderList, int index)
{
int i = index;
// 排序数组赋值
orderList[i++] = T;
// 递归左节点
if (T->left) i = preOrderRecur(T->left, orderList, i);
// 递归左节点
if (T->right) i = preOrderRecur(T->right, orderList, i);
return i;
}
// 前序遍历（递归）
int preOrderRecursion(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
// 前序遍历（递归）
return preOrderRecur(T, orderList, 0);
}
// 前序遍历（输出数据的排序数组）
int preOrder(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
linkStack stack;
// 初始化栈
initializeLinkStackSeq(&stack, BinaryTreeOrderBUFFER);
// 根节点进栈
push(&stack, (int)T);
int index = 0;
binaryNode *bn;
// 进行栈操作
while (!isEmptyLinkStack(stack))
{
// 取得栈首元素
bn = (int)top(stack);
// 将栈首元素出栈
pop(&stack);
// 判断元素是否有效
if (!bn) break;
// 排序数组赋值
orderList[index++] = bn;
// 右节点进栈
if (bn->right) push(&stack, (int)bn->right);
// 左节点进栈
if (bn->left) push(&stack, (int)bn->left);
}
// 清空栈
clearLinkStack(&stack);
return index;
}
// 中序遍历（递归）
int middleOrderRecur(binaryNode *T, binaryNode **orderList, int index)
{
int i = index;
// 递归左节点
if (T->left) i = middleOrderRecur(T->left, orderList, i);
// 排序数组赋值
orderList[i++] = T;
// 递归左节点
if (T->right) i = middleOrderRecur(T->right, orderList, i);
return i;
}
// 中序遍历（递归）
int middleOrderRecursion(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
// 中序遍历（递归）
return middleOrderRecur(T, orderList, 0);
}
// 中序遍历（输出数据的排序数组）
int middleOrder(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
linkStack stack, stackStatus;
// 初始化栈
initializeLinkStackSeq(&stack, BinaryTreeOrderBUFFER);
initializeLinkStackSeq(&stackStatus, BinaryTreeOrderBUFFER);
// 根节点进栈
push(&stack, (int)T);
push(&stackStatus, 0);
int index = 0, status;
binaryNode *bn;
// 进行栈操作
while (!isEmptyLinkStack(stack))
{
// 取得栈首元素
bn = (int)top(stack);
// 判断元素是否有效
if (!bn) break;
// 取得访问状态
status = (int)top(stackStatus);
pop(&stackStatus);
// 先访问左节点
if (status == 0)
{
push(&stackStatus, 1);
// 标记为0，尝试压栈左节点
if (bn->left)
{
push(&stack, (int)bn->left);
push(&stackStatus, 0);
}
}
else
{
// 将栈首元素出栈
pop(&stack);
// 排序数组赋值
orderList[index++] = bn;
// 尝试压栈右节点
if (bn->right)
{
push(&stack, (int)bn->right);
push(&stackStatus, 0);
}
}
}
// 清空栈
clearLinkStack(&stack);
clearLinkStack(&stackStatus);
return index;
}
// 后序遍历（递归）
int postOrderRecur(binaryNode *T, binaryNode **orderList, int index)
{
int i = index;
// 递归左节点
if (T->left) i = postOrderRecur(T->left, orderList, i);
// 递归左节点
if (T->right) i = postOrderRecur(T->right, orderList, i);
// 排序数组赋值
orderList[i++] = T;
return i;
}
// 后序遍历（递归）
int postOrderRecursion(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
// 后序遍历（递归）
return postOrderRecur(T, orderList, 0);
}
// 后序遍历（输出数据的排序数组）
int postOrder(binaryNode *T, binaryNode **orderList)
{
if ((!T) || (!orderList)) return -1;
linkStack stack, stackStatus;
// 初始化栈
initializeLinkStackSeq(&stack, BinaryTreeOrderBUFFER);
initializeLinkStackSeq(&stackStatus, BinaryTreeOrderBUFFER);
// 根节点进栈
push(&stack, (int)T);
push(&stackStatus, 0);
int index = 0, status;
binaryNode *bn;
// 进行栈操作
while (!isEmptyLinkStack(stack))
{
// 取得栈首元素
bn = (int)top(stack);
// 判断元素是否有效
if (!bn) break;
// 取得访问状态
status = (int)top(stackStatus);
pop(&stackStatus);
// 先左后右访问最低层节点
if (status == 0)
{
push(&stackStatus, 1);
// 标记为0，尝试压栈左节点
if (bn->left)
{
push(&stack, (int)bn->left);
push(&stackStatus, 0);
}
}
else if (status == 1)
{
push(&stackStatus, 2);
// 标记为1，尝试压栈右节点
if (bn->right)
{
push(&stack, (int)bn->right);
push(&stackStatus, 0);
}
}
else
{
// 将栈首元素出栈
pop(&stack);
// 排序数组赋值
orderList[index++] = bn;
}
}
// 清空栈
clearLinkStack(&stack);
clearLinkStack(&stackStatus);
return index;
}
// 在所有父级节点为空的元素中查找Key值（优先数）最小节点的索引下标
int minKeyIndex(binaryNode **nodeList, int len, int curIndex)
{
int i, min = -1;
binaryNode *bn;
// 倒序遍历已创建的二叉树节点列表
for (i = len - 1; i >= curIndex; i--)
{
bn = nodeList[i];
// 已设置父级节点，则无需比较
if (bn->parent) continue;
// 初始化最小值索引
if (min < 0) min = i;
// 比较Key值（优先数）最小节点的索引下标
if (bn->key < nodeList[min]->key) min = i;
}
return min;
}
// 生成最优二叉树（哈夫曼算法），返回二叉树根节点，参数传出叶子节点关系
binaryNode* bestBinaryTree(binaryNode *dataListOutleaf, int dataLen)
{
if ((!dataListOutleaf) || (dataLen < 2)) return NULL;
// 构造的最优二叉树，总数为叶子节点的两倍减一（dataLen * 2 - 1）
int len = dataLen * 2 - 1;
// 创建二叉树节点的缓存列表
binaryNode **nodeList = (binaryNode **)malloc(sizeof(binaryNode *) * len);
if (!nodeList) return NULL;
// 数据内容空间大小
int dataSize = dataListOutleaf[0].dataSize;
binaryNode *bn;
int index = len - 1, k;
// 循环创建二叉树节点，并倒序存储在列表中
for (k = 0; k < dataLen; k++)
{
// 创建二叉树节点
bn = createBinaryNode(dataSize);
if (!bn) continue;
// 优先数赋值
bn->key = dataListOutleaf[k].key;
// 设置二叉树节点的数据内容
setBinaryNodeData(bn, dataListOutleaf[k].data);
// 在列表中保存二叉树节点
nodeList[index--] = bn;
}
int minLeft, minRight, leafIndex;
binaryNode *leftNode, *rightNode;
// 数组左侧尚有未用空间，即新创建的节点个数还不足
while (index >= 0)
{
// 创建二叉树节点
bn = createBinaryNode(0);
if (!bn) continue;
// 在所有父级节点为空的元素中查找最小值的索引下标
minLeft = minKeyIndex(nodeList, len, index + 1);
leftNode = nodeList[minLeft];
// 添加二叉树的子节点（右：1；左：0）
addBinaryNode(bn, 0, leftNode);
// 如果是叶子节点，更新传入的基础数据列表的父级指针
if (isLeafBinaryNode(leftNode))
{
leafIndex = len - minLeft - 1;
dataListOutleaf[leafIndex].parent = bn;
dataListOutleaf[leafIndex].isRight = 0;
}
// 在所有父级节点为空的元素中查找最小值的索引下标
minRight = minKeyIndex(nodeList, len, index + 1);
rightNode = nodeList[minRight];
// 添加二叉树的子节点（右：1；左：0）
addBinaryNode(bn, 1, rightNode);
// 如果是叶子节点，更新传入的基础数据列表的父级指针
if (isLeafBinaryNode(rightNode))
{
leafIndex = len - minRight - 1;
dataListOutleaf[leafIndex].parent = bn;
dataListOutleaf[leafIndex].isRight = 1;
}
// 新创建的节点Key值（优先数）
bn->key = (leftNode->key + rightNode->key);
// 在列表中保存二叉树节点
nodeList[index--] = bn;
}
// 释放缓存列表
free(nodeList);
return bn;
}
// 取得哈夫曼编码（叶子节点列表），注意在外部释放每个hfCode的内存空间
char** getHuffmanCodeByLeaf(binaryNode *leafList, int leafLen, char **hfCodeList)
{
if ((!leafList) || (!hfCodeList) || (leafLen < 2)) return NULL;
// 定义一个字符串缓存
char *tmp = (char *)malloc(sizeof(char) * leafLen);
if (!tmp) return NULL;
binaryNode *bn;
char *code;
int i, index;
// 为每个hfCode申请内存空间
for (i = 0; i < leafLen; i++)
{
code = (char *)malloc(sizeof(char) * leafLen);
if (!code) return NULL;
bn = &(leafList[i]);
index = 0;
// 开始记录编码
while (bn->parent)
{
tmp[index++] = bn->isRight + '0';
// 递归父级节点
bn = bn->parent;
}
// 补充结束符
tmp[index] = 0;
// 字符串逆序输出
myReverse(tmp, code);
// 保存hfCode
hfCodeList[i] = code;
}
// 释放缓存
free(tmp);
return hfCodeList;
}
// 取得哈夫曼编码，注意在外部释放每个hfCode的内存空间
char** getHuffmanCode(binaryNode *dataList, int dataLen, char **hfCodeList)
{
// 生成最优二叉树（哈夫曼算法），返回二叉树根节点，参数传出叶子节点关系
binaryNode *root = bestBinaryTree(dataList, dataLen);
if (!root) return NULL;
// 取得哈夫曼编码（叶子节点列表）
char **result = getHuffmanCodeByLeaf(dataList, dataLen, hfCodeList);
// 释放二叉树列表
clearBinaryList(root);
return result;
}