龙空技术网

用 Java 深入研究树

微风01 104

前言:

目前你们对“java研究”大约比较重视,兄弟们都想要分析一些“java研究”的相关资讯。那么小编也在网上收集了一些有关“java研究””的相关文章,希望你们能喜欢,兄弟们快快来了解一下吧!

树数据结构在我们编码和面试中都是很重要的知识。使用数据结构来组织数据,数据结构越高效,程序就会越好。

今天,我们将深入探讨数据结构之一:

今天,我们将介绍:

什么是树?树的种类树的遍历和搜索什么是树?

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

是非线性数据结构。它们通常用于表示分层数据。举一个现实的例子,分层的公司结构使用树来组织。

树的组成部分

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

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

子节点:树的子节点是一个节点,具有来自其上方节点(即父节点)的一个传入链接。如果两个子节点共享同一个父节点,则它们称为兄弟节点。

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

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

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

深度:节点的深度是该节点与根之间的边数。将此视为节点和树的起点之间有多少步。

高度:节点的高度是从该节点到叶节点的最长路径中的边数。将此视为节点和树端点之间有多少步。树的高度是其根节点的高度。

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

我们为什么要使用树?

树可以应用于很多事情。层次结构赋予树用于存储、操作和访问数据的独特属性。树构成了计算机最基本的组织结构。我们可以将树用于以下用途:

存储为层次结构。存储层次结构中自然出现的信息。计算机上的文件系统和 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 中使用的树。我们将涵盖:

N叉树平衡树二叉树二叉搜索树AVL树红黑树2-3 棵树2-3-4 树N叉树

在N叉树中,一个节点可以有0-N个子节点。例如,如果我们有一个二叉树(也称为二叉树),它最多有 0-2 个子节点。

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

平衡树

平衡树是几乎所有叶子节点都在同一级别的树,最常应用于子树,即所有子树都必须是平衡的。换句话说,我们必须使树高平衡,左右子树的高度差不超过1。这是平衡树的直观表示。

根据其结构,二叉树主要分为三种类型。

1.完全二叉树

当每一层(不包括最后一层)都被填满并且最后一层的所有节点都尽可能靠左时,就存在完全二叉树。这是完整二叉树的直观表示。

2. 满二叉树

当每个节点(不包括叶子)都有两个子节点时,就存在满二叉树(有时称为真二叉树)。每一层都必须填满,并且节点尽可能远离。查看此图以了解完整二叉树的外观。

3.完美二叉树

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

注意:还可以拥有倾斜二叉树,其中所有节点都向左或向右移动,但最佳实践是在 Java 中避免这种类型的树,因为搜索节点要复杂得多。

二叉搜索树

二叉搜索树是一棵二叉树,其中每个节点都有一个键和一个关联值。这允许快速查找和编辑(添加或删除),因此得名“搜索”。二叉搜索树根据其node值有严格的条件。需要注意的是,每个二叉搜索树都是二叉树,但并非每个二叉树都是二叉搜索树。

是什么让他们与众不同?在二叉搜索树中,子树的左子树必须包含键少于该节点键的节点,而右子树将包含键大于该节点键的节点。查看此视觉效果以了解这种情况。

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

AVL树

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

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

红黑树

红黑树是另一种自平衡二叉搜索树,但它具有 AVL 树的一些附加属性。节点的颜色为红色或黑色,以帮助在插入或删除后重新平衡树。它们可以节省平衡时间。那么,我们如何为节点着色呢?

根部始终是黑色的两个红色节点不能相邻(即红色父节点不能有红色子节点)从根到叶的路径应包含相同数量的黑色节点空节点是黑色的2-3 棵树

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

2-3-4 树

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

2-节点有两个子节点和一个数据元素3-Node 有三个子节点和两个数据元素4-节点有四个子节点和三个数据元素每个内部节点最多有 4 个子节点对于内部节点的三个键,LeftChild节点的所有键都小于左键LeftMidChild 上的所有键都小于中间键RightMidChild 处的所有键都小于右侧键RightChild 处的所有键都大于右侧键树遍历和搜索简介

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

中序:将其视为在树上向上移动,然后向下移动。遍历左子树及其子树,直到到达根。然后,向下遍历右孩子及其子树。这是深度优先遍历。前序:从根开始,遍历左子树,然后移动到右子树。这是深度优先遍历。后序:从左子树开始,移至右子树。然后,向上移动访问根节点。这是深度优先遍历。层序:将其视为一种之字形图案。这将按节点的级别而不是子树遍历节点。首先,我们访问根并从左到右访问该根的所有子节点。然后我们向下移动到下一个级别,直到到达没有子节点的节点。这是左节点。这是广度优先的遍历。

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

注意:算法是用于执行某些任务的指令序列。我们使用具有数据结构的算法来操作我们的数据,在本例中是遍历我们的数据。

深度优先搜索

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

算法步骤DFS如下:

选择一个节点。将所有相邻节点压入堆栈。从该堆栈中弹出一个节点并将相邻节点推入另一个堆栈。重复此步骤,直到堆栈为空或达到目标为止。当访问节点时,必须在继续之前将其标记为已访问,否则将陷入无限循环。广度优先搜索

概述:我们逐级访问一级的所有节点,然后再进入下一级。BFS算法通常使用队列来实现,并且它比DFS算法需要更多的内存。最适合寻找两个节点之间的最短路径。

算法步骤BFS如下:

选择一个节点。将所有相邻节点放入队列中。将节点出队,并将其标记为已访问。将所有相邻节点放入另一个队列中。重复此操作,直到队列中没有已实现的目标。当访问节点时,必须在继续之前将其标记为已访问,否则将陷入无限循环。在二叉搜索树中搜索

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

从根开始。如果该值小于当前节点的值,则遍历左子树。如果大于,则遍历右子树。继续此过程,直到到达具有该值的节点或到达叶节点,这意味着该值不存在。

在3.中步奏,如下

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