二叉树和二叉搜索树的区别

首先，我们将分别理解二叉树和二叉搜索树，然后我们将探讨二叉树和二叉搜索树之间的区别。

什么是二叉树？

二叉树是一种非线性数据结构，其中一个节点最多可以拥有0、1或最多2个子节点。二叉树中的每个节点都表示为父节点或子节点。父节点可以有两个子节点，即左子节点和右子节点。

在二叉树中，从一个节点到其下一个节点只有一种方式。

二叉树中的一个节点有三个字段

• 指向左子节点的指针：它存储左子节点的引用。
• 指向右子节点的指针：它存储右子节点的引用。
• 数据元素：数据元素是节点存储的数据的值。

二叉树可以表示为

在上图中，我们可以看到每个节点最多包含2个子节点。如果某个节点没有左子节点或右子节点，则相应子节点的指针值将为NULL。

二叉树中使用的基本术语是

• 根节点：根节点是二叉树的第一个或最顶部的节点。
• 父节点：当一个节点通过边连接到另一个节点时，该节点称为父节点。在二叉树中，父节点最多可以有2个子节点。
• 子节点：如果一个节点有其前驱节点，则该节点称为子节点。
• 叶节点：没有子节点的节点称为叶节点。
• 内部节点：至少有两个子节点的节点称为内部节点。
• 节点深度：从根节点到给定节点的距离称为节点深度。我们为所有节点提供标签，例如根节点标记为0，因为它没有深度，根节点的子节点标记为1，根节点的子节点的子节点标记为2。
• 高度：从根节点到叶节点的最长距离是节点的度。

在二叉树中，有一种树称为完美二叉树。它是一种树，其中所有内部节点都必须包含两个子节点，并且所有叶节点都必须位于同一深度。对于完美二叉树，二叉树中存在的总节点数可以使用以下公式计算

n = 2^m+1-1

其中 n 是节点数，m 是节点的深度。

什么是二叉搜索树？

二叉搜索树是一种遵循某种顺序排列元素的树，而二叉树不遵循任何顺序。在二叉搜索树中，左子节点的值必须小于父节点的值，而右子节点的值必须大于父节点的值。

让我们通过示例来理解二叉搜索树的概念。

在上图中，我们可以看到根节点的值为15，它大于左子树中所有节点的值。根节点的值小于右子树中所有节点的值。现在，我们移动到根节点的左子节点。10大于8且小于12；它也满足二叉搜索树的属性。现在，我们移动到根节点的右子节点；值20大于17且小于25；它也满足二叉搜索树的属性。因此，我们可以说上图所示的树是二叉搜索树。

现在，如果我们将在上面的二叉树中将12的值更改为16，我们需要找出它是否仍然是二叉搜索树。

根节点的值为15，它大于10但小于16，因此它不满足二叉搜索树的属性。因此，它不是二叉搜索树。

二叉搜索树上的操作

我们可以在二叉搜索树上执行插入、删除和搜索操作。让我们了解如何在二叉搜索树上执行搜索。下面显示了我们要对其执行搜索操作的二叉树。

假设我们要搜索上述二叉树中的10。要执行二叉搜索，我们将考虑排序数组中的所有整数。首先，我们创建一个搜索空间中的完整列表，并且所有数字都将存在于搜索空间中。搜索空间由两个指针标记，即start和end。上面二叉树的数组可以表示为

首先，我们将计算中间元素，并将其与要搜索的元素进行比较。中间元素是通过n/2计算的。n的值为7；因此，中间元素是15。中间元素不等于要搜索的元素，即10。

注意：如果要搜索的元素小于中间元素，则将在左半部分进行搜索；否则，将在右半部分进行搜索。相等的情况下，找到元素。

由于要搜索的元素小于中间元素，因此将在左数组中进行搜索。现在搜索空间减半，如下所示。

左数组中的中间元素是10，它等于要搜索的元素。

时间复杂度

在二叉搜索中，有n个元素。如果中间元素不等于要搜索的元素，则搜索空间减小到n/2，我们将继续将搜索空间减小n/2，直到找到该元素。在整个减小过程中，如果我们从n移动到n/2再到n/4，依此类推，则需要log₂n步。

二叉树与二叉搜索树的区别