二叉树和二进制搜索树

什么是二叉树？

二叉树是一种分层数据结构，其中每个节点具有零个，一个或最多两个子节点。每个节点包含一个“左”指针，一个“右”指针和一个数据元素。 “root”指针表示树中最顶层的节点。数据结构中的每个节点直接连接到任一侧的任意数量的节点，称为子节点。空指针表示二叉树。如何在二叉树中组织节点没有特定的顺序。没有子节点的节点称为叶节点或外部节点。

简单来说，它在节点上定义了一个有组织的标签功能，然后为每个节点分配一些随机值。任何有两个子节点和一个父节点的东西都是二叉树。二叉树用于存储形成层次结构的信息，如个人计算机上的文件系统。与Arrays不同，Trees对节点数没有上限，因为它们使用指针链接，如Linked Lists。二叉树的主要功能包括表示分层数据，排序数据列表，提供有效的插入/删除操作等。树节点使用C中的结构表示。

什么是二进制搜索树？

二进制搜索树是一种二进制树数据结构，其中节点按顺序排列，因此也称为“有序二叉树”。它是一种基于节点的数据结构，提供了一种有效，快速的排序，检索，搜索数据的方法。对于每个节点，左子树中的元素必须小于或等于其父节点中的键（LP）。应该没有重复的密钥。简单来说，它是一种特殊的二叉树数据结构，可以有效地存储和管理内存中的项目。

它允许快速访问信息，插入和删除数据，此外它还可用于实现查找表，允许通过其唯一键搜索项目，例如按名称搜索人员的电话号码。唯一键以有组织的方式排序，以便可以使用二分搜索执行查找和其他动态操作。它支持三个主要操作：元素搜索，元素插入和元素删除。二进制搜索树允许快速检索存储在树中的元素，因为每个节点密钥都与根节点进行了彻底的比较，根节点丢弃了树的一半。

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

1. 二叉树和二叉搜索树的定义 - 二叉树是一种分层数据结构，其中子节点可以有零个，一个或最多两个子节点;每个节点包含一个左指针，一个右指针和一个数据元素。如何在树中组织节点没有特定的顺序。另一方面，二进制搜索树是一个有序的二叉树，其中存在与节点组织方式的相对顺序。
2. 结构体 的 二叉树和二进制搜索树 - 树中最顶层的节点表示二叉树中的根指针，左侧和右侧指针表示任一侧的较小树。它是树的一种特殊形式，表示树结构中的数据。另一方面，二进制搜索树是一种二叉树，其中左子树中的所有节点小于或等于根节点的值，右子树的值大于或等于该值根节点。
3. 手术 的 二叉树和二进制搜索树 - 二叉树可以是任何有两个孩子和一个父母的东西。可以在二叉树上执行的常见操作是插入，删除和遍历。二进制搜索树是更多排序的二叉树，允许快速有效地查找，插入和删除项目。与二叉树不同，二叉搜索树保持其键的排序，因此查找通常实现二进制搜索操作。
4. 类型 的 二叉树和二进制搜索树 - 存在不同类型的二叉树，通常是“完整二叉树”，“完全二叉树”，“完美二叉树”和“扩展二叉树”。一些常见类型的二叉搜索树包括T树，AVL树，Splay树，Tango树，红黑树等。

二叉树与二进制搜索树：比较图表

二叉树	二叉搜索树
二叉树是树的一种特殊形式，它表示树结构中的分层数据。	二进制搜索树是一种二叉树，它将键保持排序顺序以便快速查找。
每个节点必须最多具有两个子节点，每个节点通过有向边从正好一个其他节点连接。	左子树中的节点的值小于或等于根节点的值，并且右子树的节点具有大于或等于根节点的值的值。
节点的组织方式没有相对顺序。	它遵循如何在树中组织节点的明确顺序。
它基本上是一个分层数据结构，是一组称为节点的元素。	它是二叉树的变体，其中节点以相对顺序排列。
它用于在树结构中快速有效地查找数据和信息。	它主要用于元素的插入，删除和搜索。

二叉树和二叉搜索树的总结

虽然两者都模拟表示节点集合的分层树结构，其中每个节点表示一个值，但它们在如何实现和利用它们方面彼此完全不同。二进制树遵循一个简单的规则，即每个父节点不超过两个子节点，而二进制搜索树只是二叉树的变体，它遵循如何在树中组织节点的相对顺序。