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

一棵树的组成部分

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

根：树的根是没有传入链接的节点（即，没有父节点）。将此视为树的起点。

子级：一棵树的子级是一个节点，上面有一个节点（即父节点），有一个传入链接。如果两个子节点共享同一父节点，则它们称为同级。

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

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

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

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

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

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

树木类型

我们可以使用许多类型的树来在层次结构中不同地组织数据。我们使用的树取决于我们要解决的问题。让我们看一下可以在Java中使用的树。我们将介绍：

• Nary树
• 平衡的树木
• 二叉树
• 二叉搜索树
• AVL树
• 红黑树
• 2-3棵树
• 2-3-4树木

一元树

在N元树中，一个节点可以具有0-N的子节点。例如，如果我们有一个2元树（也称为二叉树），它将有最多0-2个子节点。

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

平衡树

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

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

1.完整的二叉树

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

2.完整的二叉树

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

3.完美的二叉树

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

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

二叉搜索树

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

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

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

AVL树

AVL树是二进制搜索树的一种特殊类型，它通过检查每个节点的平衡因子来实现自我平衡。平衡系数的值应为+1，0，或-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-节点具有三个子节点和两个数据元素
• 4节点具有四个子节点和三个数据元素
• 每个内部节点最多有4个子节点
• 对于内部节点上的三个键，LeftChild节点上的所有键都小于左键
• LeftMidChild上的所有键都小于中间键
• RightMidChild上的所有键都小于右键
• RightChild上的所有键都大于右键

深度优先搜索

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

该DFS算法的步骤如下：

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

广度优先搜索

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

该BFS算法的步骤如下：

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

在二叉搜索树中搜索

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

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

在下面的示例中，我们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;
      }
}

总结和后续步骤