什么是二叉树(binary tree)？

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

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

什么是二叉搜索树(binary search tree)？

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

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

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

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

二叉树与二叉搜索树：比较图

总结 - 二叉树的构造(of binary tree) vs. 二叉搜索树(binary search tree)

虽然两者都模拟了一个表示节点集合的层次树结构，每个节点表示一个值，但它们在实现和利用方式上有很大的不同。二叉树遵循一个简单的规则，即每个父节点的子节点不超过两个，而二叉搜索树只是二叉树的一个变体，二叉树遵循的是节点在树中的组织方式的相对顺序。