许吉友 - 运维

数据结构 - 树

树是一种分层数据结构,由顶点(节点)和连接它们的边组成。树类似于图形(graph),但区分树和图形的关键点是树结构中不存在循环。

树广泛用于人工智能和复杂算法,以提供解决问题的有效存储机制。

这是一个简单树的图像,以及树数据结构中使用的基本术语:

以下是树的类型:

除此之外,二叉树和二叉搜索树是最常用的树。

常见的Tree面试问题

前缀树

堆和二叉堆

堆是一颗具有特定性质的二叉树,堆的基本要求就是堆中所有结点的值必须大于或等于(或小于或等于)其孩子结点的值,这也称为堆的性质;堆还有另一个性质,就是当 h > 0 时,所有叶子结点都处于第 h 或 h - 1 层(其中 h 为树的高度,完全二叉树),也就是说,堆应该是一颗完全二叉树;