摩尔斯电码的结构是二叉树。

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. In a binary tree a degree of every node is maximum two.

二叉树很有用，因为正如你在图中看到的，如果你想找到树中的任何节点，你最多只需要找6次。例如，如果您想搜索节点24，您将从根节点开始。

根节点的值为31，大于24，所以要到左边的节点。 左边节点的值为15，小于24，所以要转到右边节点。 右边节点的值为23，小于24，所以您要转到右边节点。 右边节点的值是27，大于24，所以要转到左边节点。 左边节点的值是25，比24大，所以你到左边节点。 节点的值为24，这是我们要查找的键。

如下图所示:

您可以看到，在第一次传递时就可以排除整个树的一半节点。左边子树的一半在第二个。这使得搜索非常有效。如果这是在40亿个元素上进行的，那么您最多只需要搜索32次。因此，树中包含的元素越多，搜索的效率就越高。

删除会变得很复杂。如果节点有0或1个子节点，那么只需移动一些指针来排除要删除的指针。但是，不能轻易删除具有2个子节点的节点。所以我们走捷径。假设我们要删除节点19。

由于试图确定将左右指针移动到哪里并不容易，所以我们找到一个替换它的指针。我们到左边的子树，尽可能地向右移动。这就给出了我们想要删除的节点的下一个最大值。

现在我们复制18的所有内容，除了左指针和右指针，并删除原来的18节点。

为了创建这些图像，我实现了一棵AVL树，一棵自平衡树，这样在任何时间点，树的叶节点(没有子节点)之间最多有一层差异。这可以防止树变得倾斜，并保持最大的O(log n)搜索时间，而插入和删除需要更多的时间。

下面是一个示例，显示我的AVL树如何保持自己尽可能紧凑和平衡。

在排序数组中，查找仍然需要O(log(n))，就像树一样，但是随机插入和删除将需要O(n)，而不是树的O(log(n))。一些STL容器利用这些性能特征来发挥它们的优势，因此插入和删除时间最多为O(log n)，非常快。这些容器包括map、multimap、set和multiset。

AVL树的示例代码可以在http://ideone.com/MheW8上找到

主要应用是二叉搜索树。这是一种数据结构，其中搜索、插入和删除都非常快(大约log(n)次操作)

争论二叉树的性能是没有意义的——它们不是一种数据结构，而是一组数据结构，它们都具有不同的性能特征。虽然不平衡二叉树的搜索性能确实比自平衡二叉树差得多，但对于许多二叉树(如二进制尝试)来说，“平衡”是没有意义的。

二叉树的应用

Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries. Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered. Binary Tries - Used in almost every high-bandwidth router for storing router-tables. Hash Trees - Used in torrents and specialized image-signatures in which a hash needs to be verified, but the whole file is not available. Also used in blockchains for eg. Bitcoin. Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort. Huffman Coding Tree (Chip Uni) - Used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats. GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers. Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions. Treap - Randomized data structure used in wireless networking and memory allocation. T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

二叉树比n-ary树更常用于搜索的原因是n-ary树更复杂，但通常不会提供真正的速度优势。

在一个有m节点的(平衡的)二叉树中，从一层移动到下一层需要进行一次比较，并且有log_2(m)层，总共有log_2(m)次比较。

相比之下，一个n元树将需要log_2(n)个比较(使用二叉搜索)来移动到下一层。由于总共有log_n(m)个级别，因此搜索将需要log_2(n)*log_n(m) = log_2(m)个比较。因此，尽管n元树更复杂，但就必要的总体比较而言，它们没有提供任何优势。

(然而，n-ary树在生态位环境中仍然有用。首先想到的例子是四叉树和其他空间划分树，其中每层只使用两个节点划分空间会使逻辑不必要地复杂;以及在许多数据库中使用的b -树，其中限制因素不是在每个级别上进行多少比较，而是一次可以从硬盘加载多少节点)

在c++ STL中，以及许多其他语言的标准库中，如Java和c#。二叉搜索树用于实现set和map。

二叉树的应用:

实现路由器中的路由表。 数据压缩码 表达式解析器和表达式求解器的实现 解决数据库问题，如索引。 表达式求值