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

简介:

这节重点讨论 树的结构的源代码实现。

先做一铺垫,讨论一下二叉树的存储结构。二叉树的存储结构分为线性存储和链式存储等等。

1、二叉树的顺序存储结构
对于一棵完全二叉树,由性质 5可计算得到任意结点 i 的双亲结点序号、左孩子结点序号和右孩子结点序号。所以,完全二叉树的结点可按从上到下和从左到右的顺序存储在一维数组中,其结点间的关系可由性质 5计算得到,这就是二叉树的顺序存储结构。下图所示的二叉树的顺序存储结构为:

但是,对于一棵非完全二叉树,不能简单地按照从上到下和从左到右的顺序存放在一维数组中, 因为数组下标之间的关系不能反映二叉树中结点之间的逻辑关系。 所以, 应该对一棵非完全二叉树进行改造, 增加空结点 (并不存在的结点)使之成为一完全二叉树,然后顺序存储在一维数组中。下图(a)是

完全二叉树形态,下图(b)是顺序存储示意图。

显然, 顺序存储对于需增加很多空结点才能改造为一棵完全二叉树的二叉树适合,因为会造成空间的大量浪费。实际上,采用顺序存储结构,是对非线性
的数据结构线性化,用线性结构来表示二叉树的结点之间的逻辑关系,所以,需要增加空间。一般来说,有大约一半的空间被浪费。最差的情况是右单支树,如
下图所示,一棵深度为k的右单支树,只有k个结点,却需要分配 2k-1个存储单元。

二叉树的链式存储分为二叉链式存储和三叉链式存储。

二叉树的二叉链式存储:

二叉树的二叉链表存储结构是指二叉树的结点有三个域: 一个数据域和两个引用域,数据域存储数据,两个引用域分别存放其左、右孩子结点的地址。当左
孩子或右孩子不存在时,相应域为空,用符号 NULL 或∧表示。结点的存储结构如下所示:

二叉树的三叉链式存储:

使用二叉链表,可以非常方便地访问一个结点的子孙结点,但要访问祖先结点非常困难。 可以考虑在每个结点中再增加一个引用域存放其双亲结点的地址信息,这样就可以通过该引用域非常方便地访问其祖先结点。这就是下面要介绍的三叉链表。
二叉树的三叉链表存储结构是指二叉树的结点有四个域: 一个数据域和三个引用域,数据域存储数据,三个引用域分别存放其左、右孩子结点和双亲结点的地址。当左、右孩子或双亲结点不存在时,相应域为空,用符号 NULL 或∧表示。结点的存储结构如下所示:

简单的介绍了二叉树的存储结构后,我们重点看一看他的源代码的实现,这是这篇文章的重点。

二叉树的二叉链表的结点类有 3个成员字段:数据域字段 data、左孩子引用域字段 lChild和右孩子引用域字段 rChild。二叉树的二叉链表的结点类的实现如下所示。

 

public class Node<T>
{
private T data; //数据域
private Node<T> lChild; //左孩子
private Node<T> rChild; //右孩子  如下图所示

//构造器 赋值给相应的数据域,左孩子,右孩子。如图所示
public Node(T val, Node<T> lp, Node<T> rp)
{
data = val;
lChild = lp;
lChild = rp;
}


//构造器 赋值给相应相应的左孩子,右孩子,数据域赋值给相应的默认值 如图所示
public Node(Node<T> lp, Node<T> rp)
{
data = default(T);
lChild = lp;
rChild = rp;
}

//构造器 赋值给相应的数据域,左孩子为空,右孩子为空。如图所示
public Node(T val)
{
data = val;
lChild = null;
rChild = null;
}


//构造器 赋值给相应的 左孩子,右孩子为空,数据域为空。如图所示
public Node()
{
data = default(T);
lChild = null;
rChild = null;
}


//数据属性
public T Data
{
get
{
return data;
}
set
{
value = data;
}
}

//左孩子属性
public Node<T> LChild
{
get
{
return lChild;
}
set
{
lChild = value;
}
}

public Node<T> RChild
{
get
{
return rChild;
}
set
{
rChild = value;
}
}

 

}

不带头结点的二叉树的二叉链表比带头结点的二叉树的二叉链表的区别与不带头结点的单链表与带头结点的单链表的区别一样。 下面只介绍不带头结点的二叉树的二叉链表的类 BiTree<T>。BiTree<T>类只有一个成员字段 head表示头引用。以下是 BiTree<T>类的源代码实现。

public class BiTree<T>
{
private Node<T> head; //头引用 默认指向了根结点

//头引用属性
public Node<T> Head
{
get
{
return head;
}
set
{
head = value;
}
}

//构造器
public BiTree()
{
head = null;
}

//构造器
public BiTree(T val)
{
Node<T> p = new Node<T>(val);
head = p;

}

//构造器
public BiTree(T val, Node<T> lp, Node<T> rp)
{
Node<T> p = new Node<T>(val,lp,rp);
head = p;
}

//判断是否是空二叉树
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}

//获取根结点
public Node<T> Root()
{
return head;
}

//获取结点的左孩子结点
public Node<T> GetLChild(Node<T> p)
{
return p.LChild;
}

//获取结点的右孩子结点
public Node<T> GetRChild(Node<T> p)
{
return p.RChild;
}

//将结点p的左子树插入值为val的新结点,
//原来的左子树成为新结点的左子树
public void InsertL(T val, Node<T> p)
{

Node<T> tmp = new Node<T>(val);
tmp.LChild = p.LChild;
p.LChild = tmp;
}

//将结点p的右子树插入值为val的新结点,
//原来的右子树成为新结点的右子树
public void InsertR(T val, Node<T> p)
{
Node<T> tmp = new Node<T>(val);
tmp.RChild = p.RChild;
p.RChild = tmp;
}
算法的复杂度是O(1)
//若p非空,删除p的左子树
public Node<T> DeleteL(Node<T> p)
{
if ((p == null) || (p.LChild == null))
{
return null;
}

Node<T> tmp = p.LChild;
p.LChild = null;

return tmp;
}
算法的复杂度是O(1)
//若p非空,删除p的右子树
public Node<T> DeleteR(Node<T> p)
{
if ((p == null) || (p.RChild == null))
{
return null;
}

Node<T> tmp = p.RChild;
p.RChild = null;

return tmp;
}
算法的复杂度是O(1)
//判断是否是叶子结点
public bool IsLeaf(Node<T> p)

{
if ((p != null) && (p.LChild == null) && (p.RChild == null))
{
return true;
}
else
{
return false;
}
}

这些操作的具体情况如图所示:


}

由于类中基本操作都比较简单,这里不一一详细说明。

说完这些操作,我们再看看他的遍历的实现

二叉树的遍历是指按照某种顺序访问二叉树中的每个结点, 使每个结点被访问一次且仅一次。遍历是二叉树中经常要进行的一种操作,因为在实际应用中,常常要求对二叉树中某个或某些特定的结点进行处理, 这需要先查找到这个或这些结点。
实际上, 遍历是将二叉树中的结点信息由非线性排列变为某种意义上的线性排列。也就是说,遍历操作使非线性结构线性化。
由二叉树的定义可知,一棵二叉树由根结点、左子树和右子树三部分组成,若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树的遍历方式有 6种:DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式:DLR(先序遍历) 、LDR(中序遍历)和 LRD(后序遍历) 。 除了这三种遍历方式外,还有一种方式:层序遍历(Level Order)。层序遍历
是从根结点开始, 按照从上到下、 从左到右的顺序依次访问每个结点一次仅一次。 由于树的定义是递归的,所以遍历算法也采用递归实现。下面分别介绍这四
种算法,并把它们作为 BiTree<T>类成员方法。

先序遍历的基本思想是:首先访问根结点,然后先序遍历其左子树,最后先序遍历其右子树。先序遍历的递归算法实现如下,注意:这里的访问根结点是把根结点的值输出到控制台上。当然,也可以对根结点作其它处理。
public void PreOrder(Node<T> root)
{
//根结点为空
if (root == null)
{
return;
}

//处理根结点
Console.WriteLine("{0}", root.Data);

//先序遍历左子树

PreOrder(root.LChild);

//先序遍历右子树
PreOrder(root.RChild);  

这个算法的复杂度是O(n²) 如图所示:


}

2、中序遍历(LDR)
中序遍历的基本思想是:首先中序遍历根结点的左子树,然后访问根结点,
最后中序遍历其右子树。中序遍历的递归算法实现如下:
public void InOrder(Node<T> root)
{
//根结点为空
if (root == null)
{
return;
}

//中序遍历左子树
InOrder(root.LChild);

//处理根结点
Console.WriteLine("{0}", root.Data);

//中序遍历右子树
InOrder(root.RChild);

算法的复杂度是O(n²) 如图所示:


}

3、后序遍历(LRD)
后序遍历的基本思想是:首先后序遍历根结点的左子树,然后后序遍历根结
点的右子树,最后访问根结点。后序遍历的递归算法实现如下,
public void PostOrder(Node<T> root)
{
//根结点为空
if (root == null)
{
return;
}

//后序遍历左子树
PostOrder(root.LChild);

//后序遍历右子树

PostOrder(root.RChild);

//处理根结点
Console.WriteLine("{0}", root.Data);

算法的复杂度是O(n²)。如图所示:

 

}

 

4、层序遍历(Level Order)
层序遍历的基本思想是:由于层序遍历结点的顺序是先遇到的结点先访问,与队列操作的顺序相同。所以,在进行层序遍历时,设置一个队列,将根结点引用入队,当队列非空时,循环执行以下三步:
(1) 从队列中取出一个结点引用,并访问该结点;
(2) 若该结点的左子树非空,将该结点的左子树引用入队;
(3) 若该结点的右子树非空,将该结点的右子树引用入队;
层序遍历的算法实现如下:
public void LevelOrder(Node<T> root)
{
//根结点为空
if (root == null)
{
return;
}

//设置一个队列保存层序遍历的结点
CSeqQueue<Node<T>> sq = new CSeqQueue<Node<T>>(50);

//根结点入队
sq.In(root);

//队列非空,结点没有处理完
while (!sq.IsEmpty())
{
//结点出队
Node<T> tmp = sq.Out();

//处理当前结点
Console.WriteLine("{o}", tmp);

//将当前结点的左孩子结点入队
if (tmp.LChild != null)
{
sq.In(tmp.LChild);
}

if (tmp.RChild != null)
{
sq.In(tmp.RChild);
}
}

算法的复杂度是O(n²) 如图所示:


}

这篇文章,我们介绍了二叉树的源代码的实现,一些基本的常识已经介绍完成了。我们下届还补充一些树案例,更好的利用树的作用。

目录
相关文章
|
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