【数据结构应用题】树的应用

2023-12-24 16:30
文章标签 应用 数据结构 应用题

本文主要是介绍【数据结构应用题】树的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树的应用

  • 树
    • 树的性质
      • 总结树的度、树高、结点数等属性之间的联系
    • 树（森林）的定义和画图
      • 写代码：使用“双亲表示法”定义顺序存储的树（以及森林）
      • 写代码：使用“孩子表示法”定义链式存储的树（以及森林）
      • 写代码：使用“孩子兄弟表示法”定义链式存储的树（以及森林）
        • 写代码：求以孩子兄弟表示法存储的森林的叶结点数
        • 写代码：以孩子兄弟表示法为存储结构设计递归算法求数的深度
      • 对比“树的孩子表示法存储”vs“图的邻接矩阵存储”vs“散列表的拉链法”vs“基数排序”
      • 自己动手创造，画一个结点总数不少于10的树，并画出对应“双亲表示法”、“孩子表示法”、“孩子兄弟表示法”三种数据结构示意图（至少包含三棵树的森林）
  • 二叉树
    • 二叉树的性质
      • 总结二叉树的度、树高、结点数等属性之间的联系
    • 二叉树的顺序存储和基本操作实现
      • 写代码：定义顺序存储的二叉树（数组实现，树的结点从数组下标0开始存储）
      • 写代码：定义顺序存储的二叉树（数组实现，树的结点从数组下标1开始存储）
      • 写代码：运用非递归算法实现先/中/后序遍历
  • 哈夫曼树的应用
    • 哈夫曼树的性质
      • 总结哈夫曼树的度、树高、结点数等属性之间的联系
        • 基础哈夫曼树的性质
        • m叉哈夫曼树的性质
    • 自己动手创造，写10个字符，并给每个字符设置权值，画出构造哈夫曼树的过程
      • 用文字描述构造该哈夫曼树的过程
      • 基于你所构造的哈夫曼树，写出10个字符的哈夫曼编码
    • 用文字描述一棵哈夫曼树“译码的过程”（即如何将二进制哈夫曼编码翻译为字符）
  • 并查集的应用
    • 写代码：定义一个并查集（用长度为n的数组实现）
      • 基于上述定义，实现并查集的基本操作——并Union
      • 基于上述定义，实现并查集的基本操作——查Find
    • 自己设计一个例子，并查集初始有10个元素，进行若干次Union操作，画出每一次Union后的样子
      • 基于上一步得到的并查集，进行若干次Find操作（每次Find会进行“路径压缩”）画出每次Find（路径压缩）后的样子
  • 二叉排序树、平衡二叉树的应用题潜在考法
    • 自己设计一个例子，给出不少于10个关键字序列，按顺序插入一棵初始为空的二叉排序树，画出每一次插入后的样子
      • 基于你设计的例子，计算二叉排序树在查找成功和查找失败时的ASL
      • 基于你设计的例子，依次删除4个元素，画出每一次删除之后的样子（需要包含四种删除情况——删一个叶子节点、删一个只有左子树的结点、删一个只有右子树的结点、删一个既有左子树又有右子树的结点）
    • 自己设计一个例子，给出不少于10个关键字序列，按顺序插入一棵初始为空的平衡二叉树，画出每一次插入后的样子
      • 基于你设计的例子，计算平衡二叉树在查找成功和查找失败时的ASL

树

树的性质

总结树的度、树高、结点数等属性之间的联系

1.树的结点总数等于所有结点的度数之和加1。
2.T的第 i i i（ i ≥ 1 i\ge1 i≥1）层最多有 k i − 1 k^{i-1} ki−1个结点。
3.高度为h的T中最多有( k h − 1 ) k^{h}-1) kh−1)/( k − 1 k-1 k−1)个结点( k k k为树的度)。
4.T的最小高度为： h h h= ⌈ l o g k ( n ( k − 1 ) + 1 ) ⌉ \left \lceil log_{k}(n(k-1)+1)\right \rceil ⌈logk​(n(k−1)+1)⌉=
⌊ l o g k n ( k − 1 ) ⌋ + 1 \left \lfloor log_{k}n(k-1)\right \rfloor+1 ⌊logk​n(k−1)⌋+1
5.T的最大高度为 n − k + 1 n-k+1 n−k+1( k k k为树的度)。

树（森林）的定义和画图

写代码：使用“双亲表示法”定义顺序存储的树（以及森林）

#define Max_Tree_Size 150   //树的最多结点数
typedef int Elemtype;		//树结点的数据类型
typedef struct PTNode		//树的结点定义（结点结构）
{Elemtype data;			//结点数据元素int parent;				//双亲位置
}PTNode;
typedef struct PTree				//树的类型表示（树结构）
{PTNode nodes[Max_Tree_Size];		//结点数组int r,n;							//根的位置和结点数
}PTree;

写代码：使用“孩子表示法”定义链式存储的树（以及森林）

#define Max_Tree_Size 150   //树的最多结点数
typedef int Elemtype;		//树结点的数据类型
typedef struct CTNode		//孩子结点定义
{int Child;struct CTNode* next;		
}*Childptr;
typedef struct CTBox				//表头结构
{Elemtype data;Childptr firstchild;			//孩子链表的表头指针
}CTBox;
typedef struct CTree				//树的类型表示
{CTBox nodes[Max_Tree_Size];		//结点数组int n,r;							//结点数和根的位置
}CTree;

写代码：使用“孩子兄弟表示法”定义链式存储的树（以及森林）

typedef int Elemtype;		//树结点的数据类型
typedef struct CSNode		//孩子结点定义
{Elemtype data;							//数据域struct CSNode* firstchild,*rightsibling;	//指针域（存储第一个孩子结点的地址和该结点右兄弟的地址）	
}CSNode,*CSTree;
写代码：求以孩子兄弟表示法存储的森林的叶结点数
type struct CSNode	//孩子结点定义
{Elemtype data;								//数据域struct CSNode *firstchild,*rightsibling;	//指针域
}CSNode,*CSTree;
int Leaves(CSTree t)				//计算以孩子兄弟表示法存储的森林的叶子结点数
{if(t == NULL)return 0;					//树空返回0if(t->firstchild == NULL)		//若结点无左孩子，则该结点必是叶子结点return 1+Leaves(t->rightsibling);	//返回叶子结点和其右兄弟子树中的叶子结点树elsereturn Leaves(t->firstchild) + Leaves(t->rightsibling);		//孩子子树和兄弟子树中叶子子树之和
}
写代码：以孩子兄弟表示法为存储结构设计递归算法求数的深度
int Height(CSTree bt)				//递归求以孩子兄弟表示法的树的深度
{int hc,hs;if(bt == NULL)return 0;else						//高度取子女高度+1与兄弟子树高度更大者{hc = Height(bt->firstchild);		//第一子女树高hs = Height(bt->rightsibling);		//兄弟树高if(hc + 1 >hs)return hc+1;elsereturn hs;}
}

对比“树的孩子表示法存储”vs“图的邻接矩阵存储”vs“散列表的拉链法”vs“基数排序”

自己动手创造，画一个结点总数不少于10的树，并画出对应“双亲表示法”、“孩子表示法”、“孩子兄弟表示法”三种数据结构示意图（至少包含三棵树的森林）

树：
在这里插入图片描述
双亲表示法：
在这里插入图片描述
孩子表示法：
在这里插入图片描述
孩子兄弟表示法：
将树表示成二叉树：
在这里插入图片描述
孩子兄弟表示法示意图：
在这里插入图片描述

二叉树

二叉树的性质

总结二叉树的度、树高、结点数等属性之间的联系

1.二叉树的第k(k>=1)层最多有 2 k − 1 2^{k-1} 2k−1个结点。
2.高度为h的二叉树中最多有 2 h − 1 2^{h}-1 2h−1个结点。
3.对任意一棵二叉树T，其叶子结点数等于度为二的结点数加1，即 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0​=n2​+1。
4.具有 n ( n ≥ 1 ) n(n\ge1) n(n≥1)个结点的完全二叉树的高度 h h h满足 h h h= ⌈ l o g 2 ( n + 1 ) ⌉ \left\lceil log_{2}(n+1)\right\rceil ⌈log2​(n+1)⌉= ⌊ l o g 2 n ⌋ + 1 \left \lfloor log_{2}n \right \rfloor +1 ⌊log2​n⌋+1。
5.完全二叉树中度为1的结点的数目只能是0或1。
6.完全二叉树中叶子结点只可能在最下面两层出现。
7.二叉树的最大高度为 n n n。

二叉树的顺序存储和基本操作实现

写代码：定义顺序存储的二叉树（数组实现，树的结点从数组下标0开始存储）

#define Max_Tree_Size 150					//二叉树的最大结点数
typedef int TElemtype;
typedef int Statues;
typedef TElemtype SqBiTree[Max_Tree_Size];	//0号单元存储根结点
void InitSqBiTree(SqBiTree& T) {			//创建一个空的二叉树for (int i = 0; i < Max_Tree_Size; i++) {T[i] = 0;}
}
Statues SetNodes(SqBiTree& T,int i ,TElemtype e) {	//给结点i赋值if (T == NULL)return 0;if (i >= Max_Tree_Size)return 0;T[i] = e;return 1;
}
Statues SetLeftchild(SqBiTree& T, int i, TElemtype e) {		//给结点i的左孩子赋值if (T == NULL)return 0;if (i * 2 >= Max_Tree_Size)return 0;T[i * 2] = e;return 1;
}
Statues SerRightchild(SqBiTree& T, int i, TElemtype e) {	//给结点i的右孩子赋值if (T == NULL)return 0;if (i * 2 + 1 >= Max_Tree_Size)return 0;T[i * 2 + 1] = e;return 1;
}

写代码：定义顺序存储的二叉树（数组实现，树的结点从数组下标1开始存储）

#define Max_Size_Tree 150
typedef int TElemtype;
typedef struct SqBiTree{TElemtype *elem;	//元素存储空间基址，建表时按实际长度分配，0号单元留空int LSqBiTree;		//表示树的数组最大长度
}SqBiTree;

写代码：运用非递归算法实现先/中/后序遍历

先序遍历：

void PreOrder(BiTNode *T){if(T == NULL) return;			//特殊情况处理Stack STK = initStack();		//等价于递归栈push(STK,T);while(!stackEmpty(STK)){T = pop(STK);visit(T);					//访问当前结点<==>本层递归处理if(T->rchild != NULL)	push(STK,T->rchild);	//右孩子先入栈<==>后递归处理右子树if(T->lchild != NULL)push(STK,T->lchild);	//左孩子后入栈<==>先递归处理左子树}
}

中序遍历：

void GoAlonglchild(BiTNode *T,Stack &STK){while(T != NULL){STK.push(T);T = T->lchild;
}
void InOrder(BiTNode *T){Stack STK = initStack();GoAlonglchild(T,STK);while(!stackEmpty(STK)){T = pop(STK);visit(T);GoAlonglchild(T->rchild);
}

后序遍历：

void PostOrder(){if(T ==NULL) return;Stack STK = initStack();		//主栈：实现N-R-L递归遍历push(STK,T);Stack auxSTK = initStack();		//辅助栈用来保存调整顺序后的结点while(!stackEmpty(STK)){T = pop(STK);// 将N-R-L变成L-R-Npush(auxSTK,T);				//等价于逆置递归顺序if(T->lchild !=NULL)push(STK,T->lchild);	//左孩子先入栈<==>后递归处理左子树if(T->rchild !=NULL)push(STK,T->rchild);	//右孩子后入栈<==>先递归处理右子树}while (!stackEmpty(auxSTK)){T = pop(auxSTK);visit(T);					//依次出辅助栈并访问}
}

哈夫曼树的应用

哈夫曼树的性质

总结哈夫曼树的度、树高、结点数等属性之间的联系

基础哈夫曼树的性质

1.若哈夫曼树中有 n 0 n_{0} n0​个叶子结点，则总共有 2 n 0 − 1 2n_{0}-1 2n0​−1个结点，且度为2（构造过程中新建立）的结点数为 n 0 − 1 n_{0}-1 n0​−1。
2.哈夫曼树是一棵二叉树，结点的度只有0或2，没有度为1的结点。
3.上一层所有结点的权值均大于下一层。

m叉哈夫曼树的性质

1.若 m m m叉哈夫曼树中有 n 0 n_{0} n0​个叶子结点，则总共有 ( m n 0 − 1 ) / ( m − 1 ) (mn_{0}-1)/(m-1) (mn0​−1)/(m−1)个结点，且度为 m m m（构造过程中新建立）的结点数为 ( n 0 − 1 ) / ( m − 1 ) (n_{0}-1)/(m-1) (n0​−1)/(m−1)。
2. m m m叉哈夫曼树结点的度只有 0 0 0或 m m m。

自己动手创造，写10个字符，并给每个字符设置权值，画出构造哈夫曼树的过程

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

用文字描述构造该哈夫曼树的过程

1.首先，根据给定的字符集合和对应的权重，创建一个包含所有字符的叶子结点集合。
2.从叶子结点集合中选择权重最小的两个结点作为左右子节点，创建一个新的父结点，并将父结点的权重设置为左右子节点的权重之和。
3.将新创建的父结点加入到结点集合中，并从结点集合中移除原来的两个子节点
4.重复步骤2、3直到集合中只剩下一个结点，即根结点。该根结点就是哈夫曼树的根结点。
选择结点4、5作为左右结点得到父结点9加入结点集合中，删除结点4、5。
选择结点6、8作为左右结点得到父结点14加入结点集合中，删除结点6、8。
选择结点9、9作为左右结点得到父结点18加入结点集合中，删除结点9、9。
选择结点10、14作为左右结点得到父结点24加入结点集合中，删除结点10、14。
选择结点18、18作为左右结点得到父结点36加入结点集合中，删除结点18、18。
选择结点24、29作为左右结点得到父结点53加入结点集合中，删除结点24、29。
选择结点36、36作为左右结点得到父结点72加入结点集合中，删除结点36、36。
选择结点45、53作为左右结点得到父结点98加入结点集合中，删除结点45、53。
选择结点72、98作为左右结点得到父结点170加入结点集合中，删除结点72、98。
结点集合只剩下结点170，该结点为此哈夫曼树的根结点。

基于你所构造的哈夫曼树，写出10个字符的哈夫曼编码

A:00000;
B:00001;
C:11010;
D:11011;
E:0001;
F:1100;
G:001;
H:111;
I:01;
J:10;
带权路径长度WPL=（权重X编码位数）求和

用文字描述一棵哈夫曼树“译码的过程”（即如何将二进制哈夫曼编码翻译为字符）

1.首先，根据哈夫曼树的构造过程，得到每个字符对应的编码。编码是由0、1组成的二进制序列，根据字符在哈夫曼树的路径确定。
2.从根结点开始，根据输入的编码位逐步向下遍历哈夫曼树。如果当前位是0，则向左子结点移动；如果当前位是1，则向右子结点移动。
3.当遍历到叶子结点时，即找到了一个字符的编码。将该字符输出，并重新回到根结点，继续下一个编码的遍历。
4.重复步骤2、3直至所有输入的编码全部遍历完毕。
通过以上步骤可将输入的编码序列译码为原始的字符序列。由于哈夫曼树的构造过程保证了每个字符的编码是唯一的，因此译码过程是可靠的。

并查集的应用

写代码：定义一个并查集（用长度为n的数组实现）

typedef int Elemtype;
typedef struct UnionFindSet {int n;				//总的元素（结点）个数Elemtype* parents;	//存储元素parent的数组的首元素指针
}UnionFindSet;
UnionFindSet Initialize(int n) {	//并查集的初始化UnionFindSet ufs;ufs.n = n;for (int i = 0; i < n; i++) {ufs.parents[i] = -1;	//初始时，所有结点的parent设置为-1，表示树内只有一个结点}return ufs;
}

基于上述定义，实现并查集的基本操作——并Union

int Union(UnionFindSet& ufs, Elemtype e, Elemtype t) {int eRoot = Find(ufs, e);int tRoot = Find(ufs, t);if (eRoot == -1 || tRoot == -1)		//判断是否查找成功return -1;if (eRoot != tRoot)ufs.parents[tRoot] = eRoot;		//将y树合并到x树return eRoot;
}

基于上述定义，实现并查集的基本操作——查Find

int Find(UnionFindSet& ufs, Elemtype e) {if (e >= ufs.n || e < 0)	//该元素在集合中不存在return -1;while (ufs.parents[e] >= 0)	//parent值>0，表示有父节点e = ufs.parents[e];return e;
}

自己设计一个例子，并查集初始有10个元素，进行若干次Union操作，画出每一次Union后的样子

在这里插入图片描述

基于上一步得到的并查集，进行若干次Find操作（每次Find会进行“路径压缩”）画出每次Find（路径压缩）后的样子

在这里插入图片描述

二叉排序树、平衡二叉树的应用题潜在考法

自己设计一个例子，给出不少于10个关键字序列，按顺序插入一棵初始为空的二叉排序树，画出每一次插入后的样子

关键字序列{25,20,99,16,11,1,22,26,42,17}
在这里插入图片描述
对该二叉排序树进行中序遍历得到有序关键字序列{1,11,16,17,20,22,25,26,42,99}

基于你设计的例子，计算二叉排序树在查找成功和查找失败时的ASL

在这里插入图片描述

ASLsuc=(1X1+2X2+3X3+4X3+5X1)/10=3.1;(10为○的个数；1、2、3、3、1为○在该层的个数；1、2、3、4、5为○的层数)
ASLunsuc=(2X1+3X3+4X5+5X2)/11=3.73;(11为□的个数；1、3、5、2为□在该层的个数；2、3、4、5为□的父结点所在的层数)

基于你设计的例子，依次删除4个元素，画出每一次删除之后的样子（需要包含四种删除情况——删一个叶子节点、删一个只有左子树的结点、删一个只有右子树的结点、删一个既有左子树又有右子树的结点）

在这里插入图片描述

自己设计一个例子，给出不少于10个关键字序列，按顺序插入一棵初始为空的平衡二叉树，画出每一次插入后的样子

关键字序列{25,20,99,16,11,1,22,26,42,17}
在这里插入图片描述
对该平衡二叉树进行中序遍历得到有序关键字序列{1,11,16,17,20,22,25,26,42,99}

基于你设计的例子，计算平衡二叉树在查找成功和查找失败时的ASL

在这里插入图片描述
ASLsuc=(1X1+2X2+3X3+4X4)/10=3;(10为○的个数；1、2、3、4为○在该层的个数；1、2、3、4为○的层数)
ASLunsuc=(2X1+3X2+4X8)/11=3.73;(11为□的个数；1、2、8为□在该层的个数；2、3、4为□的父结点所在的层数)

这篇关于【数据结构应用题】树的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/532397。

相关文章

中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
zoj3820(树的直径的应用)

zoj3820(树的直径的应用)

题意：在一颗树上找两个点，使得所有点到选择与其更近的一个点的距离的最大值最小。 思路：如果是选择一个点的话，那么点就是直径的中点。现在考虑两个点的情况，先求树的直径，再把直径最中间的边去掉，再求剩下的两个子树中直径的中点。 代码如下： #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#
阅读更多...
【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善，其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性， 将与教育相关的数据要素在区块链上进行存证确权，在确保数据可信的前提下，促进教育的公平、透明、开放，为教育教学质量提升赋能，实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护，支撑教育资源共享、教学质量评估、
阅读更多...
AI行业应用(不定期更新)

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件，然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它，快速获取到想要知道的信息。https://www.chatpdf.com/
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

随着区块链技术的快速发展，越来越多的企业开始将其应用于实际业务中。然而，区块链技术的专业性使得其集成开发成为一项挑战。针对此，广东中创智慧科技有限公司基于国产开源联盟链 FISCO BCOS 推出了区块链集成开发平台。该平台基于区块链技术，提供一套全面的区块链开发工具和开发环境，支持开发者快速开发和部署区块链应用。此外，该平台还可以提供一套全面的区块链开发教程和文档，帮助开发者快速上手区块链开发。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2