[数据结构] 树、森林及二叉树的应用

合集 - 数据结构与算法(11)

1.算法3：质数的个数2023-05-012.算法2：Hanoi塔2022-11-223.算法1：Fibonacci数列2022-11-214.[数据结构]排序算法的性能比较01-215.[数据结构] 链表02-036.[数据结构] 栈02-067.[数据结构] 数组与特殊矩阵02-068.[数据结构] 队列02-079.[数据结构] 串与KMP算法详解02-1210.[数据结构] 树与二叉树03-04

11.[数据结构] 树、森林及二叉树的应用03-05

收起

树、森林

树的存储结构

双亲表示法

双亲表示法的存储结构

#define MAX_TREE_SIZE 100
typedef struct {
    int data;
    int parent;
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;
}PTree;

【注】 区别树的顺序存储结构与二叉树的顺序存储结构。在树的顺序存储结构中，数组下标代表节点的编号，下标中所存的内容指示了节点之间的关系。而在二叉树的顺序存储结构中， 数组下标既表达了节点的编号，又指示了二叉树中节点之间的关系。当然，二叉树属于树，因此二叉树也可以用树的存储结构来存储，但树却不能都用都用二叉树的存储结构来存储。

孩子表示法

孩子表示法是将每个节点的孩子节点视为一个线性表，且以单链表作为存储结构，则$n$个节点就有$n$个孩子链表（叶节点的孩子链表为空表）。而$n$个头指针又组成一个线性表。

与双亲表示法相反，孩子表示法寻找孩子的操作非常方便，而寻找双亲的操作则需要遍历$n$个节点中孩子链表指针域所指向的$n$个孩子链表。

孩子兄弟表示法

又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个节点包括三个部分的内容：节点值、指向节点第一个孩子节点的指针、指向节点下一个兄弟节点的指针

结构体如下：

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

树、森林、二叉树的转换

树转换为二叉树

（1）在兄弟节点之间画一条线；

（2）对每个节点，只保留它与第一个孩子的连线，而与其他孩子的连线全部删除；

（3）以树根为轴心，顺时针旋转45°。

以下代码引用我大佬同学：作者：Amαdeus，出处：https://www.cnblogs.com/MAKISE004/p/17089756.html
 
//树 转化为 二叉树
BinaryTree CSTree_Transform_to_BinaryTree(CSTree ct){
 if(!ct) return NULL;
 
 BinaryTree T = (BinaryTree)malloc(sizeof(BiNode));
 T->data = ct->data;
 //相当于将left变为firstchild, 将right变为nextsibling 本质的形态没有改变
 T->leftchild = CSTree_Transform_to_BinaryTree(ct->firstchild);
 T->rightchild = CSTree_Transform_to_BinaryTree(ct->nextsibling);
 
 return T;
}

森林转换为二叉树

（1）将森林中的每棵树转换成相应的二叉树；

（2）每棵树的根视为兄弟关系，加上连线；

（3）以第一棵树的根为轴心顺时针旋转45°。

以下代码引用我大佬同学：作者：Amαdeus，出处：https://www.cnblogs.com/MAKISE004/p/17089756.html
 
//森林 转化为 二叉树
BinaryTree Forest_Transform_to_BinaryTree(CSTree ct[], int low, int high){
 if(low > high)  return NULL;
 
 //每个树变成二叉树
 BinaryTree T = CSTree_Transform_to_BinaryTree(ct[low]);  
 //通过rightchild连接每一个二叉树的根节点
 T->rightchild = Forest_Transform_to_BinaryTree(ct, low + 1, high);
 
 return T;
}

树、森林的遍历

树的遍历

• 先根遍历。若树非空，则按如下规则遍历：

  • 先访问根节点
  • 再依次遍历根节点的每棵子树，遍历子树时仍遵循先根后子树的规则

• 后根遍历。若树非空，则按如下规则遍历：

  • 先依次遍历根节点的每棵子树，遍历子树时仍遵循先子树后根的规则
  • 再访问根节点

树的先根遍历与对应二叉树的先序序列相同，树的后根遍历与对应二叉树的中序序列相同。

森林的遍历

• 先序遍历森林。若森林非空，则按如下规则遍历：

  • 访问森林中第一棵树的根节点
  • 先序遍历第一棵树中根节点的子树森林
  • 先序遍历除去第一棵树之后剩余的树构成的森林

• 中序遍历森林。若森林非空，则按如下规则遍历：

  • 中序遍历森林中第一棵树的根节点的子树森林
  • 访问第一棵树的根节点
  • 中序遍历粗去第一棵树之后剩余的树构成的森林

树与二叉树的应用

哈夫曼树和哈夫曼编码

几个概念

• 路径：树中一个节点到另一个节点之间的分支构成

• 路径长度：路径上的分支数目

• 权：树中节点被赋予的一个表示某种意义的数值

• 带权路径长度：从树的根到一个节点的路径长度与该节点上权值的乘积

  $$WPL=\sum _{i=1}^n{w}_i{l}_i$$

  其中，$w_i$是第$i$个叶节点所带的权值，$l_i$是该叶节点到根节点的路径长度

在含有$n$个带权叶节的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树。

下面看个算法：递归求WPL

int getWPL(struct TreeNode *root, int depth) {
    if (root == NULL) { // 如果节点为空，返回0
        return 0;
    }
    if (root->left == NULL && root->right == NULL) { // 如果节点是叶子节点，返回带权路径长度
        return depth * root->val;
    }
    // 如果节点不是叶子节点，递归计算左子树和右子树的WPL，并相加返回
    return getWPL(root->left, depth + 1) + getWPL(root->right, depth + 1);
}

接下来咱们举个栗子，来看一下哈夫曼编码

看题：来自北邮考研机试

3531. 哈夫曼树 - AcWing题库

题解：

// 优先队列求哈夫曼树最短带权路径长度
#include
using namespace std;
 
int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        q.push(x);
    }
    int ans = 0;
    while(q.size() > 1) {
        int t1 = q.top();
        q.pop();
        int t2 = q.top();
        q.pop();
        q.push(t1 + t2);
        ans += t1 + t2;
    }
    cout << ans << endl;
    return 0;
}

并查集

这里不想做太多解释，我们看一下y总的模版（写的时候已经快要零点了，第二天还要早起）（PS：第二天果然多睡了半个小时）

(1)朴素并查集：
 
    int p[N]; //存储每个点的祖宗节点
 
    // 返回x的祖宗节点
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
 
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;
 
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
 
 
(2)维护size的并查集：
 
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
 
    // 返回x的祖宗节点
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
 
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) {
        p[i] = i;
        size[i] = 1;
    }
 
    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
 
 
(3)维护到祖宗节点距离的并查集：
 
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
 
    // 返回x的祖宗节点
    int find(int x) {
        if (p[x] != x) {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
 
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) {
        p[i] = i;
        d[i] = 0;
    }
 
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
 
作者：yxc
链接：https://www.acwing.com/blog/content/404/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

836. 合并集合 - AcWing题库

#include
using namespace std;
 
const int N = 100010;
int p[N];//定义多个集合
 
int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    /*
    经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
    p[x]=x;
    */
    return p[x];
    //找到了便返回祖宗节点的值
}C
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) p[i]=i;
    while(m --) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(*op == 'M') p[find(a)] = find(b);//集合合并操作
        else
        	if(find(a)==find(b))
        	//如果祖宗节点一样,就输出yes
        		printf("Yes\n");
       	 	else
        		printf("No\n");
    }
    return 0;
}