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

什么是二叉树?

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

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

什么是二进制搜索树?

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

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

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

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

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

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

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

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