数据结构教程系列02:使用Java深入研究树
数据结构教程系列
数据结构是编程和编码采访的重要组成部分。这些技能显示了您进行复杂思考,解决歧义问题和识别编码模式的能力。程序员使用数据结构来组织数据,因此您的数据结构越有效,您的程序就会越好。
今天,我们将深入研究其中最流行的数据结构之一:tree。我们将介绍:
- 什么是树?
- 树木类型
- 树木遍历和搜索简介
- 后续步骤和总结
现在,让我们开始吧!
什么是树?
数据结构用于存储和组织数据。我们可以使用算法来操纵和使用我们的数据结构。通过使用不同的数据结构,可以更有效地组织不同类型的数据。
树是非线性数据结构。它们通常用于表示分层数据。对于一个实际示例,分层的公司结构使用树进行组织。
一棵树的组成部分
树是节点(顶点)的集合,它们与边(指针)链接,代表节点之间的层次连接。节点包含任何类型的数据,但是所有节点必须具有相同的数据类型。树类似于图,但是树中不能存在循环。一棵树有哪些不同的组成部分?
根:树的根是没有传入链接的节点(即,没有父节点)。将此视为树的起点。
子级:一棵树的子级是一个节点,上面有一个节点(即父节点),有一个传入链接。如果两个子节点共享同一父节点,则它们称为同级。
父节点:父节点具有一个将其连接到一个或多个子节点的传出链接。
叶子:叶子具有父节点,但没有到子节点的传出链接。将此视为树的端点。
子树:子树是在较大树中保存的较小树。该树的根可以是较大树的任何节点。
深度:节点的深度是该节点与根之间的边数。可以认为这是您的节点与树的起点之间有多少步骤。
高度:节点的高度是从节点到叶节点的最长路径中的边数。可以认为这是您的节点和树的端点之间有多少步骤。一棵树的高度是其根节点的高度。
程度:节点的程度是指子树的数量。
如何做一棵树
但是,所有这些在代码中如何看待?例如,要在Java中构建树,我们从根节点开始。
Node<String> root = new Node<>("root");
拥有根之后,我们可以使用来添加第一个子节点addChild
,这将添加一个子节点并将其分配给父节点。我们将此过程称为插入(添加节点)和删除(删除节点)。
Node<String> node1 = root.addChild(new Node<String>("node 1"));
我们将继续使用相同的过程添加节点,直到我们拥有复杂的层次结构。在下一节中,让我们看一下可以使用的各种树。
树木类型
我们可以使用许多类型的树来在层次结构中不同地组织数据。我们使用的树取决于我们要解决的问题。让我们看一下可以在Java中使用的树。我们将介绍:
- Nary树
- 平衡的树木
- 二叉树
- 二叉搜索树
- AVL树
- 红黑树
- 2-3棵树
- 2-3-4树木
一元树
在N元树中,一个节点可以具有0-N的子节点。例如,如果我们有一个2元树(也称为二叉树),它将有最多0-2个子节点。
N元树
注意: 节点的平衡因子是左右子树之间的高度差。
平衡树
平衡树是几乎所有叶节点都处于同一级别的树,并且最常应用于子树,这意味着所有子树必须是平衡的。换句话说,我们必须使树的高度平衡,其中左右子树的高度之差不超过1。这是平衡树的视觉表示。
二叉树
基于二进制树的结构,主要有三种类型。
1.完整的二叉树
当每个级别(不包括最后一个级别)都已填充且最后一个级别的所有节点都尽其所能时,就存在一个完整的二叉树。这是完整二叉树的直观表示。
完整的二叉树(左侧完全填充)
2.完整的二叉树
当每个节点(不包括叶子)具有两个子节点时,将退出完整的二叉树(有时称为适当的二叉树)。必须填满每个级别,并且节点要尽可能地靠左。查看此图以了解完整的二叉树的外观。
完整的二叉树
3.完美的二叉树
一个完美的二叉树应该既完整又完整。所有内部节点应具有两个子节点,所有叶子的深度必须相同。查看此图以了解完美的二叉树的外观。
完美的二叉树
注意:您也可以有一个偏斜的二叉树,其中所有节点都向左或向右移动,但是最好的做法是在Java中避免这种类型的树,因为搜索节点要复杂得多。
二叉搜索树
二进制搜索树是一个二进制树,其中每个节点都有一个键和一个关联值。这允许快速查找和编辑(添加或删除),因此命名为“搜索”。二叉搜索树基于其node
值具有严格的条件。重要的是要注意,每个二进制搜索树都是一个二进制树,但并不是每个二进制树都是一个二进制搜索树。
是什么使它们与众不同?在二叉搜索树中,子树的左子树必须包含的键数比节点的键数少的节点,而右子树将包含其键号大于该节点的键数的节点。看一看这个视觉,以了解这种情况。
在此示例中,节点Y是具有两个子节点的父节点。子树1中的所有节点的值都必须小于节点Y,子树2的值必须大于节点Y。
AVL树
AVL树是二进制搜索树的一种特殊类型,它通过检查每个节点的平衡因子来实现自我平衡。平衡系数的值应为+1,0,或-1。左右子树之间的最大高度差只能为1。
如果这种差异大于一,我们必须使用旋转技术重新平衡树以使其有效。这些对于搜索是最重要的操作的应用程序最为常见。查看此视觉效果以查看有效的AVL树。
红黑树
红黑树是自平衡二进制搜索树的另一种类型,但它具有AVL树的一些其他属性。节点被着色为红色或黑色,以帮助在插入或删除后重新平衡树。它们通过平衡为您节省了时间。那么,我们如何为节点着色?
- 根永远是黑色的
- 两个红色节点不能相邻(即红色父节点不能有红色子节点)
- 从根到叶的路径应包含相同数量的黑色节点
- 空节点为黑色
要使用树,我们可以通过访问/检查树的每个节点来遍历它们。如果“遍历”一棵树,则意味着已访问每个节点。有四种遍历树的方法。这四个过程属于以下两类之一:广度优先遍历或深度优先遍历。
- 顺序:将其想象成是向上移动树然后向下移动。您遍历左孩子及其子树,直到到达根。然后,遍历正确的孩子及其子树。这是深度优先遍历。
- 预购:从顶部开始,向下移动,然后结束。您从根开始,遍历左侧的子树,然后移至右侧的子树。这是深度优先遍历。
- 后置订单:从左子树开始,然后移到右子树。然后,向上移动以访问根节点。这是深度优先遍历。
- Levelorder:将此视为一种锯齿形模式。这将遍历节点的级别而不是子树。首先,我们从左到右访问根并访问该根的所有子代。然后,我们向下移动到下一个级别,直到到达没有子节点的节点。这是左节点。这是广度优先的遍历。
那么,广度优先遍历和深度优先遍历有什么区别?让我们看一下深度优先搜索(DFS)和呼吸优先搜索(BFS)的算法,以更好地理解这一点。
注意:算法是用于执行某些任务的一系列指令。在这种情况下,我们使用具有数据结构的算法来操纵我们的数据以遍历我们的数据。
深度优先搜索
概述:我们遵循从起始节点到结束节点的路径,然后开始另一条路径,直到访问了所有节点。这通常使用堆栈来实现,并且比BFS需要更少的内存。最好用于地形排序,例如图形回溯或循环检测。
该DFS
算法的步骤如下:
- 选择一个节点。将所有相邻节点推入堆栈。
- 从该堆栈中弹出一个节点,然后将相邻节点推入另一个堆栈。
- 重复此操作,直到堆栈为空或达到目标为止。当您访问节点时,必须
visited
在继续之前将它们标记为,否则您将陷入无限循环。
广度优先搜索
概述:我们逐级进行操作,以在访问下一级别之前访问一个级别的所有节点。BFS算法通常使用队列来实现,并且比DFS算法需要更多的内存。最好找到两个节点之间的最短路径。
该BFS
算法的步骤如下:
- 选择一个节点。将所有相邻节点排入队列。使节点出队,并将其标记为已访问。将所有相邻节点排入另一个队列。
- 重复直到队列中的人都达到目标为止。
- 当您访问节点时,必须
visited
在继续之前将它们标记为,否则您将陷入无限循环。
在二叉搜索树中搜索
知道如何在树中进行搜索很重要。搜索意味着我们正在数据结构中定位特定的元素或节点。由于二进制搜索树中的数据是有序的,因此搜索非常容易。让我们看看它是如何完成的。
- 从根开始。
- 如果该值小于当前节点的值,则遍历左子树。如果更多,我们遍历正确的子树。
- 继续此过程,直到达到
node
具有该值的a或达到一个Leafnode
,这意味着该值不存在。
在下面的示例中,我们3
在树中搜索值。看一看。
这是我们的树。由于3小于5,因此我们遍历左子树。
因为3大于2,所以我们移到合适的孩子。
找到了搜索到的值。
让我们现在在Java代码中看到它!
public class BinarySearchTree { … public boolean search(int value) { if (root == null) return false; else return root.search(value); } } public class BSTNode { … public boolean search(int value) { if (value == this.value) return true; else if (value < this.value) { if (left == null) return false; else return left.search(value); } else if (value > this.value) { if (right == null) return false; else return right.search(value); } return false; } }
总结和后续步骤
希望您学到了一些有关树的新知识,并可以继续您的Java和数据结构领域的探索。在Java中掌握树的知识和实践还有很多。为了更好地了解如何使用树,以下是一些常见的数据结构挑战。
- 查找二叉搜索树的最小值
- 在二叉搜索树中找到给定节点的祖先
- 查找二叉树的高度
- 查找距根“ k”距离的节点
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 数据结构教程系列02:使用Java深入研究树
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。