binary-tree - 二叉树的使用

Question

谁能给我一个需要使用二叉树或什至只是一棵普通树的真实生活示例(在编程中，C#)？

我了解二叉树的原理及其工作原理，但我正试图找到一些现实生活中的使用示例？

托尼

Answer 1

在C#、Java、Python、C++(使用STL)和其他高级语言中，大多数时候你会使用一种内置/库包含的类型来存储你的数据，至少是数据你现在正在工作，所以大多数时候你不会明确地使用二叉树或其他类型的树。

话虽如此，其中一些内置类型在“后台”实现为一种或另一种树，在某些情况下，您必须自己实现一种。

此外，您必须了解的相关内容是二分查找。这主要是在二叉树(二叉搜索树 :P)中完成的，但这个想法可以外推到很多问题，即使不涉及树，所以试着很好地理解它。

编辑:现实生活中的经典例子:

假设您想在大城市的电话指南中搜索某个人的电话号码。在所有条件相同的情况下，您将大致从中间打开它，寻找该页面中的人，看看您的“目标”是在它之前还是之后，从而将数据减半。然后你在你知道你的“目标”所在的那一半重复这个操作，一次又一次，直到你找到你的“目标”。由于每次您查看的数据都是之前的一半，因此总共需要 log(base 2) n 次操作才能达到您的“目标”，其中 n 是数据的总大小。

因此，在 100 万个电话簿中，您在 log(base 2) 100 万 = 20 次比较中找到目标，而不是像线性搜索那样逐个比较(最坏情况下是 100 万次比较)。

请注意，这仅适用于已排序的数据。