C#数据结构与算法揭秘九

简介:

这节,我们说一说二叉树常见的应用的场景。呵呵。。。。。。。。。。。。。。

定义一个哈夫曼树,首先,要高清楚什么是哈夫曼树。所谓哈夫曼树是又叫最优二叉树,指的是对于一组具有确定权值的叶子结点的具有最小带权路径长度的二叉树。

介绍哈夫曼树的一些基本概念。

(1)路径(Path):从树中的一个结点到另一个结点之间的分支构成这两个结点间的路径。
(2)路径长度(Path Length):路径上的分支数。
(3)树的路径长度(Path Length of Tree):从树的根结点到每个结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。
(4)结点的权(Weight of Node):在一些应用中,赋予树中结点的一个有实际意义的数。
(5)结点的带权路径长度(Weight Path Length of Node):从该结点到树的根结点的路径长度与该结点的权的乘积。

(6)树的带权路径长度(WPL) :树中所有叶子结点的带权路径长度之和,记为   ∑==n1kkkWPLLW

具体情况,如图a所示:

在下图所示的的四棵二叉树, 都有 4个叶子结点, 其权值分别为 1、 2、 3、4,它们的带权路径长度分别为:

wl=(1+2+3+4)*2=20  如图所示:

wl=(3+4)*3+2*2+1=26 如图所示:

WPL=1×3+2×3+3×2+4×1=19  如图所示:

WPL=2×1+1×2+3×3+4×3=25  如图所示:

那么, 如何构造一棵哈夫曼树呢?哈夫曼最早给出了一个带有一般规律的算法,俗称哈夫曼算法。现叙述如下:
(1)根据给定的n个权值{w1,w2,…,wn},构造n棵只有根结点的二叉树集合F={T1,T2,…,Tn};
(2)从集合 F 中选取两棵根结点的权最小的二叉树作为左右子树,构造一棵新的二叉树, 且置新的二叉树的根结点的权值为其左、 右子树根结点权值之和。
(3)在集合 F 中删除这两棵树,并把新得到的二叉树加入到集合 F 中;
(4)重复上述步骤,直到集合中只有一棵二叉树为止,这棵二叉树就是哈夫曼树。他的步骤如下图所示:

 

由哈夫曼树的构造算法可知, 用一个数组存放原来的 n个叶子结点和构造过程中临时生成的结点,数组的大小为 2n-1。所以,哈夫曼树类 HuffmanTree中有两个成员字段: data数组用于存放结点, leafNum表示哈夫曼树叶子结点的数目。结点有四个域,一个域 weight,用于存放该结点的权值;一个域 lChild,用于存放该结点的左孩子结点在数组中的序号;一个域 rChild,用于存放该结点的右孩子结点在数组中的序号; 一个域 parent, 用于判定该结点是否已加入哈夫曼树中。哈夫曼树结点的结构为,如图所示:

所以,结点类 Node有 4 个成员字段,weight 表示该结点的权值,lChild和rChild分别表示左、右孩子结点在数组中的序号,parent 表示该结点是否已加入哈夫曼树中,如果 parent的值为-1,表示该结点未加入到哈夫曼树中。当该结点已加入到哈夫曼树中时,parent的值为其双亲结点在数组中的序号。

结点类 Node的定义如下:
public class Node
{
private int weight; //结点权值
private int lChild; //左孩子结点
private int rChild; //右孩子结点
private int parent; //父结点

//结点权值属性
public int Weight
{
get
{
return weight;
}
set
{
weight = value;
}
}

//左孩子结点属性
public int LChild
{
get
{
return lChild;
}
set
{
lChild = value;
}
}

//右孩子结点属性
public int RChild
{
get
{
return rChild;
}
set
{
rChild = value;

}
}

//父结点属性
public int Parent
{
get
{
return parent;
}
set
{
parent = value;
}
}


//构造器

//默认为空  就是空值了
public Node()
{
weight = 0;
lChild = -1;
rChild = -1;
parent = -1;
}

//构造器 

//为权重,做结点,有结点都赋值的吧
public Node(int w, int lc, int rc, int p)
{
weight = w;
lChild = lc;
rChild = rc;
parent = p;
}
}
哈夫曼树类 HuffmanTree中只有一个成员方法 Create,它的功能是输入 n个叶子结点的权值,创建一棵哈夫曼树。哈夫曼树类 HuffmanTree的实现如下。 如图所示:


public class HuffmanTree
{
private Node[] data; //结点数组
private int leafNum; //叶子结点数目

//索引器 运用当前的索引器来遍历的吧
public Node this[int index]
{

get
{
return data[index];
}
set
{
data[index] = value;
}
}

//叶子结点数目属性
public int LeafNum
{
get
{
return leafNum;
}
set
{
leafNum = value;
}
}

//构造器   创建一个2*n-1二叉树   带权叶子的结点为n
public HuffmanTree (int n)
{
data = new Node[2*n-1];
leafNum = n;
}

//创建哈夫曼树   在创建哈夫曼树 就开始了
public void Create()
{
int m1;
int m2;
int x1;
int x2;

//输入 n个叶子结点的权值
for (int i = 0; i < this.leafNum; ++i)
{
data[i].Weight = Console.Read();
}

//处理 n 个叶子结点,建立哈夫曼树
for (int i = 0; i < this.leafNum - 1; ++i)
{
max1 = max2 = Int32.MaxValue;
tmp1 = tmp2 = 0;

//找权重的 最小的结点加入到哈夫曼树。
//在全部结点中找权值最小的两个结点
for (int j = 0; j < this.leafNum + i; ++j)
{
if ((data[i].Weight < max1)
&& (data[i].Parent == -1))
{
max2 = max1;
tmp2 = tmp1;
tmp1 = j;
max1 = data[j].Weight;
}
else if ((data[i].Weight < max2)
&& (data[i].Parent == -1))
{
max2 = data[j].Weight;
tmp2 = j;
}
}

data[tmp1].Parent = this.leafNum + i; //加入其中
data[this.leafNum + i].Weight = data[tmp1].Weight
+ data[tmp2].Weight;
data[this.leafNum + i].LChild = tmp1;
data[this.leafNum + i].RChild = tmp2;
}
}
}

//这个算法的时间的复杂度是O(n²)  具体的情况如上图所示。

 我们花了这么大的篇幅,介绍了哈夫曼树,他能做什么,就是哈夫曼编码。哈夫曼就是把互相的路径写成01,这个应用最常用的应用,就是想win-zip,win-rar就是基于这个基础。

应用举例二。编写算法,在二叉树中查找值为 value的结点。

算法实现如下:
Node<T> Search(Node<T> root, T value)
{
Node<T> p = root;

if (p == null)
{
return null;
}

if (p.Data.Equals(value))
{
return p;
}

if (p.LChild != null)
{
return Search(p.LChild, value);
}

if (p.RChild != null)
{
return Search(p.RChild, value);
}

return null;    由于用到了递归,这个算法的时间的复杂度是O(n²) 如图所示:


}

  统计出二叉树中叶子结点的数目。

  就是 统计其中二叉树的没有子节点的数目。通过递归来查找的。递归实现该算法。如果二叉树为空,则返回 0;如果二叉树只有一个结点,则根结点就是叶子结点,返回 1,否则返回根结点的左分支的叶子结点数目和右分支的叶子结点数目的和。

int CountLeafNode(Node<T> root)
{
if (root == null)
{
return 0;
}
else if (root.LChild == null && root.RChild == null)
{
return 1;
}
else
{

return (CountLeafNode(root.LChild) +
CountLeafNode(root.RChild));
}

由于用到了递归算法的实现,其时间复杂度是O(n²),其中的算法的实现,如图所示:


}

最后一个实例,我们来聊聊一下实际的商业的项目中用到到的树的数据结构,就是比如你构建一个父子级的菜单,这个就是树的典型的应用。这在做数据库设计时候,一个字段ParentCode指向了富集。他最终的效果,如图所示:

    这就是树形数据结构的,典型应用。下篇文章,我们来讨论一下图形结构。

目录
相关文章
|
3月前
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
84 5
|
4月前
|
存储 算法 安全
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
137 8
|
4月前
|
存储 监控 算法
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
97 4
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
135 2
|
5月前
|
人工智能 运维 算法
基于 C# 深度优先搜索算法的局域网集中管理软件技术剖析
现代化办公环境中,局域网集中管理软件是保障企业网络高效运行、实现资源合理分配以及强化信息安全管控的核心工具。此类软件需应对复杂的网络拓扑结构、海量的设备信息及多样化的用户操作,而数据结构与算法正是支撑其强大功能的基石。本文将深入剖析深度优先搜索(Depth-First Search,DFS)算法,并结合 C# 语言特性,详细阐述其在局域网集中管理软件中的应用与实现。
126 3
|
3月前
|
监控 算法 数据处理
内网实时监控中的 C# 算法探索:环形缓冲区在实时数据处理中的关键作用
本文探讨了环形缓冲区在内网实时监控中的应用,结合C#实现方案,分析其原理与优势。作为固定长度的循环队列,环形缓冲区通过FIFO机制高效处理高速数据流,具备O(1)时间复杂度的读写操作,降低延迟与内存开销。文章从设计逻辑、代码示例到实际适配效果展开讨论,并展望其与AI结合的潜力,为开发者提供参考。
183 2
|
3月前
|
监控 算法 安全
公司电脑监控软件关键技术探析:C# 环形缓冲区算法的理论与实践
环形缓冲区(Ring Buffer)是企业信息安全管理中电脑监控系统设计的核心数据结构,适用于高并发、高速率与短时有效的多源异构数据处理场景。其通过固定大小的连续内存空间实现闭环存储,具备内存优化、操作高效、数据时效管理和并发支持等优势。文章以C#语言为例,展示了线程安全的环形缓冲区实现,并结合URL访问记录监控应用场景,分析了其在流量削峰、关键数据保护和高性能处理中的适配性。该结构在日志捕获和事件缓冲中表现出色,对提升监控系统效能具有重要价值。
97 1
|
4月前
|
存储 监控 算法
基于 C# 的局域网计算机监控系统文件变更实时监测算法设计与实现研究
本文介绍了一种基于C#语言的局域网文件变更监控算法,通过事件驱动与批处理机制结合,实现高效、低负载的文件系统实时监控。核心内容涵盖监控机制选择(如事件触发机制)、数据结构设计(如监控文件列表、事件队列)及批处理优化策略。文章详细解析了C#实现的核心代码,并提出性能优化与可靠性保障措施,包括批量处理、事件过滤和异步处理等技术。最后,探讨了该算法在企业数据安全监控、文件同步备份等场景的应用潜力,以及未来向智能化扩展的方向,如文件内容分析、智能告警机制和分布式监控架构。
125 3
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
124 7
|
4月前
|
存储 监控 算法
基于 C# 时间轮算法的控制局域网上网时间与实践应用
在数字化办公与教育环境中,局域网作为内部网络通信的核心基础设施,其精细化管理水平直接影响网络资源的合理配置与使用效能。对局域网用户上网时间的有效管控,已成为企业、教育机构等组织的重要管理需求。这一需求不仅旨在提升员工工作效率、规范学生网络使用行为,更是优化网络带宽资源分配的关键举措。时间轮算法作为一种经典的定时任务管理机制,在局域网用户上网时间管控场景中展现出显著的技术优势。本文将系统阐述时间轮算法的核心原理,并基于 C# 编程语言提供具体实现方案,以期深入剖析该算法在局域网管理中的应用逻辑与实践价值。
103 5