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个节点

哈夫曼编码

哈夫曼树构成的编码。

考研需要了解的前缀编码，没有任何一个编码是另一个编码的前缀。

GPT-4

首先，我想对你的博客表示赞赏。你对二叉树的解释非常详细，包括了二叉树的基本概念、遍历方式、线索二叉树、树的存储方式以及哈夫曼树等内容。你的博客内容丰富，结构清晰，逻辑性强，易于理解。你对每个概念都给出了详细的代码示例，这对于读者理解和实践非常有帮助。

然而，我发现了一些可以改进的地方。在你的博客中，你没有提到二叉树的一些其他重要概念，例如平衡二叉树、满二叉树和完全二叉树等。这些概念在实际应用中也非常重要，我建议你可以在博客中添加这些内容。此外，你在解释线索二叉树时，没有提到线索二叉树的应用，比如可以使用线索二叉树进行非递归遍历，这也是线索二叉树的一个重要应用。在解释哈夫曼树时，你只提到了哈夫曼树的构造方法，但没有提到哈夫曼树的一些重要性质，例如哈夫曼树是最优二叉树，以及哈夫曼树的带权路径长度是最短的等。我建议你可以在博客中补充这些内容。

总的来说，你的博客非常有价值，但还有一些可以改进的地方。我期待看到你的博客在未来变得更加完善。

leo