408笔记——数据结构树

2022-07-04 数据结构 408考研, 数据结构, 树 0 评论

1.树的基本概念

1.1 树的一些基本术语

（1）结点的度(Degree)：结点的子树个数，如B的度是2，D的度是3

（2）树的度：树种所有结点中最大的度数

（3）叶结点(Leaf)：度为0**的结点

（4）祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点，如A、B、E都是K的祖先

（5）子孙结点(Descendant)：某一结点的子树中的所有结点都是这个结点的子孙

（6）父结点(Parent)/子结点（Child）：有子树的结点是其子树的根结点的父结点，若A结点是B结点的父结点，则称B结点是A结点的子结点，也称孩子结点，拥有同一父结点的各结点彼此是兄弟结点

（7）结点的深度、高度、层次(Level)：根结点在1层，其他任意结点的层数是其父结点层数加1，结点的深度是从根结点自顶向下逐层累加的，结点的高度是从叶结点开始自底向上逐层累加的

（8）树的深度(Depth)：树中所有结点的最大层次是这棵树的深度。

（9）有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树

（10）路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数

（11）森林：森林是m（m≥0）棵互不相交的树的集合。

1.2 树的性质

2.二叉树的概念和性质

2.1 二叉树和度为2的有序树的区别

度为2的树至少有3个结点，而二叉树可以为空
度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子无需区分左右次序，而二叉树无论其孩子子树是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的

2.2 二叉树的性质

（1）非空二叉树上的叶子结点树等于度为2的结点树加1

（2）非空二叉树上第k层至多有**2^(k-1)**个结点

（3）深度为h的二叉树至多有2^h -1个结点

2.3 几种特殊的二叉树

（1）满二叉树/完美二叉树

一棵高度为h，且含有2^h -1个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点，可以对二叉树按层序编号（根结点编号为1），自上而下，从左到右编号。

编号为i的结点，父结点为「i/2」(向下取整)，左儿子为2i，右儿子为2i+1

（2）完全二叉树

高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。

若i≤「n/2」，则i为分支结点，否则为叶子结点
若有度为1的结点，且该结点只有左孩子无右孩子
若出现某结点(编号为i)，为叶子结点或只有左孩子，则编号大于i的均为叶子结点
若n为奇数，则每个分支结点都有左孩子和有孩子；若n为偶数，则编号最大的分支结点n/2只有左孩子，其余分支结点左右孩子都有

2.4 二叉树的存储结构

2.4.1 顺序存储结构

顺序存储是指用一组地址连续的存储单元依次自上而下、自左到右储存完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在下标为i-1的分量中。

完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号唯一地反映结点之间的逻辑关系，既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

1
2
3

#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

空结点为0，最坏情况高度h和结点数h的单支树，却要占据2^h -1个存储单元

2.4.2 链式存储结构

顺序存储空间利用率低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树的每个结点。

链表头指针指向二叉树的根结点，三叉链表有一个指针域指向父结点

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

n个结点的二叉链表中有n+1个空链域，可以利用空链域存储其他有用信息，从而得到另一种链式存储结构——线索链表

2.5 二叉树的遍历

2.5.1 先/中/后序遍历

（1）先序遍历PreOrder：

根结点—>左子树—>右子树

void PreOrder(BiTree T){
    if(T){
        visit(T);//访问根结点 此函数可以是任何方式访问，最简单就是输出一下
        PreOrder(T->lchild); //递归遍历左子树
        PreOrder(T->rchild); //递归遍历右子树
    }
}//递归栈深恰好为树的深度，时间复杂度都是O(n)

（2）中序遍历InOrder：

左子树—>根结点—>右子树

（3）后序遍历PostOrder

左子树—>右子树—>根结点

2.5.2 先/中/后序非递归遍历

中序非递归遍历：

（1）遇到一个结点，就把他压栈，并遍历它的左子树

（2）当左子树遍历结束后，就把这个结点出栈并访问他

（3）然后按其右指针再去中序遍历该结点的右子树

void InOrderTraversal(BiTree BT){
    BiTree T=BT;
    Stack S=CreatStack(MAXSIZE);//创建并初始化堆栈S
    while(T || !IsEmpty(S)){
        while(T){/* 一直向左并将沿途结点压入堆栈 */
            //printf("%d",T->data) 如果访问操作在这里，就是先序序列
            Push(S,T);
            T=T->lchild;
        }
        if(!IsEmpty(S)){//堆栈不空
            T=Pop(S)
            printf("%d",T->data);//访问操作
            T=T->rchild;//转向右子树
        }
    }
}

后序非递归遍历：

（1）沿着根的左孩子，依次入栈，直到左孩子空，此时栈内元素依次为A B D

（2）读栈顶元素，若其右孩子不空且未被访问过，将右子树执行(1)操作；否则栈顶元素出栈并访问

D右孩子空，D出栈访问。B的右孩子不空且未被访问，E入栈，E左右孩子为空，E出栈访问。B的右孩子不空但访问过，B出栈访问。A右孩子不空且未访问，C入栈，C左右孩子空，C出栈访问。A右孩子不空但访问过，A出栈访问。

void PostOrderTraversal(BiTree BT){
    BiTree T=BT,r=NUll;
    /* 在(2)中，必须分清楚返回时是左子树返回的还是从右子树返回的，因此设定一个辅助指针r，执行最近访问过的结点 */
    Stack S=CreatStack(MAXSIZE);//创建并初始化堆栈S
    while(T || !IsEmpty(S)){
        if(T){//走到最左边
            Push(S,T);
            T=T->lchild
        }else{//已经走到最左边了
            GetTop(S,T);//读栈顶结点指针，并不出栈
            if(T->rchild && T->rchild!=r){//右子树存在且未被访问过
                T=T->rchild;//T就指向它的右儿子，进行下一次while循环，也就是(1)操作
            }else{
                Pop(S,T);//结点出栈
                visit(T->data);
                r=T;//记录最近访问过的结点
                T=NULL; //结点访问过后重置T指针
            }
        }
    }
}

2.5.3 层序遍历

用队列实现，遍历从根结点开始，首先将根结点入队，执行循环{结点出队，访问该结点，左右儿子入队}，直到队列空，这样就是一层一层的访问（不贴代码，太简单了）

2.5.4 由遍历序列构造二叉树

可以由两种序列确定一颗二叉树的构造，但是必须要有中序序列

例如先序 (ABCDEFGHI) 和中序(BCAEDGHFI) 确定

先序序列第一个结点为根结点
在中序序列根结点的左边为左子树，右边为右子树
然后再在先序里面确定左子树和右子树的根结点，递归循环

void solve(int preL,int inL,int postL,int n,int pre[],int in[],int post[]){
    /* preL inL postL 都是三种序列在三个数组里的第一个元素的下标 */
    int root;//根结点元素
    int leftTreeL,rightTreeL;//左子树 右子树长度
    if(n==0){return;}
    if(n==1){post[postL]=pre[preL];return;}//n等于1时，就相当于只有一个叶结点
    //看做根结点直接赋给post当前处理长度的最后一格
    root=pre[preL];//先序序列的第一个就是根结点
    post[postL+n-1]=root;
    for(leftTreeL=0;leftTreeL<n;leftTreeL++){
        if(in[inL+leftTreeL]==root){break;}
        //从中序序列里面取取到左子树的长度
    }
    rightTreeL=n-leftTreeL-1;//取得右子树长度
    solve(preL+1,inL,postL,leftTreeL,pre,in,post);//递归处理左子树
    solve(preL+leftTreeL+1,inL+leftTreeL+1,postL+leftTreeL,rightTreeL,pre,in,post);
    //递归处理右子树
}
主方法里：solve(0,0,0,num,pre,in,post);
/* num是结点数 pre in post都是存放序列的数组 pre in是有数据的，post是空的，在solve里面填写 */

3.线索二叉树

3.1 基本概念

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

3.2 中序线索二叉树的构造

指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p

中序序列：BDAEC

void InThread(ThreadTree &p,ThreadTree &pre){//中序遍历对二叉树线索化的递归算法
    if(p!=NULL){
        InThread(p->lchild,pre); //递归 线索化左子树
        if(p->lchild==NULL){//左子树为空，建立前驱线索
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild=p;//建立前驱结点的后继线索
            pre->rtag=1;
        }
        pre=p;//标记当前结点为刚刚访问的结点
        InThread(p-rchild,pre);//递归，线索化右子树
    }
}
void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){//判断二叉树是否为空
        InThread(T,pre);//线索化二叉树
        pre->rchild=NULL;//下面两行是处理遍历的最后一个结点 
        /* 带头结点的版本是最后一个结点的rchild指向Thrt(头结点) */
        pre->rtag=1;
    }
}

在《数据结构(C语言版)》严蔚敏著中，为了方便，在二叉树的线索链表中添加了一个头结点，令其lchild指向二叉树根结点，rchild指向中序遍历时访问的最后一个结点。反之，根结点的lchild和末结点的rchild指向头结点。

就好比为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。教材中的中序线索化代码如下(相比上面代码框的是带头结点版本的)：

3.3 中序线索二叉树的遍历

在对其遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直到后继为空。在中序线索二叉树中找结点后继的规律是：若其右标志位”1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最做下的结点）为其后继。不含头结点的线索二叉树遍历算法如下

/* 求中序线索二叉树中中序序列下的第一个结点 */
ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag==0)p=p->lchild;//最左下结点，不一定是叶结点
}
/* 求中序线索二叉树中结点p在中序序列下的后继 */
ThreadNode *Nextnode(ThreadNode *p){
    if(p->rtag==0) return Firstnode(p->rchild);
    else return p->rchild; //rtag等于1 指向后继，直接返回后继线索
} 
/* 不含头结点中序线索二叉树遍历 */
void Inorder(ThreadNode *T){
    for( ThreadNode *p=Firstnode(T) ; p!=NULL ; p=Nextnode(p) ){
        visit(p);
    }
}

下面是教材中带头结点的版本，原理基本是一样的，只是加了头结点更方便判断（中序序列最后一个结点rchild指向头结点）

3.4 先序/后序线索二叉树

（1）先序线索二叉树

先序序列：ABCDF

先序线索二叉树中找结点后继的办法：如果有左孩子，则左孩子就是其后继，如果无左孩子但是有右孩子，则右孩子就是其后继；如果为叶节点，则右链域直接指示了结点后继

（2）后序线索二叉树

后序序列：CDBFA

后序线索二叉树中找结点后继的办法：

如果为根结点，则后继为空
如果结点x是父结点的右孩子，或是其双亲的左孩子且没有右子树，则后继为父结点
如果结点x是父结点的左孩子，且双亲有右子树，则后继为双亲右子树上按后序遍历列出的第一个结点。

图中结点B的后继无法通过链域找到，可见在后序线索二叉树上找到后继时需要知道结点双亲，即需采用带标志域的三叉链表作为存储结构。

4.树和森林

4.1 树的存储结构

4.1.1 双亲表示法

一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示双亲结点在链表中的位置

#define MAX_TREE_SIZE 100	
typedef struct PTNode{
    TElemType data;
    int parent;//双亲位置域
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;//根的位置和结点数
}PTree：

这种存储结构利用了每个结点（除根以外）只有唯一双亲的性质。**PARENT(T,x)**操作可以在常量时间内实现。PARENT是返回x的双亲，若是根节点，则函数值为空。反复调用PARENT操作，知道遇见无双亲的结点时，便找到了树的根。

但是这种表示方法中，求结点的孩子时需要遍历整个结构

4.1.2 孩子表示法

树不同于二叉树最多只有两个分支，树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，每个指针指向一棵子树的根节点，此时链表中的结点可以有如下两种结点格式

（1）

这种结点格式，多重链表中的结点是同构的，d为树的度。树中很多结点的度都小于d，所以链表中有很多空链域，在一棵有n个结点度为k的树中必有 n(k-1)+1 个空链域

（2）

（3）把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表(叶结点的孩子链表为空表)。n个头指针又组成一个线性表，为了方便查找，可采用顺序存储结构

4.1.1图中树的孩子表示法如图（a）

typedef struct CTNode{//孩子结点
    int child;
    struct CTNode *next;
}*ChildPtr;
typedef struct{
    TElemType data;
    ChildPtr firstchild; //孩子链表头指针
}CTBox;
typedef struct{//存放头指针的线性表
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;//存放结点数和根的位置
}CTree;

孩子表示法便于那些涉及孩子的操作的实现，不适用于**PARENT(T,x)**操作，可以把双亲表示法和孩子表示法结合起来，即代码中CTBox再加个int parent即可，该表示方法如图(b)

4.1.3 孩子兄弟表示法

又称二叉树表示法/二叉链表表示法，以二叉链表作为树的存储结构。链表结点中的两个链域分别指向该结点的第一个孩子 (firstchild域) 和下一个兄弟 (nextsibling域) 结点

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

从firstchild域找到第一个孩子结点，然后沿着孩子结点的nextsibling域走 i-1 步就能找到第 i 个孩子。同样如果为每个结点增设一个PARENT域，同样能实现PARENT(T,x)操作

4.2 森林与二叉树的转换

二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。给定一棵树 -> 找到唯一的一棵二叉树对应，物理结构上，它们的二叉链表是相同的，只是解释不同

树->二叉树规则：任何一棵树和树对应的二叉树，其右子树必空。

森林->二叉树规则：若把森林的第i+1棵树的根节点看成是第i棵树的根节点的兄弟，则同样可以导出森林与二叉树的关系，这个一一对应的的关系导致森林/树和二叉树可以相互转换

树->二叉树画法：①在兄弟结点之间加一连线；②对每个结点，只保留它与第一个孩子的连线，与其他孩子的连线全部抹掉；③以树根为轴心，顺时针旋转45°

森林->二叉树画法：①将森林中的每棵树转换成响应的二叉树；②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；③以第一棵树的根为轴心顺时针旋转45°

4.3 树和森林的遍历

树的遍历：

先根遍历：ABEFCDG 根节点->子树，子树仍然遵循先根后子树，遍历序列与这棵树对应二叉树的先序序列相同
后根遍历：EFBCGDA 子树->根节点，子树仍然遵循先子树后根，遍历序列与这棵树对应二叉树的中序序列相同

森林的遍历：

先序遍历森林：ABCDEFGHIJ

中序遍历森林：BCDAFEHJIG

当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即对应的二叉树的先序和中序遍历。

5.树与等价问题

教材P139，这里不做整理

6.哈夫曼树及应用

6.1 基本概念

（1）带权路径长度(WPL)：树中结点尝尝被赋予一个表示某种意义的值，称为该结点的权。从树根到任意结点的路径长度(经过的边数)与该结点上权值的乘积，称为该结点的带权路径长度，树中所有叶结点的带权路径长度之和称为树的带权路径长度。

（2）最优二叉树/哈夫曼树：一棵有n个叶子结点的二叉树，每个叶子结点带权为Wi，其中带权路径长度WPL最小的二叉树。

(a) WPL=7x2+5x2+2x2+4x2=36

(b) WPL=7x3+5x3+2x1+4x2=46

6.2 哈夫曼树的构造

哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法，叙述如下：

（1）给定n个权值分别为{w1,w2,…,wn}构成n棵只有一个带权为wi的根结点(左右子树为空)的二叉树的集合，即森林F

（2）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值的和

（3）在F中删除这两棵树，同时将新得到的二叉树加入F中

（4）重复**(2)和(3)**，直到F只含一棵树为止，这棵树便是哈夫曼树

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int Weight;
    HuffmanTree Left,Right;
}
HuffmanTree Huffman(MinHeap H){
    /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
    int i;HuffmanTree T;
    BuildMinHeap(H);/* 将H->Elements[]按权值调整为最小堆 */
    for(i=1;i< H->Size;i++){//做(H->size)-1次合并
        T=malloc(sizeof(struct TreeNode));//建立新结点
        T->Left = DeleteMin(H);//从最小堆拿出最小结点 作为T的左子结点
        T->Right = DeleteMin(H);//再次拿出最小结点 作为T的右子结点
        T->Weight=(T->Left->Weight)+(T->Right->Weight);//计算新的权值
        Insert(H,T);//将合并的新T插入最小堆
    }
    T = DeleteMin(H);
    return T;
}

哈夫曼树特点：

没有度为1的结点
n个叶子结点的哈夫曼共有2n-1个结点
哈夫曼树的任意非叶结点的左右子树交换后仍然是哈夫曼树
同一组权值，可以存在不同构的哈夫曼树

6.3 哈夫曼编码

（1）固定/可变长度编码：在数据通信中，若对每个字符用相等长度的二进制位表示，这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码

可变长度编码比固定长度编码要好得多，特点是频率高的字符赋以短编码，而对频率高的字符则赋以较长一些的编码，从而降低字符的平均编码长度，起到压缩数据的效果。

（2）假设传递的电文为’A B A C C D A’，只有四种字符，假设编码分别为A00、B01、C10、D11，上述7个字符的电文便为 00010010101100 ，总长14位，可以按两位一分来进行译码

传送电文时，希望总长尽可能短，假设编码分别为A0、B00、C1、D01，则新的电文为 000011010，但是这样电文就无法翻译，0000就可有多种译法，或是AAAA，ABA，BB。

因此，若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符编码的前缀，这种编码称作前缀编码。

6.3.1 二叉树设计二进制前缀编码

如图实例，约定左分支代表字符0，右分支代表1，则可以从根结点到叶子结点的路径上分支字符组成的字符串为该叶子结点字符的编码，如此得到的必为二进制前缀编码，A0，B10，C110，D111

假设每种字符在电文中出现二代次数为Wi，其编码长度为Li，电文中只有n种字符，则电文总长为，对应到二叉树上，若设置Wi为叶子结点的权，Li恰为从根到叶子的路径长度。则恰好为二叉树上带权路径长度。

由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便成为哈夫曼编码

6.3.2 具体实现

哈夫曼树中没有度为1的结点，这类树称为严格的二叉树/正则二叉树，有n个叶子结点的哈夫曼树共有2n-1个结点，存储在大小为2n-1的一维数组中。

求编码->从叶子结点出发走一条叶子到根的路径；求译码->从根出发走一条从根到叶子的路径；对每个结点而言，要知道双亲信息，也要知道孩子结点的信息

typedef struct{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
    //w存放n个字符的权值(均>0),构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
    if(n<=1) return;//只有一个结点
    int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //多申请一个 0号单元不用
    for(p=HT,i=1 ; i<=n ; ++i,++p,++w) *p={*w,0,0,0};//将n个字符的权值赋到n个HTNode的weight
    for(;i<=m; ++i,++p) *p={0,0,0,0};//将剩余的HTNode初始化
    for(i=n+1;i<=m;++i){//建哈夫曼树
        /* 在HT[1..i-1] (1..i-1里有i个)选择parent为0且weight最小的两个结点，其序号分别为s1 s2 */
        /* 第一次先从1..n里面选，他们的parent都是0，被选中后的两个parent就为i了，下次就从剩下的和i里面选， 
        i的parent也是0*/
        Select(HT,i-1,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;
    }
    /* 从叶子到根逆向求每个字符的哈夫曼编码 */
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量，所以是sizeof(*char),带*
    cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
    cd[n-1]="\0";//编码结束符，字符串的结尾
    for(i=1;i<=n;++i){//逐个字符求哈夫曼编码 一共n个字符，求n次
        start=n-1;//编码结束符的位置
        for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent){//从叶子到根逆向求编码
            if(HT[f].lchild==c) cd[--start]='0';//如果该结点是父节点的左儿子，就编码为0
            else cd[--start]='1';
        }
        /* 为第i个字符编码，HC[i]是头指针向量，n-start为从叶子到根逆向求编码的for循环次数，也就是编码长度 */
        HC[i]=(char*)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);//从cd复制编码到HC
    }
    free(cd);//释放工作空间
}

上述算法求哈夫曼编码是从叶子到根逆向处理的，也可以根出发，遍历整颗哈夫曼树，求得各叶子结点所代表的的字符的哈夫曼编码

译码过程比较简单，看教材P148

补：回溯法与树的遍历/树的计数

回溯法与树的遍历P149 树的计数P152

7.并查集

7.1 基本概念

并查集是一种简单的集合表示，支持以下三种操作

（1）Initial(S)：将集合S中的每个元素都初始化为只有一个单元素的子集合

（2）Union(S,Root1,Root2)：把集合S中的子集合Root2并入子集合Root1，要求Root1和Root2互不相交，否则不执行合并

（3）Find(S,x)：查找集合S中单元素x所在的子集合，并返回该子集合的根结点

通常用树(森林)的双亲作为并查集的存储结构，每个子集以一棵树表示。所有表示子集合的数，构成表示全集合的森林，存放在双亲表示的数组内。通常用数组元素下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

eg.一个全集合S={0,1,2,3,4,5,6,7,8,9}，初始化时每个元素自成一个单元素子集合，每个子集合的数组值为-1

经过一段时间的计算，这些子集合合并为三个更大的子集合S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}

得到两个子集合的并：将其中一个子集合的根节点的双亲指针指向另一个集合的根节点，如图，将index为1的元素改为0，然后0的元素为-4+-3=-7

7.2 代码实现

采用树的双亲指针数组表示作为并查集的存储表示，集合元素编号从0到size-1，其中size是最大元素的个数

/* 并查集的结构定义如下 */
#define SIZE 100
int UFSets[SIZE];
/* 并查集的初始化操作 S即为并查集*/
void Initial(int S[]){
    for(int i=0;i<size;i++) S[i]=-1;// -1 自成单元素集合
}
/* Find操作 函数在并查集S中查找并返回包含元素x的树根 */
int Find(int S[],int x){
    while(S[x]>=0){//S[x]为负数时退出while 即找到根
        x=S[x];//往上找根
    }
    return x;
    //判断两个是否属于同一集合，分别找到根节点，比较即可
}
/*  Unionc操作 */
void Union(int S[],int Root1,int Root2){
    S[Root2]=Root1;
}

mooc版本的结构表示：

typedef struct{
    ElementType Data;
    int Parent;
}SetType;

本文链接： http://edcc1015.github.io/2022/07/04/408数据结构笔记——树/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！