当前位置: 首页 > article >正文

【学习笔记】数据结构(六 ②)

树和二叉树(二)

文章目录

  • 树和二叉树(二)
      • 6.3.2 线索二叉树
    • 6.4 树和森林
      • 6.4.1 树的存储结构
      • 6.4.2 森林与二叉树的转换
      • 6.4.3 树和森林的遍历
    • 6.5 树与等价问题
      • 6.5.1 等价定义
      • 6.5.2 划分等价类的方法
      • 6.5.3 划分等价类的具体操作 - 并查集MFSet
      • 6.5.4 用树型结构表示集合
      • 6.5.5 并查集及其优化
    • 6.6 赫夫曼树及其应用
      • 6.6.1 最优二叉树(赫夫曼树)
      • 6.6.2 赫夫曼编码
    • 6.7 回溯法与树的遍历
    • 6.8 树的计数

6.3.2 线索二叉树

lchildLTagdataRTagrchild
  • LTag = 0 lchild 域指示结点的左孩子
  • LTag = 1 lchild 域指示结点的前驱
  • RTag = 0 rchild域指示结点的右孩子
  • RTag= 1 rchild域指示结点的后继

以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结前驱和后继的指针,叫做线索。加上线索的二叉树称之为线索二叉树 (Threaded Binary Tree) 。

对二叉树 以某种次序遍历使其变为线索二叉树的过程叫做线索化

#define TElemType char//宏定义,结点中数据域的类型
//枚举,Link(孩子)为0,Thread(线索)为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {
    TElemType data;//数据域
    struct BiThrNode* lchild, * rchild;//左孩子,右孩子指针域
    PointerTag LTag, RTag;//标志域,枚举类型
}BiThrNode, * BiThrTree;

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

  • 先序线索化

    在这里插入图片描述

/*  先序线索化  */
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

#define TElemType char//宏定义,结点中数据域的类型
//枚举,Link为0,Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {
    TElemType data;//数据域
    struct BiThrNode* lchild, * rchild;//左孩子,右孩子指针域
    PointerTag LTag, RTag;//标志域,枚举类型
}BiThrNode, * BiThrTree;


//创建二叉树
BiThrTree CreateBiTree();
//创建线索二叉树
void CreatePreThread(BiThrTree T);
//先序遍历线索化
void PreThread(BiThrTree T);
void Visit(BiThrNode* q);

//后继
BiThrNode* NextNode(BiThrNode* p);
//对先序线索二叉树进行先序遍历
void PrintElement(TElemType e);
void PreOrder(BiThrTree T);


BiThrNode* pre = NULL;

int main() {
    BiThrTree T = NULL;
    printf("输入前序二叉树:\n");  // abd#g##e##cf###
    T = CreateBiTree();
    CreatePreThread(T);
    PreOrder(T);
    return 0;
}

//先序创建二叉树
BiThrTree CreateBiTree() {
    char ch;
    if (scanf(" %c", &ch) != 1) { // 检查输入是否成功
        // 输入失败,可能是文件结束符或错误输入
        exit(EXIT_FAILURE);
    }
    if (ch != '#') {
        BiThrNode* node = (BiThrNode*)malloc(sizeof(BiThrNode)); // 分配内存
        if (node == NULL) {
            // 内存分配失败
            perror("内存分配失败");
            exit(EXIT_FAILURE);
        }
        node->data = ch;
        node->lchild = CreateBiTree(); // 递归创建左子树
        node->rchild = CreateBiTree(); // 递归创建右子树
        node->LTag = Link;
        node->RTag = Link;
        return node;
    }
    else {
        return NULL;
    }
}

/*
对二叉树进行线索化
*/
void CreatePreThread(BiThrTree T)
{
    pre = NULL;
    if (T)
    {
        PreThread(T); // 先序线索化
        if (pre->rchild == NULL)
        {
            pre->RTag = Thread; // 处理最后一个结点
        }
    }
}

// 先序遍历 - 边遍历边线索化
void PreThread(BiThrTree T)
{
    if (T)
    {
        Visit(T);
        if (T->LTag == 0)
        {
            PreThread(T->lchild);
        }
        if (T->RTag == 0)
        {
            PreThread(T->rchild);
        }
    }
}

void Visit(BiThrNode* q)
//线索化
{
    if (q->lchild == NULL)
    {
        q->lchild = pre;
        q->LTag = Thread;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;
        pre->RTag = Thread;
    }
    pre = q;
}

//找先序后继:根左右
/*
① 若 p->RTag == 1,则 next = p->rchild
② 若 p->RTag == 0,则 如果p有左孩子,next=p的左孩子;如果p没有左孩子,next=p的右孩子
*/
BiThrNode* NextNode(BiThrNode* p)
//寻找p的后继结点
{
    if (p->RTag == 1)
    {
        return p->rchild;
    }
    if (p->RTag == 0)
    {
        if (p->lchild && p->LTag == 0)
            return p->lchild;
        else
            return p->rchild;
    }
    
}
/*
对先序线索二叉树进行先序遍历
*/
void PrintElement(TElemType e)
{
    printf("%c ", e);
}

void PreOrder(BiThrTree T)
{
    BiThrNode* p = T;
    for (p; p != NULL; p = NextNode(p))
    {
        PrintElement(p->data);
    }
}
  • 中序线索化

在这里插入图片描述

/*  中序线索化  */
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

#define TElemType char//宏定义,结点中数据域的类型
//枚举,Link为0,Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {
    TElemType data;//数据域
    struct BiThrNode* lchild, * rchild;//左孩子,右孩子指针域
    PointerTag LTag, RTag;//标志域,枚举类型
}BiThrNode, * BiThrTree;


//创建二叉树
BiThrTree CreateBiTree();
//创建线索二叉树
void CreateInThread(BiThrTree T);
//中序遍历线索化
void InThread(BiThrTree T);
void Visit(BiThrNode* q);

//寻找p最左下结点
BiThrNode* FirstNode(BiThrNode* p);
//获取后继结点
BiThrNode* NextNode(BiThrNode* p);

//对中序线索二叉树进行中序遍历
void PrintElement(TElemType e);
void InOrder(BiThrTree T);

//寻找p最右下结点
BiThrNode* LastNode(BiThrNode* p);
//获取前驱结点
BiThrNode* PreNode(BiThrNode* p);
//对中序线索二叉树进行逆向中序遍历
void RevInOrder(BiThrTree T);

BiThrNode* pre = NULL;

int main() {
    BiThrTree T = NULL;
    printf("输入前序二叉树:\n");  // abd#g##e##cf###
    T = CreateBiTree();
    CreateInThread(T);
    printf("对中序线索二叉树进行中序遍历\n");
    InOrder(T); // d g b e a f c
    printf("\n对中序线索二叉树进行逆向中序遍历\n");
    RevInOrder(T); // c f a e b g d
    return 0;
}

//先序创建二叉树
BiThrTree CreateBiTree() {
    char ch;
    if (scanf(" %c", &ch) != 1) { // 检查输入是否成功
        // 输入失败,可能是文件结束符或错误输入
        exit(EXIT_FAILURE);
    }
    if (ch != '#') {
        BiThrNode* node = (BiThrNode*)malloc(sizeof(BiThrNode)); // 分配内存
        if (node == NULL) {
            // 内存分配失败
            perror("内存分配失败");
            exit(EXIT_FAILURE);
        }
        node->data = ch;
        node->lchild = CreateBiTree(); // 递归创建左子树
        node->rchild = CreateBiTree(); // 递归创建右子树
        node->LTag = Link;
        node->RTag = Link;
        return node;
    }
    else {
        return NULL;
    }
}

/*
对二叉树进行线索化
*/
void CreateInThread(BiThrTree T)
{
    pre = NULL;
    if (T)
    {
        InThread(T); // 中序线索化
        if (pre->rchild == NULL)
        {
            pre->RTag = Thread; // 处理最后一个结点
        }
    }
}

// 中序遍历 - 边遍历边线索化
void InThread(BiThrTree T)
{
    if (T)
    {
        InThread(T->lchild);
        Visit(T);
        InThread(T->rchild);
    }
}

void Visit(BiThrNode* q)
//线索化
{
    if (q->lchild == NULL)
    {
        q->lchild = pre;
        q->LTag = Thread;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;
        pre->RTag = Thread;
    }
    pre = q;
}

//找中序后继:左根右
/*
① 若 p->RTag == 1,则 next = p->rchild
② 若 p->RTag == 0,则 next = p的右子树最左下结点
*/
BiThrNode* FirstNode(BiThrNode* p)
//寻找p最左下结点
{
    while (p->LTag == 0)
    {
        p = p->lchild;
    }
    return p;
}
BiThrNode* NextNode(BiThrNode* p)
//寻找p的后继结点
{
    if (p->RTag == 0)
    {
        return FirstNode(p->rchild);//寻找p的右子树最左下结点
    }
    else
    {
        return p->rchild;
    }
}

/*
对中序线索二叉树进行中序遍历
*/
void PrintElement(TElemType e)
{
    printf("%c ", e);
}

void InOrder(BiThrTree T)
{
    BiThrNode* p = FirstNode(T);
    for (p; p != NULL; p = NextNode(p))
    {
        PrintElement(p->data);
    }
}

//找中序前驱:左根右
/*
① 若 p->LTag == 1,则 pre = p->lchild
② 若 p->LTag == 0,则 pre = p的左子树最右下结点
*/
BiThrNode* LastNode(BiThrNode* p)
//寻找p最右下结点
{
    while (p->RTag == 0)
    {
        p = p->rchild;
    }
    return p;
}
BiThrNode* PreNode(BiThrNode* p)
//寻找p的前驱结点
{
    if (p->LTag == 0)
    {
        return LastNode(p->lchild);//寻找p的左子树最右下结点
    }
    else
    {
        return p->lchild;
    }
}
/*
对中序线索二叉树进行逆向中序遍历
*/
void RevInOrder(BiThrTree T)
{
    BiThrNode* p = LastNode(T);
    for (p; p != NULL; p = PreNode(p))
    {
        PrintElement(p->data);
    }
}
  • 后序线索化

    在这里插入图片描述

/*  后序线索化  */
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

#define TElemType char//宏定义,结点中数据域的类型
//枚举,Link为0,Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {
    TElemType data;//数据域
    struct BiThrNode* lchild, * rchild;//左孩子,右孩子指针域
    PointerTag LTag, RTag;//标志域,枚举类型
}BiThrNode, * BiThrTree;


//创建二叉树
BiThrTree CreateBiTree();
//创建线索二叉树
void CreatePostThread(BiThrTree T);
//后序遍历线索化
void PostThread(BiThrTree T);
void Visit(BiThrNode* q);

//寻找前驱
BiThrNode* PreNode(BiThrNode* p);
//逆向遍历
void PrintElement(TElemType e);
void RevPostOrder(BiThrTree T);


BiThrNode* pre = NULL;

int main() {
    BiThrTree T = NULL;
    printf("输入前序二叉树:\n");  // abd#g##e##cf###
    T = CreateBiTree();
    CreatePostThread(T);
    //正序:g d e b f c a
    //逆序:a c f b e d g
    RevPostOrder(T);
    return 0;
}

//先序创建二叉树
BiThrTree CreateBiTree() {
    char ch;
    if (scanf(" %c", &ch) != 1) { // 检查输入是否成功
        // 输入失败,可能是文件结束符或错误输入
        exit(EXIT_FAILURE);
    }
    if (ch != '#') {
        BiThrNode* node = (BiThrNode*)malloc(sizeof(BiThrNode)); // 分配内存
        if (node == NULL) {
            // 内存分配失败
            perror("内存分配失败");
            exit(EXIT_FAILURE);
        }
        node->data = ch;
        node->lchild = CreateBiTree(); // 递归创建左子树
        node->rchild = CreateBiTree(); // 递归创建右子树
        node->LTag = Link;
        node->RTag = Link;
        return node;
    }
    else {
        return NULL;
    }
}

/*
对二叉树进行线索化
*/
void CreatePostThread(BiThrTree T)
{
    pre = NULL;
    if (T)
    {
        PostThread(T); // 后序线索化
        if (pre->rchild == NULL)
        {
            pre->RTag = Thread; // 处理最后一个结点
        }
    }
}

// 后序遍历 - 边遍历边线索化
void PostThread(BiThrTree T)
{
    if (T)
    {
        PostThread(T->lchild);
        PostThread(T->rchild);
        Visit(T);
    }
}

void Visit(BiThrNode* q)
//线索化
{
    if (q->lchild == NULL)
    {
        q->lchild = pre;
        q->LTag = Thread;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;
        pre->RTag = Thread;
    }
    pre = q;
}

//找后序前驱:左右根
/*
① 若 p->LTag == 1,则 pre = p->lchild
② 若 p->LTag == 0,则 如果p有右孩子,pre=p的右孩子;如果p没有右孩子,pre=p的左孩子
*/

BiThrNode* PreNode(BiThrNode* p)
//寻找p的前驱结点
{
    if (p->LTag == 1)
    {
        return p->lchild;//寻找p的左子树最右下结点
    }
    else
    {
        if (p->rchild && p->RTag == 0)
        {
            return p->rchild;
        }
        else
        {
            return p->lchild;
        }
    }
}
/*
对后序线索二叉树进行逆向的后序遍历
*/
void PrintElement(TElemType e)
{
    printf("%c ", e);
}

void RevPostOrder(BiThrTree T)
{
    BiThrNode* p = T;
    for (p; p != NULL; p = PreNode(p))
    {
        PrintElement(p->data);
    }
}

6.4 树和森林

6.4.1 树的存储结构

  • 双亲表示法(顺序存储)

    在这里插入图片描述

    #define MAX_TREE_SIZE 100   //树中最多结点数
    typedef char ElemType;
    typedef struct {            //结点结构
        ElemType data;          //数据元素
        int parent;             //双亲位置域
    }PTNode;
    
    typedef struct {                   //树结构
        PTNode nodes[MAX_TREE_SIZE];  
        int r, n;                      //根的位置和结点数
    }PTree;
    

    可以根据结点的parent 指针很容易找到它的双亲结点,所用的时间复杂度为0(1),直到parent为-1时,表示找到了树结点的根。
    要找到结点的孩子只能遍历整个结构。

  • 孩子表示法(顺序+链式存储)

    在这里插入图片描述

    #define MAX_TREE_SIZE 100   //树中最多结点数
    typedef char ElemType;
    
    typedef struct CTNode{   //孩子结点
        int child;
        struct CTNode* next;
    }* ChildPtr;
    
    typedef struct {
        ElemType data;
        ChildPtr firstchild;  //孩子链表头指针
    }CTBox;
    
    typedef struct {
        CTBox nodes[MAX_TREE_SIZE];
        int n, r; //结点数和根的位置
    }CTree;
    

    查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树就对头结点的数组循环即可。但是查找某个结点的双亲, 需要整棵树遍历才行。

  • 孩子兄弟表示法(链式存储)

    在这里插入图片描述

    typedef struct CSNode{  
        ElemType data;
        struct CSNode * firstchild, *nextsibling;
    }CSNode, * CSTree;
    

6.4.2 森林与二叉树的转换

  • 树转换为二叉树

    在这里插入图片描述

  • 森林转化为二叉树

    在这里插入图片描述

  • 二叉树转化为森林

    在这里插入图片描述

6.4.3 树和森林的遍历

  • 树的遍历

    1️⃣先根遍历 / 深度优先遍历

    ​ 先访问树的根结点,然后依次先根遍历根的每棵子树

    2️⃣后根遍历 / 深度优先遍历

    ​ 先依次后根遍历每棵子树,然后访问根结点

    3️⃣层次遍历(用队列实现) / 广度优先遍历

    ​ ①若树非空,则根节点入队

    ​ ②若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队

    ​ ③重复②直到队列为空

    在这里插入图片描述

  • 森林的遍历

    1️⃣先序遍历

    ​ 若森林为非空,则按如下规则进行遍历:

    ​ 访问森林中第一棵树的根结点。

    ​ 先序遍历第一棵树中根结点的子树森林。

    ​ 先序遍历除去第一棵树之后剩余的树构成的森林。

    2️⃣中序遍历

    ​ 若森林为非空,则按如下规则进行遍历:

    ​ 中序遍历森林中第一棵树的根结点的子树森林。

    ​ 访问第一棵树的根结点。

    ​ 中序遍历除去第一棵树之后剩余的树构成的森林。

    在这里插入图片描述

6.5 树与等价问题

6.5.1 等价定义

  • 等价关系

    A是一个非空集,R是A上的一个二元关系,若R有自反性对称性、传递性,则说R是A上的等价关系。

    设R是集合A上的一个二元关系,即R ⊆ A x A。
    定义1:对于任意的x∈A,均有(x,x)∈R, 则称关系R有自反性或称R是A上的自反关系。
    定义2: 对于任意的x,y∈A,若(x,y)∈R,就有(y,x)∈ R,则称关系R有对称性,或称R是A上的对称关系。
    定义3: 对于任意的x,y,z∈A,若(x,y)∈ R且(y,z)∈R,就有(x,z)∈R,则称关系R有传递性,或称R是A上的传递关系。

  • 等价类

    设R是集合S的等价关系。对任何x∈S,由[x]R = {y|y∈S ∧ xRy} 给出的集合[ x ]R ⊆ S 称 为由于x ∈ S生成的一个R等价类。

    (设R是定义在集合A上的等价关系。与A中的一个元素a有关系的所有元素的集合叫作a的等价类。A的关于R的等价类记作[a]R。当只考虑一个关系时,我们将省去下标R并把这个等价类写作[a]。)

    若R是集合S上的一个等价关系,则由这个等价关系可产生这个集合的唯一划分,即可按R将S划分为若干不相交的子集S1, S2,…,他们的并为S,则这些子集Si便为S的等价类。

    在这里插入图片描述

6.5.2 划分等价类的方法

​ (1) 令S中每个元素各自形成一个只含单个成员的子集,记作 S1, S2 , …, Sn

​ (2) 重复读入m个偶对,对每个读入的偶对 (x,y) 判定 所属子集。

​ 假设 x∈Si,y∈Sj,若 Si ≠ Sj,则将Si并入Sj并置Si为空(或将Sj并入Si并置 Sj空)。

​ (3) 当m个偶对都被处理过后, S1, S2 , …, Sn中所有非空子集即为S的R等价类。

6.5.3 划分等价类的具体操作 - 并查集MFSet

  • 其一是构造只含单个成员的集 合;
  • 其二是判定某个单元素所在子集;(查)
  • 其三是归并两个互不相交的集合为一个集合。(并)

MFSet的ADT:

ADT MFSet{
    数据对象: 若设S是MFSet型的集合,则它由 n(n>O)个子集Si, (i = 12... ,n) 构成,每个子集的成员都是子界[-maxnumber .. maxnumber 内的整数;
	数据关系: S1∪S2∪ … ∪Sn=S Si⊂S(i=l,2,•••,n)
	基本操作:
		Initial(&S, n, x1 , x2 ,……,xn);
        操作结果:初始化操作。构造一个由 个子集(每个子集只含单个成员 xi) 构成的集合S
		Find(S, x); 
		初始条件:S是已存在的集合, x是S中某个子集的成员。
		操作结果:查找函数。确定S中x所属子集Si
		Merge(&S, i, j);
		初始条件:Si,Sj是S中的两个互不相交的非空集合。
		操作结果:归并操作。将Si和Sj中的一个并入另一个中
}ADT MFSet;

6.5.4 用树型结构表示集合

  • 以森林F =( T1 , T2 , . . . , Tn )表示MFSet型的集合S

​ 森林中的每一棵树Ti ( T1 , T2 , . . . , Tn )表示S中的一个元素——子集 Si(Si ⊂ S, i= 1,2, …,n)

​ 树中的每个结点表示对应子集Si中的一个成员x

​ 令每个结点含有一个指向其双亲的指针,并约定根结点的成员兼作子集的名字

以采用双亲表示法来作树的存储结构

  • 由于各子集成员均不相同,"并操作"只需将一棵子集树的根指向另一子集树的根即可;
  • 完成"查找"某个成员所在集合的操作,只需从该成员结点出发,顺链而进,直至找到树的根结点为止.。
// ---- 树的双亲表存储表示 ----
#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构
    ElemType data;          //数据元素
    int parent;             //双亲位置域
}PTNode;

typedef struct {                   //树结构
    PTNode nodes[MAX_TREE_SIZE];  
    int r, n;                      //根的位置和结点数
}PTree;

//---- MFSet的树的双亲存储表示 ----
typedef PTree MFSet;

6.5.5 并查集及其优化

优化前最坏的时间复杂度

​ 查:=最坏树高=O(n)

​ 将n个独立元素通过多次Union合并为一个集合:O(n2)

并优化后树高不超过 ⌊log2n⌋+1 ,最坏的时间复杂度

​ 查:O(log2n)

​ 将n个独立元素通过多次Union合并为一个集合:O(nlog2n)

find优化后最坏的时间复杂度

​ 查:O(α(n))

​ 将n个独立元素通过多次Union合并为一个集合:O(nα(n))

​ α(n) 是一个增长极其缓慢的函数,对于通常所见到的正整数n而言, α(n) ≤ 4

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

// ---- 树的双亲表存储表示 ----
#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构
    ElemType data;          //数据元素
    int parent;             //双亲位置域
}PTNode;

typedef struct {                   //树结构
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;                      //根的位置和结点数
}PTree;

//---- MFSet的树的双亲存储表示 ----
typedef PTree MFSet;

void Initial(MFSet* mfset, ElemType elements[], int parent[], int size)
{
    mfset->n = size; // 设置结点数
    mfset->r = -1;   // 假设根节点的双亲位置为-1

    for (int i = 0; i < size; i++) {
        mfset->nodes[i].data = elements[i]; // 设置数据元素
        mfset->nodes[i].parent = parent[i]; // 设置双亲位置
    }
}


// 打印MFSet
void printMFSet(MFSet mfset) {
    printf("MFSet:\n");
    for (int i = 0; i < mfset.n; i++) {
        printf("Node %d: Data = %c, Parent = %d\n", i, mfset.nodes[i].data, mfset.nodes[i].parent);
    }
}

//查 - 找i所属集合的根节点  最坏的时间复杂度O(d), 其中d是树的深度
int Find_MFSet(MFSet s, int i)
{
    if (i<0 || i>s.n - 1)
    {
        return -2;
    }
    int j;
    for (j = i; s.nodes[j].parent >= 0; j = s.nodes[j].parent);
    return j;
}

//并 -i,j两个集合合并为一个  时间复杂度O(1)
void Merge_MFSet(MFSet* s, int i, int j)
{
    if (i<0 || i>(*s).n - 1 || j<0 || j>(*s).n - 1)
    {
        return -2;
    }
    if (i == j)
    {
        return -2;
    }
    (*s).nodes[j].parent = i; //j并到i
}



int main() {
    ElemType elements[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M' };
    int parent[] = { -1, 0, -1, -1, 1, 1, 2, 3, 3, 3, 4, 4, 7 };
    int size = sizeof(elements) / sizeof(elements[0]);
    MFSet myMFSet;

    Initial(&myMFSet, elements, parent, size);
    printMFSet(myMFSet);

    int gen = Find_MFSet(myMFSet, parent[6]);
    printf("G所在集合的根节点:%d, 根节点为:%c\n", gen, myMFSet.nodes[gen].data);
    Merge_MFSet(&myMFSet, 0, 2); // C集合合并到A集合
    printMFSet(myMFSet);
    int gen1 = Find_MFSet(myMFSet, parent[6]);
    printf("G所在集合的根节点:%d, 根节点为:%c\n", gen1, myMFSet.nodes[gen1].data);
    return 0;
}

并优化

  • 在作“并”操作之前先判别子集中所含成员的数目,然后令含成员少的子集树根结点指向含成员多的子集的根

    在这里插入图片描述

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    #include <stdlib.h>
    
    // ---- 树的双亲表存储表示 ----
    #define MAX_TREE_SIZE 100   //树中最多结点数
    typedef char ElemType;
    typedef struct {            //结点结构
        ElemType data;          //数据元素
        int parent;             //双亲位置域
    }PTNode;
    
    typedef struct {                   //树结构
        PTNode nodes[MAX_TREE_SIZE];
        int r, n;                      //根的位置和结点数
    }PTree;
    
    //---- MFSet的树的双亲存储表示 ----
    typedef PTree MFSet;
    
    void Initial(MFSet* mfset, ElemType elements[], int parent[], int size)
    {
        mfset->n = size; // 设置结点数
        mfset->r = -1;   // 假设根节点的双亲位置为-1
    
        for (int i = 0; i < size; i++) {
            mfset->nodes[i].data = elements[i]; // 设置数据元素
            mfset->nodes[i].parent = parent[i]; // 设置双亲位置
        }
    }
    
    
    // 打印MFSet
    void printMFSet(MFSet mfset) {
        printf("MFSet:\n");
        for (int i = 0; i < mfset.n; i++) {
            printf("Node %d: Data = %c, Parent = %d\n", i, mfset.nodes[i].data, mfset.nodes[i].parent);
        }
    }
    
    //并的优化 
    void Mix_MFSet(MFSet* s, int i, int j)
    {
        if (i<0 || i>(*s).n - 1 || j<0 || j>(*s).n - 1)
        {
            return -2;
        }
        if (s->nodes[i].parent > s->nodes[j].parent)
        {
            //Si 所含成员数比 Sj少
            s->nodes[j].parent += s->nodes[i].parent;
            s->nodes[i].parent = j;
    
        }
        else
        {
            s->nodes[i].parent += s->nodes[j].parent;
            s->nodes[j].parent = i;
        }
    }
    
    
    int main() {
        printf("------------------------优化-----------------------");
        ElemType elements[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M' };
        int parent[] = { -6, 0, -2, -5, 1, 1, 2, 3, 3, 3, 4, 4, 7 };
        int size = sizeof(elements) / sizeof(elements[0]);
        MFSet myMFSet;
        Initial(&myMFSet, elements, parent, size);
        printMFSet(myMFSet);
        printf("----------------------合并A和C----------------------");
        Mix_MFSet(&myMFSet, 0, 2);
        printMFSet(myMFSet);
       /* printf("----------------------合并C和D----------------------");
        Mix_MFSet(&myMFSet, 2, 3);
        printMFSet(myMFSet);*/
        return 0;
    }
    

查找优化

  • 压缩路径–Find 操作,先找到根节点,再将查找路径上所有结点都挂到根结点下

    在这里插入图片描述

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    #include <stdlib.h>
    
    // ---- 树的双亲表存储表示 ----
    #define MAX_TREE_SIZE 100   //树中最多结点数
    typedef char ElemType;
    typedef struct {            //结点结构
        ElemType data;          //数据元素
        int parent;             //双亲位置域
    }PTNode;
    
    typedef struct {                   //树结构
        PTNode nodes[MAX_TREE_SIZE];
        int r, n;                      //根的位置和结点数
    }PTree;
    
    //---- MFSet的树的双亲存储表示 ----
    typedef PTree MFSet;
    
    void Initial(MFSet* mfset, ElemType elements[], int parent[], int size)
    {
        mfset->n = size; // 设置结点数
        mfset->r = -1;   // 假设根节点的双亲位置为-1
    
        for (int i = 0; i < size; i++) {
            mfset->nodes[i].data = elements[i]; // 设置数据元素
            mfset->nodes[i].parent = parent[i]; // 设置双亲位置
        }
    }
    
    
    // 打印MFSet
    void printMFSet(MFSet mfset) {
        printf("MFSet:\n");
        for (int i = 0; i < mfset.n; i++) {
            printf("Node %d: Data = %c, Parent = %d\n", i, mfset.nodes[i].data, mfset.nodes[i].parent);
        }
    }
    
    //查 - 优化(压缩路径)
    int Find_MFSet(MFSet *s, int i)
    {
        if (i<0 || i>s->n-1)
        {
            return -2;
        }
        int root = i;
        while (s->nodes[root].parent >= 0)
        {
            root = s->nodes[root].parent;
        }
        while (i != root)
        {
            int t = s->nodes[i].parent;
            s->nodes[i].parent = root;
            i = t;
        }
        return root;
    }
    
    int main() {
        ElemType elements[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M' };
        int parent[] = { -1, 0, -1, -1, 1, 1, 2, 3, 3, 3, 4, 4, 7 };
        int size = sizeof(elements) / sizeof(elements[0]);
        MFSet myMFSet;
    
        Initial(&myMFSet, elements, parent, size);
        printMFSet(myMFSet);
    
        printf("----------------------查找优化----------------------\n");
        int gen = Find_MFSet(&myMFSet, 11);
        printf("G所在集合的根节点:%d, 根节点为:%c\n", gen, myMFSet.nodes[gen].data);
        printMFSet(myMFSet);
        return 0;
    }
    

6.6 赫夫曼树及其应用

6.6.1 最优二叉树(赫夫曼树)

  • 从树中一个结点到另一个结点之间的分支构成这 两个结点之间的路径,路径上的分支数目称做路径长度

  • 树的路径长度是从树根到每一 结点的路径长度之和。

  • 树的带权路径长度(Weighted Path Length of Tree,简记为WPL):定义为树中所有叶子结点的带权路径长度之和.

    • 结点的权值:在一些应用中,赋予树中结点的一个有某种意义的实数。

    • 结点的带权路径长度:从该结点到树根之间的路径长度与该结点上权值的乘积。

  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树(Full Binary Tree)或者哈夫曼树(Huffman Tree)

    特点:

    • 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

    • 最优二叉树中,权越大的叶子离根越近。

    • 最优二叉树的形态不唯一,WPL最小。

      在这里插入图片描述

6.6.2 赫夫曼编码

任一字符的编码都不是另一个字符的编码的前缀,这种编码称为前缀码

在这里插入图片描述

在这里插入图片描述

//方法一 - 从叶子到根
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) {
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
    char* cd = (char*)malloc(n * sizeof(char)); //存放结点哈夫曼编码的字符串数组
    cd[n - 1] = '\0';//字符串结束符

    for (int i = 1; i <= n; i++) {
        //cd数组的下标,用于逆序存储到cd数组
        int start = n - 1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while (j != 0) {
            // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
            if (HT[j].lchild == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
            //以父结点为孩子结点,继续朝树根的方向遍历
            c = j;
            j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char*)malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    //使用malloc申请的cd动态数组需要手动释放
    free(cd);
}

在这里插入图片描述

// 方法二: 从根到叶子结点
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) {
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
    int m = 2 * n - 1;
    int p = m;
    int cdlen = 0;
    char* cd = (char*)malloc(n * sizeof(char));
    

    for (int i = 1; i <= m; i++) {
        HT[i].weight = 0;
    }
    //一开始 p 初始化为 m,也就是从树根开始。一直到p为0
    while (p) {
        //如果当前结点一次没有访问,进入这个if语句
        if (HT[p].weight == 0) {
            HT[p].weight = 1;//重置访问次数为1
            //如果有左孩子,则访问左孩子,并且存储走过的标记为0
            if (HT[p].lchild != 0) {
                p = HT[p].lchild;
                cd[cdlen++] = '0';
            }
            //当前结点没有左孩子,也没有右孩子,说明为叶子结点,直接记录哈夫曼编码
            else if (HT[p].rchild == 0) {
                (*HC)[p] = (char*)malloc((cdlen + 1) * sizeof(char));
                cd[cdlen] = '\0';
                strcpy((*HC)[p], cd);
            }
        }
        //如果weight为1,说明访问过一次,即是从其左孩子返回的
        else if (HT[p].weight == 1) {
            HT[p].weight = 2;//设置访问次数为2
            //如果有右孩子,遍历右孩子,记录标记值 1
            if (HT[p].rchild != 0) {
                p = HT[p].rchild;
                cd[cdlen++] = '1';
            }
        }
        //如果访问次数为 2,说明左右孩子都遍历完了,返回父结点
        else {
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}

存储结构

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct {
	unsigned int weight;
	unsigned int parent, lchild, rchild;
}HTNode, * HuffmanTree;  //动态分配数组存储赫夫曼树

typedef char** HuffmanCode;   //动态分配数组存储赫夫曼编码表

void Select(HuffmanTree HT, int end, int* s1, int* s2)
{
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;

    /*找到还没构建树的结点*/
    //i取值[1,9) -> [1,n+1) -> [1,n]
    while (HT[i].parent != 0 && i < end) {
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;

    i++;
    while (HT[i].parent != 0 && i < end) {
        i++;
    }
    //对找到的两个结点比较大小,min2为大的,min1为小的
    if (HT[i].weight < min1) {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
    }
    else {
        min2 = HT[i].weight;
        *s2 = i;
    }
    //两个结点和后续的所有未构建成树的结点做比较
    for (int j = i + 1; j < end; j++)
    {
        //如果有父结点,直接跳过,进行下一个
        if (HT[j].parent != 0) {
            continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if (HT[j].weight < min1) {
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
        //如果介于两者之间,min2赋值为新的结点的位置下标
        else if (HT[j].weight >= min1 && HT[j].weight < min2) {
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}

void CreateHuffmanTree(HuffmanTree* HT, int* w, int n)
{
    if (n <= 1) return; // 如果只有一个编码就相当于0
    int m = 2 * n - 1; // 赫夫曼树总结点数,n + (n - 1)【 4个结点-创建的赫夫曼树总共需要7个结点】
    *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 0号位置不用
    // 初始化赫夫曼树中的所有结点
    if (*HT)
    {
        for (int i = 1; i <= n; i++)
        {
            ((*HT) + i)->weight = *(w + i - 1);
            ((*HT) + i)->parent = 0;
            ((*HT) + i)->lchild = 0;
            ((*HT) + i)->rchild = 0;
        }
        //从树组的下标 n+1 开始初始化赫夫曼树中除叶子结点外的结点
        for (int i = n + 1; i <= m; i++)
        {
            ((*HT) + i)->weight = 0;
            ((*HT) + i)->parent = 0;
            ((*HT) + i)->lchild = 0;
            ((*HT) + i)->rchild = 0;
        }
        //构建赫夫曼树
        for (int i = n + 1; i <= m; i++)
        {
            int s1, s2;
            Select(*HT, i, &s1, &s2);
            (*HT)[s1].parent = i; 
            (*HT)[s2].parent = i;
            (*HT)[i].lchild = s1;
            (*HT)[i].rchild = s2;
            (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
        }
    }
    
}
//方法一实现:
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n)
{ // w存放n个字符的权值(均 >O), 构造赫夫曼树HT, 并求出n个字符的赫夫曼编码HC
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
    char* cd = (char*)malloc(n * sizeof(char)); //存放结点哈夫曼编码的字符串数组
    cd[n - 1] = '\0';//字符串结束符

    for (int i = 1; i <= n; i++) {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n - 1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while (j != 0) {
            // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
            if (HT[j].lchild == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
            //以父结点为孩子结点,继续朝树根的方向遍历
            c = j;
            j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char*)malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    //使用malloc申请的cd动态数组需要手动释放
    free(cd);
}

//打印哈夫曼编码的函数
void PrintHuffmanCode(HuffmanCode htable, int* w, int n)
{
    printf("Huffman code : \n");
    for (int i = 1; i <= n; i++)
        printf("%d code = %s\n", w[i - 1], htable[i]);
}
int main()
{
    int w[8] = { 5,29,7,8,14,23,3,11 };
    int n = 8;
    HuffmanTree htree;
    HuffmanCode htable;
    CreateHuffmanTree(&htree, w, n);
    HuffmanCoding(htree, &htable, n);
    PrintHuffmanCode(htable, w, n);
	return 0;
}

在这里插入图片描述

6.7 回溯法与树的遍历

回溯法也可以叫做回溯搜索法,它是⼀种搜索的⽅式

回溯法(backtracking)是设计递归过程的一种重要方法,它的求解过程实质上是一个先序遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。回溯是递归的副产品,只要有递归就会有回溯。

可以解决的问题:

  • 组合:N个数⾥⾯按⼀定规则找出k个数的集合(无序)
  • 切割:⼀个字符串按⼀定规则有⼏种切割⽅式
  • 子集:⼀个N个数的集合⾥有多少符合条件的⼦集
  • 排列:N个数按⼀定规则全排列,有⼏种排列⽅式(有序)
  • 棋盘:N皇后,解数独等等

模板框架:

在这里插入图片描述

void backtracking(参数) {
	if (终⽌条件) {
		存放结果;
		return;
	}
	for (选择:本层集合中元素(树中节点孩⼦的数量就是集合的⼤⼩)) {
		处理节点;
		backtracking(路径,选择列表); // 递归
		回溯,撤销处理结果
	}
}
  • 组合问题

    • 给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。

      示例: 输⼊: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

      在这里插入图片描述

      #include <stdio.h>
      #include <stdlib.h>
      
      typedef struct {
          int** result;
          int* path;
          int resultSize;
          int pathSize;
      } Solution;
      
      void backtracking(Solution* sol, int n, int k, int startIndex) {
          if (sol->pathSize == k) {
              sol->result[sol->resultSize] = (int*)malloc(k * sizeof(int));
              if (sol->result[sol->resultSize])
              {
                  for (int i = 0; i < k; i++) {
                      sol->result[sol->resultSize][i] = sol->path[i];
                  }
                  sol->resultSize++;
                  return;
              }
              return;
          }
          for (int i = startIndex; i <= n; i++) {
              sol->path[sol->pathSize] = i;
              sol->pathSize++;
              backtracking(sol, n, k, i + 1);
              sol->pathSize--; // 回溯,撤销处理的节点
          }
      }
      
      void combine(Solution* sol, int n, int k) {
          sol->resultSize = 0;
          sol->pathSize = 0;
          sol->result = (int**)malloc(10000 * sizeof(int*)); // 假设结果集不会超过10000个
          sol->path = (int*)malloc(k * sizeof(int));
          backtracking(sol, n, k, 1);
      }
      
      void printSolution(Solution* sol, int k) {
          for (int i = 0; i < sol->resultSize; i++) {
              for (int j = 0; j < k; j++) {
                  printf("%d ", sol->result[i][j]);
              }
              printf("\n");
              free(sol->result[i]); // 释放每一行的内存
          }
          free(sol->result); // 释放结果集的内存
          free(sol->path); // 释放路径的内存
      }
      
      int main() {
          Solution sol;
          int n = 4;
          int k = 2;
          combine(&sol, n, k);
          printSolution(&sol, k);
          return 0;
      }
      
    • 剪枝操作

      在这里插入图片描述

      void backtracking(Solution* sol, int n, int k, int startIndex) {
          if (sol->pathSize == k) {
              sol->result[sol->resultSize] = (int*)malloc(k * sizeof(int));
              if (sol->result[sol->resultSize])
              {
                  for (int i = 0; i < k; i++) {
                      sol->result[sol->resultSize][i] = sol->path[i];
                  }
                  sol->resultSize++;
                  return;
              }
              return;
          }
          for (int i = startIndex; i <= n - (k - sol->pathSize) + 1; i++) {
              sol->path[sol->pathSize] = i;
              sol->pathSize++;
              backtracking(sol, n, k, i + 1);
              sol->pathSize--; // 回溯,撤销处理的节点
          }
      }
      
    • 组合总和

      找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。输⼊: k = 2, n = 4

      在这里插入图片描述

      #include <stdio.h>
      #include <stdlib.h>
      
      typedef struct {
          int** result;
          int* path;
          int resultSize;
          int pathSize;
      } Solution;
      
      
      // targetSum:⽬标和,也就是题⽬中的n。
      // k:题⽬中要求k个数的集合。
      // sum:已经收集的元素的总和,也就是path⾥元素的总和。
      // startIndex:下⼀层for循环搜索的起始位置。
      void backtracking(Solution* sol, int targetSum, int n, int k, int sum, int startIndex) {
          if (sol->pathSize == k) {
              if (sum > targetSum) return; // 剪枝操作
              if (sum == targetSum)
              {
                  sol->result[sol->resultSize] = (int*)malloc(k * sizeof(int));
                  if (sol->result[sol->resultSize])
                  {
                      for (int i = 0; i < k; i++) {
                          sol->result[sol->resultSize][i] = sol->path[i];
                      }
                      sol->resultSize++;
                      return;
                  }
              }
              return;
          }
          // 剪枝操作
          for (int i = startIndex; i <= n - (k - sol->pathSize) + 1; i++) {
              sum += i;
              sol->path[sol->pathSize] = i;
              sol->pathSize++;
              backtracking(sol, targetSum, n, k, sum, i + 1);
              sum -= i;
              sol->pathSize--; // 回溯,撤销处理的节点
          }
      
      }
      
      void combine(Solution* sol, int n, int k, int targetSum) {
          sol->resultSize = 0;
          sol->pathSize = 0;
          sol->result = (int**)malloc(10000 * sizeof(int*)); // 假设结果集不会超过10000个
          sol->path = (int*)malloc(k * sizeof(int));
          backtracking(sol, targetSum, n, k, 0, 1);
      }
      
      void printSolution(Solution* sol, int k) {
          for (int i = 0; i < sol->resultSize; i++) {
              for (int j = 0; j < k; j++) {
                  printf("%d ", sol->result[i][j]);
              }
              printf("\n");
              free(sol->result[i]); // 释放每一行的内存
          }
          free(sol->result); // 释放结果集的内存
          free(sol->path); // 释放路径的内存
      }
      
      int main() {
          Solution sol;
          int n = 9;
          int target_sum = 11;
          int k = 3;
          combine(&sol, n, k, target_sum);
          printSolution(&sol, k);
          return 0;
      }
      
  • N皇后

    在n×n格的棋盘上放置彼此不受攻击的n个皇后

    皇后的约束条件: 1. 不能同⾏ 2. 不能同列 3. 不能同斜线

    在这里插入图片描述

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    bool isSafe(int* queens, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col || abs(row - i) == abs(col - queens[i])) {
                return false;
            }
        }
        return true;
    }
    
    void backtrack(int* queens, int row, int N, char*** result, int* resultSize) {
        if (row == N) {
            // 当前解已经找到,将其存入结果数组
            result[*resultSize] = (char**)malloc(N * sizeof(char*));
            for (int i = 0; i < N; i++) {
                result[*resultSize][i] = (char*)malloc((N + 1) * sizeof(char));
                for (int j = 0; j < N; j++) {
                    result[*resultSize][i][j] = (queens[i] == j) ? 'Q' : '.';
                }
                result[*resultSize][i][N] = '\0';
            }
            (*resultSize)++;
            return;
        }
    
        for (int col = 0; col < N; col++) {
            if (isSafe(queens, row, col)) {
                queens[row] = col;
                backtrack(queens, row + 1, N, result, resultSize);
                queens[row] = -1;
            }
        }
    }
    
    
    char*** solveNQueens(int N, int* returnSize) {
        char*** result = (char***)malloc(1000 * sizeof(char**));
        *returnSize = 0;
    
        int* queens = (int*)malloc(N * sizeof(int));
        for (int i = 0; i < N; i++) {
            queens[i] = -1;
        }
    
        backtrack(queens, 0, N, result, returnSize);
        free(queens); // 释放queens数组
        return result;
    }
    
    // 打印所有合法的棋盘配置
    void printSolutions(char*** result, int N, int returnSize) {
        for (int i = 0; i < returnSize; i++) {
            for (int row = 0; row < N; row++) {
                printf("%s\n", result[i][row]);
            }
            printf("\n");
            for (int row = 0; row < N; row++) {
                free(result[i][row]); // 释放每一行的内存
            }
            free(result[i]); // 释放二维数组的内存
        }
        free(result); // 释放结果集的内存
    }
    
    int main() {
        int N = 4; // 例如,解决4皇后问题
        int returnSize;
        char*** result = solveNQueens(N, &returnSize);
    
        printf("Total %d solutions for %d Queens problem:\n", returnSize, N);
        printSolutions(result, N, returnSize);
        return 0;
    }
    

6.8 树的计数

含有n个结点的不相似的二叉树有 1 n + 1 C 2 n n \frac{1}{n+1} C^n_{2n} n+11C2nn

在这里插入图片描述

参考:

教材:

严蔚敏《数据结构》(C语言版).pdf

离散数学及其应用(原书第8版) (Kenneth H.Rosen) .pdf

《代码随想录》回溯算法(V3.0).pdf

视频:

https://www.bilibili.com/video/BV1Zf4y1a77g/?spm_id_from=333.788&vd_source=a89593e8d33b31a56b894ca9cad33d33

https://www.bilibili.com/video/BV1b7411N798/?p=51&spm_id_from=333.880.my_history.page.click&vd_source=a89593e8d33b31a56b894ca9cad33d33

https://www.bilibili.com/video/BV1pu411c7pf/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=a89593e8d33b31a56b894ca9cad33d33

https://www.bilibili.com/video/BV17F411T7Ao?p=195&vd_source=a89593e8d33b31a56b894ca9cad33d33

博客:

https://blog.csdn.net/Real_Fool_/article/details/113930623

https://blog.csdn.net/m0_73633088/article/details/133443742

https://blog.csdn.net/wangrunmin/article/details/7831318

https://blog.csdn.net/Colorful___/article/details/133603913

https://blog.51cto.com/u_13360/6732847

https://zhuanlan.zhihu.com/p/600665635

https://blog.csdn.net/crr411422/article/details/129932889

https://blog.51cto.com/u_15773967/6148952

https://blog.csdn.net/2401_82584055/article/details/138349195

https://mp.weixin.qq.com/s?__biz=Mzg5MjkxNTA5MA==&mid=2247484467&idx=2&sn=3ea1749b1c7c301289a40dac4497e87e&chksm=c03798cef74011d8ead16e27ebea8e3a1df2a9a0242385d328f0ec05973e9b12ef1fa7254e14&scene=27

工具:

https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html


http://www.kler.cn/a/313830.html

相关文章:

  • 「Mac玩转仓颉内测版12」PTA刷题篇3 - L1-003 个位数统计
  • C语言入门到精通(第六版)——第十六章
  • 记录使用documents4j来将word文件转化为pdf文件
  • 群控系统服务端开发模式-应用开发-前端个人信息功能
  • 量化交易系统开发-实时行情自动化交易-3.4.1.2.A股交易数据
  • 01-Ajax入门与axios使用、URL知识
  • git命令大全
  • Vue页面跳转
  • 有关elementui form验证问题,有值却仍然显示不通过
  • 数据结构day2
  • java重点学习-线程池的使用和项目案例
  • C++ | 多态
  • 浅谈C++之运算符
  • 文件上传-php
  • ZionAI应用无代码开发平台 | OPENAIGC开发者大赛企业组AI创新之星奖
  • Spring扩展点系列-MergedBeanDefinitionPostProcessor
  • 企业微信应用消息收发实施记录
  • Spring Boot实现:Java免税商品购物商城全攻略
  • 8. 详细描述一条 SQL 语句在 MySQL 中的执行过程。
  • 深度学习——微积分求导,反向传播
  • 简单多状态dp第三弹 leetcode -买卖股票的最佳时机问题
  • 嵌入式Linux学习笔记(6)-线程处理、线程同步、线程池(c语言实现)
  • Spring Boot与gRPC的完美融合:构建高效用户服务与订单服务通信
  • 视频存储EasyCVR视频监控汇聚管理平台设备录像下载报错404是什么原因?
  • GO GIN 推荐的库
  • 2024年上海初中生古诗文大会倒计时一个半月:来做2024官方模拟题