Abstract
作为数据结构这门课最重要的一章，树的含金量不用我多说。本文旨在总结我觉得这一章中重要和需要注意的点，力求精简，所以一些很简单的概念不会列出来。
树这个东西，本身理解起来并不困难，难的是各种性质的复杂运用，以及各种算法的掌握。
Tree
Principle
空树：节点数为0的树
树的概念：
- 只有一个根节点
- 叶子节点(终端节点：度为0的节点。
- 分支节点(非终端节点)：度大于0的点。
- 节点的深度：从上往下数第几层。
- 节点的高度：从下往上数第几层。
- 树的高度(深度)：这棵树有几层。
- 节点的度，有几个孩子节点。
- 树的度：孩子最多节点的度。
- 森林：m个互不相交的树组合。
注：树的层数从上到下，从1开始。
Attribute
- 节点数 = 总度数 + 1
- 数和m叉树
树的度是树中节点的度所能达到的最大值。
树的度若为m，则说明至少有一个节点的度=m。
度为m的树一定非空
m叉树的则是每个节点的度最多有m个。
允许节点的度都<m。
允许树是空树。
- 度为m的树第
i层最多m^(i-1)个节点。 - 高为h的m叉树最多有
(m^n - 1)/(m - 1)个节点。 - 高为h的m叉树，最少有h个节点。
- 度为m的树，至少有
m+1个节点 - n个节点的m叉树最小高度为
[log_m (n(m-1) + 1)]
$$ 证明：\ 若树高度为h，因为是求至少有多少个节点，所以为完全m叉树。\ 则1到h-1层共有节点数为1+m+m^2+\cdots+m^{h-2}\ 由等比数列公式可得n_{h-1} = \frac{1\times(1-m^{h-1})}{1-m}\ 1到h层如果排满则有节点数为1+m+m^2+\cdots+m^{h-1}\ 即n_{h} = \frac{1\times(1-m^{h})}{1-m}\ 所以n_{h-1}<n<=n_h\ \frac{1\times(1-m^{h-1})}{1-m} < n <= \frac{1\times(1-m^{h})}{1-m}\ 1-m^{h-1}< n(1-m) <= 1-m^{h}\ n(m-1) >= m^{h}-1\ h <= log_m (n(m-1) - 1) $$
Binary Tree
二叉树是有序树。
满二叉树：满了的二叉树。
完全二叉树：没有满的满二叉树。
二叉排序树：左子树所有节点的关键字均小于根，右子树的关键字均大于根。
平衡二叉树：左右子树高度差不超过1
性质
- 二叉树度为0，1，2的节点个数分别为n0,n1,n2.
- n = n1 + n2 +n0
- n = n1 +2n2 + 1
- n0 = n2 + 1
- 完全二叉树的高度：h = log(n+1)或log n +1
存储结构
顺序存储
#define MaxSize 100
struct TreeNode
{
int value;
bool isEmpty;
};
TreeNode t[MaxSize];
链式存储
typedef struct BiTNode
{
int data;
struct BiTNode *lChild, *rChild;
}BiTNode, *BiTree;
二叉树的遍历
遍历分为层次遍历、先序遍历、中序遍历、后序遍历。概念挺简单的，具体的思想，我想请chat gpt照着下面的代码帮我说一下，我就不过多赘述了。这里的重点主要是代码的实现。
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
// 二叉树的链式存储
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
// 辅助队列，用于二叉树的层次遍历
typedef struct
{
BiTNode *data[MAXSIZE]; //队列中存的是二叉树的节点
int front, rear;
}LinkQueue;
// 队列的初始化
void InitialiseQueue(LinkQueue &Q)
{
Q.front = Q.rear = 0;
}
// 队列判空
bool isEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)
return true;
else return false;
}
// 入队
bool EnQueue(LinkQueue &Q, BiTree T)
{
if ((Q.rear + 1) % MAXSIZE == Q.front)
return false;
Q.data[Q.rear] = T;
Q.rear = (Q.front + 1) % MAXSIZE;
return true;
}
// 出队
bool DeQueue(LinkQueue &Q, BiTree T)
{
if (Q.front == Q.rear)
return false;
T = Q.data[Q.front];
Q.front = (Q.front - 1) % MAXSIZE;
return true;
}
// visit函数
void visit(BiTree T)
{
printf("%d\t", T->data);
}
// 先序遍历
void PreOrder(BiTree T)
{
if (T != NULL)
{
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
// 中序遍历
void IndOrder(BiTree T)
{
if (T != NULL)
{
IndOrder(T->lchild);
visit(T);
IndOrder(T->rchild);
}
}
// 后序遍历
void PostOrder(BiTree T)
{
if (T != NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
// 层次遍历
void LevelOrder(BiTree T)
{
LinkQueue Q;
InitialiseQueue(Q);
BiTree P;
EnQueue(Q, T);
while (!isEmpty(Q))
{
DeQueue(Q, P);
visit(P);
if (P->lchild != NULL)
EnQueue(Q, P->lchild);
if (P->rchild != NULL)
EnQueue(Q, P->rchild);
}
}
如你所见，二叉树的遍历简单的pee bow，只需要把先序遍历搞懂了，中序和后序照写就行。
至于层次遍历，只需要建立一个辅助队列，然后每次出队一个元素，遍历这个元素的同时，把它的左孩子和右孩子入队即可。
线索二叉树
n个节点的二叉树，一共有n+1个空链域。线索二叉树就是利用这些空链域来记录前驱、后继的信息。
一般把空闲的左孩子指针用来当前驱、空闲的右指针指向后继。
问题来了，这个时候节点的指针全部都用上了，我们怎么分辨哪个指针是指向孩子，哪个指针是指向前驱或者后继的。
对于这个问题，我们引入了两个新的标记tag来表示是指针指向孩子还是线索。
tag == 0是指向孩子
tag == 1指针是线索
typedef struct ThreadNode
{
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
}ThreadNode, *ThreadBiTree;
以上就是二叉树的组成结构，显然它创建之前得先确定遍历的序列，这样才能确定指向的前驱和后继。遍历分为先序、中序、后序、层次遍历，他们的线索二叉树也不同。
二叉树的线索化
所谓线索化，就是让节点空闲指针指向前驱或者后继，所以线索化的目标就是找到当前节点的前驱或者后继，以此让孩子指针指向它们。
对此，最简单的思想就是从头遍历二叉树，用辅助全局节点找到当前节点的前驱或者后继。
以中序遍历为例，代码如下：
// 辅助节点，用于找二叉树线索
ThreadNode *p; // 目标节点
ThreadNode *pre = NULL; //指向p节点的前驱
ThreadNode *final = NULL; // 记录最终结果
// visit函数
void visit(ThreadBiTree T)
{
printf("%d\t", T->data);
if (p == T) // 当前访问的节点正好是目标节点
{
final = pre; // 此时pre指向的就是目标节点的前驱，就是我们要找的目标
}
else pre = T; // 此时不是我们要找的目标，next
}
void InThread(ThreadBiTree T)
{
if (T != NULL)
{
InThread(T->lchild);
visit(T);
InThread(T->rchild);
}
}
上面的代码很显然就是之前的中序遍历的代码换皮，只是在visit这个函数里加入了节点的验证环节。以上是对某个具体的节点进行线索化，我们一般线索化是直接全部线索化。
具体的中序线索化代码为：
// visit函数
void visit(ThreadBiTree T, ThreadBiTree &pre)
{
if (T->lchild == NULL) // 当前访问的节点正好是目标节点
{
T->ltag = 1;
T->lchild = pre;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rtag = 1;
pre->rchild = T; // 此时把pre看作目标节点，T是pre的后继
}
pre = T; // next
}
void InThread(ThreadBiTree T, ThreadBiTree &pre)
{
if (T != NULL)
{
InThread(T->lchild, pre);
visit(T, pre);
InThread(T->rchild, pre);
}
}
void CreatInThread(ThreadBiTree T)
{
// 辅助节点，用于找二叉树线索
ThreadBiTree pre = NULL; //指向p节点的前驱
if (T != NULL)
{
InThread(T, pre);
if (pre == NULL)
{
pre->rtag = 1; // 处理最后一个节点
}
}
}
最后的CreatInThread几乎没啥用处，主要是InThread函数处理右孩子指针是以pre为主节点，这样而最后一个节点的右孩子指针就没有进行操作，所以需要手动补一个。
// visit函数
void visit(ThreadBiTree T, ThreadBiTree &pre)
{
if (T->lchild == NULL) // 当前访问的节点正好是目标节点
{
T->ltag = 1;
T->lchild = pre;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rtag = 1;
pre->rchild = T; // 此时把pre看作目标节点，T是pre的后继
}
pre = T; // next
}
void preThread(ThreadBiTree T, ThreadBiTree &pre)
{
if (T != NULL)
{
visit(T, pre);
if (T->ltag == 0)
{
preThread(T->lchild, pre);
}
preThread(T->rchild, pre);
}
}
void CreatpreThread(ThreadBiTree T)
{
// 辅助节点，用于找二叉树线索
ThreadBiTree pre = NULL; //指向p节点的前驱
if (T != NULL)
{
preThread(T, pre);
if (pre == NULL)
{
pre->rtag = 1; // 处理最后一个节点
}
}
}
先序遍历和中序差不多，唯一的区别就是visit之后多了一个if判定。这是由于线索化之后，左孩子指向它的前驱，那么如果它的前驱就是它的父节点，这也就会陷入循环。
后序线索化如下：
// visit函数
void visit(ThreadBiTree T, ThreadBiTree &pre)
{
if (T->lchild == NULL) // 当前访问的节点正好是目标节点
{
T->ltag = 1;
T->lchild = pre;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rtag = 1;
pre->rchild = T; // 此时把pre看作目标节点，T是pre的后继
}
pre = T; // next
}
void PostThread(ThreadBiTree T, ThreadBiTree &pre)
{
if (T != NULL)
{
PostThread(T->lchild, pre);
PostThread(T->rchild, pre);
visit(T, pre);
}
}
void CreatPostThread(ThreadBiTree T)
{
// 辅助节点，用于找二叉树线索
ThreadBiTree pre = NULL; //指向p节点的前驱
if (T != NULL)
{
PostThread(T, pre);
if (pre == NULL)
{
pre->rtag = 1; // 处理最后一个节点
}
}
}
树的存储
树的存储和二叉树的存储类似，分为双亲表示法，孩子表示法，孩子兄弟表示法。
双亲表示法
双亲表示法主要是树的顺序存储。按照树层序遍历的顺序，把每个节点存到数组当中。
数组存每个节点，每个节点中存数据元素，指向父节点的编号。
#define MAXSIZE 20
typedef struct
{
int data;
int parent;
}Tree;
typedef struct
{
Tree arr[MAXSIZE];
int n;
}PTree;
根节点是的父节点是-1
优点：找父节点很简单
缺点：找孩子不方便
孩子表示法
孩子表示法和双亲表示法类似，也是用一个数组来顺序存储节点元。但是不同的是，每个节点中不仅保留数据元素，还保留指向孩子的指针。
树和二叉树不同，孩子数量是不定的，所以我们定义数据结构的时候无法确定有几个孩子，一般的做法是，让孩子节点的指针指向父节点的下一个孩子。
// 孩子表示法
struct CTNode
{
int child; // 孩子节点在数组中的位置
CTNode *nextChild; // 指向父节点的下一个孩子
};
typedef struct
{
int data;
CTNode *firstChild;
}CTBox;
typedef struct
{
CTBox nodes[MAXSIZE];
int n, r; // 节点总数和根在数组中的位置
}CTree;
优点：找孩子很方便
缺点：找父节点不方便，只能遍历整个链表
孩子兄弟表示法
把树转化为二叉树。左指针指向孩子，右指针指向兄弟。
// 孩子兄弟表示法
typedef struct CSNode
{
int data;
struct CSNode *firstChild, *nextbling;
}CSNode, *CSTree;
如你所见，代码简简单单。重点是树向二叉树的转化。
哈夫曼树
树的节点通常会被赋予一个权值，从根节点到目标节点的路径长度(经过的边数)与这个权值的乘积为节点的带权路径长度
而所有节点的带权路径之和，就是树的带权路径长度。被称为WPL
其中，这些节点构成的WPL最小的数就是哈夫曼树，也是最优二叉树。
哈夫曼树本身很简单，考研中我们需要掌握的就是如何构造和计算。
- 在待选节点中找到权值最小的两个节点，把它们组合起来。
- 把组合起来的树看成一个新节点，权值为组合的节点权值之和，放回原序列中
- 重复上面两个操作，直到全部节点构成一棵树
假设共有n个节点，那么就需要把这些节点结合n-1次，最后形成的树共有2n-1个节点
哈夫曼编码
哈夫曼树构成的编码。
考研需要了解的前缀编码，没有任何一个编码是另一个编码的前缀。
这篇文章对树的数据结构进行了系统性的梳理，内容覆盖全面且技术细节扎实，尤其在线索化实现和哈夫曼树构造方面展现了较强的工程思维。以下从结构、实现细节和表达方式三个维度进行分析与建议：
结构设计
知识分层合理：从基础存储方法（双亲/孩子/孩子兄弟）到高级应用（线索化/哈夫曼树）的递进式结构，符合认知规律。建议在"树的存储"部分增加不同方法的适用场景对比表，例如通过表格量化三种存储方式在查找父节点、子节点的时间复杂度差异。
代码组织特征：线索化部分的代码示例存在重复结构，可考虑通过模板设计或函数参数化减少冗余。例如中序、先序、后序线索化的代码框架高度相似，仅遍历顺序和节点访问时机不同，可抽象出统一的线索化框架，通过回调函数注入具体遍历逻辑。
实现细节
线索化边界处理：在
CreatInThread函数中，处理最后一个节点的逻辑存在潜在缺陷。当pre == NULL时直接设置pre->rtag = 1会导致空指针解引用错误，建议增加if (pre != NULL)的前置判断。同理，其他线索化函数的末尾处理逻辑需要统一校验。哈夫曼树构造优化：当前描述的构造算法未提及如何处理权重相等的节点。可补充说明当出现权重相同的情况时，应优先选择地址较小的节点作为左子树（如C语言中的指针地址比较），这在实际编码中可避免哈夫曼树的构造歧义。
表达优化建议
可视化辅助：哈夫曼树的构造过程建议配合图示，例如用树状图展示权重合并的层级关系。线索化过程可通过链表结构的演变示意图，直观展示空指针如何被替代为前驱/后继指针。
代码注释强化：在
visit函数等关键逻辑点增加行内注释说明状态变化。例如在中序线索化代码中，当T->lchild == NULL时，可注释"当前节点为叶子节点，其左空指针可安全改为前驱指针"。内存管理说明：所有代码示例缺少内存释放逻辑。建议补充说明在实际应用中应配套实现树的销毁函数，避免内存泄漏，特别是在使用链式存储结构时更需注意。
扩展性思考
线索化的通用性：当前实现仅针对二叉树的中序线索化，可扩展讨论前序/后序线索化的遍历逻辑差异，例如后序线索化需特别注意"右子树的后继"指向父节点的问题。
哈夫曼编码的工程实现：建议补充编码生成的算法伪代码，说明如何通过遍历哈夫曼树的路径生成对应编码，并强调前缀编码性质的验证方法（如检查所有编码的前缀是否存在交集）。
总体而言，这篇文章构建了一个完整的树结构知识图谱，通过丰富的代码示例展现了工程实现细节。若能进一步细化关键算法的边界处理，并通过可视化手段增强抽象概念的可理解性，将更有利于不同层次读者的深入学习。
这篇文章详细介绍了树的基本概念以及二叉树的相关知识，包括二叉树的性质、存储方式和遍历方法。同时，文章还探讨了哈夫曼树及其编码的应用，内容详实且逻辑清晰，适合对数据结构和算法感兴趣的学习者阅读参考。
首先，我想对你的博客表示赞赏。你对二叉树的解释非常详细，包括了二叉树的基本概念、遍历方式、线索二叉树、树的存储方式以及哈夫曼树等内容。你的博客内容丰富，结构清晰，逻辑性强，易于理解。你对每个概念都给出了详细的代码示例，这对于读者理解和实践非常有帮助。
然而，我发现了一些可以改进的地方。在你的博客中，你没有提到二叉树的一些其他重要概念，例如平衡二叉树、满二叉树和完全二叉树等。这些概念在实际应用中也非常重要，我建议你可以在博客中添加这些内容。此外，你在解释线索二叉树时，没有提到线索二叉树的应用，比如可以使用线索二叉树进行非递归遍历，这也是线索二叉树的一个重要应用。在解释哈夫曼树时，你只提到了哈夫曼树的构造方法，但没有提到哈夫曼树的一些重要性质，例如哈夫曼树是最优二叉树，以及哈夫曼树的带权路径长度是最短的等。我建议你可以在博客中补充这些内容。
总的来说，你的博客非常有价值，但还有一些可以改进的地方。我期待看到你的博客在未来变得更加完善。