树的基本概念

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

树是一种特殊的图 (后续文章会提到图).

前缀树 prefix tree (字典树 - trie)

有向树

它的边是有方向的。而树是没有简单回路的连通图。

以结点 v 为出发点的边的数量，我们叫作 v 的出度。而以 v为 终点的边之数量，称为 v 的入度。在上图中，结点 v2​ 的入度是 1，出度是 2。

回路和连通

高度与结点

二叉树

二叉树又分为：完美二叉树，完全二叉树，完满二叉树

完美二叉树(满二叉树)

除了叶子节点之外的每一个节点都有两个子节点,每一层(包括最后一层)都被完全填充

完全二叉树

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐

完满二叉树

所有非叶子结点的度都是2 换句话说：只要你有孩子，你就必然是有两个孩子。

微信公众号

本文链接：