简介

概念解释

树(Tree)是一个分层的数据结构，由节点和连接节点的边组成。树是一种特殊的图，它与图最大的区别是没有循环。

树被广泛应用在人工智能和一些复杂算法中，用来提供高效的存储结构。

下图是一个简单的树以及与树相关的术语：

树有很多分类：

• N叉树(N-ary Tree)

• 平衡树(Balanced Tree)

• 二叉树(Binary Tree)

• 二叉查找树(Binary Search Tree)

• 平衡二叉树(AVL Tree)

• 红黑树(Red Black Tree)

• 2-3树(2–3 Tree)

其中，二叉树和二叉查找树是最常用的树。

常见的树代码面试题

• 计算树的高度

• 查找二叉平衡树中第K大的元素

• 查找树中与根节点距离为k的节点

• 查找二叉树中某个节点所有祖先节点