第 6 章 理解和实现树

迄今为止，我们对数据结构的探索只涉及线性部分。无论是数组、链表、栈还是队列，都是线性数据结构。我们已经看到了线性数据结构操作的复杂性，大多数情况下，插入和删除的复杂度都可以达到 \$O(1)\$。但是，搜索就有点复杂了，需要 \$O(n)\$ 的复杂度。唯一的例外是 PHP 数组，事实上，它可以像哈希表一样工作，如果索引或键以这种方式管理，则可以在 \$O(1)\$ 的复杂度内进行搜索。为了解决这个问题，我们可以使用分层数据结构来代替线性数据结构。分层数据可以解决许多线性数据结构无法轻松解决的问题。每当我们谈论家族树、组织结构和网络连接图时，我们实际上都在谈论层次结构数据。树是一种特殊的抽象数据类型（ADT），可以表示分层数据。与同为 ADT 的链表不同，树是分层的，而链表则是线性的。在本章中，我们将探索树的世界。家族树就是树形结构的一个完美示例，如下图所示：