数据结构教程系列02:使用Java深入研究树

作者 : IT 大叔 本文共4794个字,预计阅读时间需要12分钟 发布时间: 2020-09-9

数据结构教程系列

数据结构教程系列01:JavaScript数组教程

数据结构教程系列02:使用Java深入研究树

数据结构教程系列03:如何在Java中使用链接列表

数据结构教程系列04:在JavaScript中引入图

数据结构教程系列05:在JavaScript中实现哈希表

数据结构教程系列06:如何在Java中使用堆栈和队列

数据结构是编程和编码采访的重要组成部分。这些技能显示了您进行复杂思考,解决歧义问题和识别编码模式的能力。程序员使用数据结构来组织数据,因此您的数据结构越有效,您的程序就会越好。

今天,我们将深入研究其中最流行的数据结构之一:tree。我们将介绍:

  • 什么是树?
  • 树木类型
  • 树木遍历和搜索简介
  • 后续步骤和总结

现在,让我们开始吧!

什么是树?

数据结构用于存储和组织数据。我们可以使用算法来操纵和使用我们的数据结构。通过使用不同的数据结构,可以更有效地组织不同类型的数据。

是非线性数据结构。它们通常用于表示分层数据。对于一个实际示例,分层的公司结构使用树进行组织。

数据结构教程系列02:使用Java深入研究树插图

一棵树的组成部分

树是节点(顶点)的集合,它们与边(指针)链接,代表节点之间的层次连接。节点包含任何类型的数据,但是所有节点必须具有相同的数据类型。树类似于图,但是树中不能存在循环。一棵树有哪些不同的组成部分?

根:树的根是没有传入链接的节点(即,没有父节点)。将此视为树的起点。

子级:一棵树的子级是一个节点,上面有一个节点(即父节点),有一个传入链接。如果两个子节点共享同一父节点,则它们称为同级。

节点父节点具有一个将其连接到一个或多个子节点的传出链接。

叶子:叶子具有父节点,但没有到子节点的传出链接。将此视为树的端点。

树:子树是在较大树中保存的较小树。该树的根可以是较大树的任何节点。

深度:节点的深度是该节点与根之间的边数。可以认为这是您的节点与树的起点之间有多少步骤。

高度:节点的高度是从节点到叶节点的最长路径中的边数。可以认为这是您的节点和树的端点之间有多少步骤。一棵树的高度是其根节点的高度。

程度:节点的程度是指子树的数量。

数据结构教程系列02:使用Java深入研究树插图(2)

我们为什么要用树?

树木可以应用于许多事物。层次结构为树提供了用于存储,操作和访问数据的独特属性。树构成了一些最基本的计算机组织。我们可以将树用于以下用途:

  • 存储为层次结构。存储自然存在于层次结构中的信息。计算机上的文件系统和PDF使用树形结构。
  • 正在搜寻。存储我们要快速搜索的信息。树比链接列表更容易搜索。某些类型的树(例如AVL和红黑树)被设计用于快速搜索。
  • 遗产。树用于继承,XML解析器,机器学习和DNS等。
  • 索引。诸如B树和B +树之类的高级树可以用于索引数据库
  • 联网。树木是社交网络和国际象棋游戏之类的理想选择。
  • 最短的路径。生成树可用于查找路由器中用于网络的最短路径。
  • 以及更多

如何做一棵树

但是,所有这些在代码中如何看待?例如,要在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个子节点。

12346378

N元树

注意: 节点的平衡因子是左右子树之间的高度差。

平衡树

平衡树是几乎所有叶节点都处于同一级别的树,并且最常应用于子树,这意味着所有子树必须是平衡的。换句话说,我们必须使树的高度平衡,其中左右子树的高度之差不超过1。这是平衡树的视觉表示。

1234567

二叉树

基于二进制树的结构,主要有三种类型。

1.完整的二叉树

当每个级别(不包括最后一个级别)都已填充且最后一个级别的所有节点都尽其所能时,就存在一个完整的二叉树。这是完整二叉树的直观表示。

125346

完整的二叉树(左侧完全填充)

2.完整的二叉树

当每个节点(不包括叶子)具有两个子节点时,将退出完整的二叉树(有时称为适当的二叉树)。必须填满每个级别,并且节点要尽可能地靠左。查看此图以了解完整的二叉树的外观。

1234567

完整的二叉树

3.完美的二叉树

一个完美的二叉树应该既完整又完整。所有内部节点应具有两个子节点,所有叶子的深度必须相同。查看此图以了解完美的二叉树的外观。

1234567

完美的二叉树

注意:您也可以有一个偏斜的二叉树,其中所有节点都向左或向右移动,但是最好的做法是在Java中避免这种类型的树,因为搜索节点要复杂得多。

二叉搜索树

二进制搜索树是一个二进制树,其中每个节点都有一个键和一个关联值。这允许快速查找和编辑(添加或删除),因此命名为“搜索”。二叉搜索树基于其node值具有严格的条件。重要的是要注意,每个二进制搜索树都是一个二进制树,但并不是每个二进制树都是一个二进制搜索树。

是什么使它们与众不同?在二叉搜索树中,子树的左子树必须包含的键数比节点的键数少的节点,而右子树将包含其键号大于该节点的键数的节点。看一看这个视觉,以了解这种情况。

Node XNode YSubTree 3SubTree 1SubTree 2

在此示例中,节点Y是具有两个子节点的父节点。子树1中的所有节点的值都必须小于节点Y,子树2的值必须大于节点Y。

AVL树

AVL树是二进制搜索树的一种特殊类型,它通过检查每个节点的平衡因子来实现自我平衡。平衡系数的值应为+10,或-1。左右子树之间的最大高度差只能为1

如果这种差异大于一,我们必须使用旋转技术重新平衡树以使其有效。这些对于搜索是最重要的操作的应用程序最为常见。查看此视觉效果以查看有效的AVL树。

64835207

红黑树

红黑树是自平衡二进制搜索树的另一种类型,但它具有AVL树的一些其他属性。节点被着色为红色或黑色,以帮助在插入或删除后重新平衡树。它们通过平衡为您节省了时间。那么,我们如何为节点着色?

  • 根永远是黑色的
  • 两个红色节点不能相邻(即红色父节点不能有红色子节点)
  • 从根到叶的路径应包含相同数量的黑色节点
  • 空节点为黑色
数据结构教程系列02:使用Java深入研究树插图(4)

一棵有效的红黑树

2-3棵树

2-3棵树与我们到目前为止所学的完全不同。与二叉搜索树不同,2-3树是一种自平衡,有序多路搜索树。它始终是完美平衡的,因此每个叶节点都与根等距。除叶节点外,每个节点都可以是2节点(具有单个数据元素和两个孩子的节点)或3节点(具有两个数据元素和三个孩子的节点)。无论发生多少插入或删除,2-3棵树都将保持平衡。

数据结构教程系列02:使用Java深入研究树插图(6)

2-3-4树木

2-3-4树是一种搜索树,它可以容纳比2-3树更多的键。它涵盖了与2-3棵树相同的基础,但是增加了以下属性:

  • 2节点具有两个子节点和一个数据元素
  • 3-节点具有三个子节点和两个数据元素
  • 4节点具有四个子节点和三个数据元素
  • 每个内部节点最多有4个子节点
  • 对于内部节点上的三个键,LeftChild节点上的所有键都小于左键
  • LeftMidChild上的所有键都小于中间键
  • RightMidChild上的所有键都小于右键
  • RightChild上的所有键都大于右键

数据结构教程系列02:使用Java深入研究树插图(8)

继续学习。

树木遍历和搜索简介

要使用树,我们可以通过访问/检查树的每个节点来遍历它们。如果“遍历”一棵树,则意味着已访问每个节点。有四种遍历树的方法。这四个过程属于以下两类之一:广度优先遍历或深度优先遍历。

  • 顺序:将其想象成是向上移动树然后向下移动。您遍历左孩子及其子树,直到到达根。然后,遍历正确的孩子及其子树。这是深度优先遍历。
  • 预购:从顶部开始,向下移动,然后结束。您从根开始,遍历左侧的子树,然后移至右侧的子树。这是深度优先遍历。
  • 后置订单:从左子树开始,然后移到右子树。然后,向上移动以访问根节点。这是深度优先遍历。
  • Levelorder:将此视为一种锯齿形模式。这将遍历节点的级别而不是子树。首先,我们从左到右访问根并访问该根的所有子代。然后,我们向下移动到下一个级别,直到到达没有子节点的节点。这是左节点。这是广度优先的遍历。

那么,广度优先遍历深度优先遍历有什么区别?让我们看一下深度优先搜索(DFS)和呼吸优先搜索(BFS)的算法,以更好地理解这一点。

注意:算法是用于执行某些任务的一系列指令。在这种情况下,我们使用具有数据结构的算法来操纵我们的数据以遍历我们的数据。

深度优先搜索

概述:我们遵循从起始节点到结束节点的路径,然后开始另一条路径,直到访问了所有节点。这通常使用堆栈来实现,并且比BFS需要更少的内存。最好用于地形排序,例如图形回溯或循环检测。

DFS算法的步骤如下:

  1. 选择一个节点。将所有相邻节点推入堆栈。
  2. 从该堆栈中弹出一个节点,然后将相邻节点推入另一个堆栈。
  3. 重复此操作,直到堆栈为空或达到目标为止。当您访问节点时,必须visited在继续之前将它们标记为,否则您将陷入无限循环。

广度优先搜索

概述:我们逐级进行操作,以在访问下一级别之前访问一个级别的所有节点。BFS算法通常使用队列来实现,并且比DFS算法需要更多的内存。最好找到两个节点之间的最短路径。

BFS算法的步骤如下:

  1. 选择一个节点。将所有相邻节点排入队列。使节点出队,并将其标记为已访问。将所有相邻节点排入另一个队列。
  2. 重复直到队列中的人都达到目标为止。
  3. 当您访问节点时,必须visited在继续之前将它们标记为,否则您将陷入无限循环。

在二叉搜索树中搜索

知道如何在树中进行搜索很重要。搜索意味着我们正在数据结构中定位特定的元素或节点。由于二进制搜索树中的数据是有序的,因此搜索非常容易。让我们看看它是如何完成的。

  1. 从根开始。
  2. 如果该值小于当前节点的值,则遍历左子树。如果更多,我们遍历正确的子树。
  3. 继续此过程,直到达到node具有该值的a或达到一个Leaf node,这意味着该值不存在。

在下面的示例中,我们3在树中搜索值。看一看。

5216-43

这是我们的树。由于3小于5,因此我们遍历左子树。

5216-43

因为3大于2,所以我们移到合适的孩子。

5216-43

找到了搜索到的值。

让我们现在在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

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论