文章目录前言1. 树的定义2. 树的相关概念2.1 结点间的关系描述2.2 结点和树之间的属性描述3. 树的性质3.1 性质一树中的结点数 所有结点的度数之和 13.2 性质二m 叉树中第 i 层上至多有m i − 1 m^{i-1}mi−1个结点i ≥ 13.3 性质三高度为 h 的 m 叉树至多有m h − 1 m − 1 \frac{m^h - 1}{m - 1}m−1mh−1​个结点4. 二叉树的定义5. 几个特殊的二叉树5.1 满二叉树5.2 完全二叉树5.3 搜索二叉树6. 二叉树的性质6.1 性质一在二叉树的第 i 层上至多有 2^(i-1) 个结点i ≥ 16.2 性质二高度为 h 的二叉树至多有 2^h - 1 个结点h ≥ 16.3 性质三对任何一棵二叉树 T如果其度为 0叶子结点数为 n0度为 2 的结点数为 n2则 n0 n2 16.4 性质四具有 n 个结点的完全二叉树的高度为 ⌊log2 n⌋ 1前言树Tree是数据结构中非常重要且基础的一类非线性结构。与线性结构如数组、链表、栈、队列不同树结构中的数据元素之间存在明显的层次关系例如现实生活中的家族谱系、公司组织架构、计算机中的文件系统以及编译原理中的语法分析树都可以用树这种结构来抽象和描述。本文将从树的定义出发系统梳理树的相关概念如度、叶子结点、路径、高度等再介绍树的重要性质并进一步聚焦到最常用、最基础的二叉树讲解二叉树的定义、几种特殊形态满二叉树、完全二叉树、搜索二叉树以及二叉树的核心性质。1. 树的定义树Tree是 nn ≥ 0个结点的有限集。当 n 0 时称为空树当 n 0 时称为非空树。任意一棵非空树应该满足以下要求a. 有且仅有一个特定的称为根的结点。b. 当 n 1 时其余结点可分为 mm 0个互不相交的有限集 T1T2…Tm其中每个集合本身又是一棵树并且称为根的子树。树的根结点没有前驱结点除根结点外的所有结点有且只有一个前驱结点树中的所有结点可以有多个后继结点。树Tree这个概念来源于现实世界中常见的树都是从根开始生长再长出很多子树。树是一种递归定义的数据结构树可以分成根和多棵子树每棵子树又可以分为根和多棵子树。2. 树的相关概念2.1 结点间的关系描述祖先从根结点到该结点所经分支上的所有结点称为该结点的祖先。如A 到 G 分支中A 和 C 都是 G 的祖先。子孙以某结点为根的子树中任一结点都称为该结点的子孙。如下面的所有结点都是 A 的子孙C 的子孙只有 G。孩子/双亲结点所有子树的根结点称为该结点的孩子相对应该结点称为孩子的双亲。如B 的孩子是 E 和 FE 和 F 的双亲是 B。兄弟同一个双亲的孩子之间互称为兄弟。如H 和 I 是兄弟结点这里兄弟类似人类亲缘关系的亲兄弟。堂兄弟双亲在同一层的结点互为堂兄弟。如G 和 H 是堂兄弟关系。2.2 结点和树之间的属性描述3. 树的性质3.1 性质一树中的结点数 所有结点的度数之和 1这个点很好理解一个结点的度就是这个结点有几个孩子结点所有的度相加就是累计的孩子结点数只有根结点没算进去所以所有结点的度之和 1 就是结点数。有些地方也会说树中的结点数 所有边之和 1因为一个结点连接出去的边等于这个结点的度。3.2 性质二m 叉树中第 i 层上至多有m i − 1 m^{i-1}mi−1个结点i ≥ 1m 叉树是指每个结点最多 m 个孩子最少可以是 0 个孩子m 叉树中不一定存在 m 个孩子的结点。极端场景下高度为 h 的 m 叉树叶子结点都在第 h 层每个分支结点均有 m 个孩子每层都是满的假设层数是 i则每层结点数为m i − 1 m^{i-1}mi−1第 1 至 h 层的结点数是一个以 m 为公比的等比数列。3.3 性质三高度为 h 的 m 叉树至多有m h − 1 m − 1 \frac{m^h - 1}{m - 1}m−1mh−1​个结点极端场景下高度为 h 的 m 叉树叶子结点均在第 h 层每个分支结点均有 m 个孩子每层都是结点数达到最大满假设层数是 i则每层结点数为m i − 1 m^{i-1}mi−1第 1 至 h 层的结点数是一个以 m 为公比的等比数列。等比数列前 n 项和S n a 1 ⋅ 1 − q n 1 − q S_n a_1 \cdot \frac{1 - q^n}{1 - q}Sn​a1​⋅1−q1−qn​其中a 1 a_1a1​为首项q qq为公比n nn是项数。高度为 h 的 m 叉树最多结点数为S_h (m^h - 1) / (m - 1)。4. 二叉树的定义二叉树Binary Tree是另一种树型结构它的特点是每个结点至多只有两棵子树即二叉树中不存在度大于 2 的结点并且二叉树的子树有左右之分其次序不能任意颠倒二叉树是有序树左边的叫左子树右边的叫右子树。二叉树的度并不一定为 2它要求每个结点度最大为 2特殊情况下树的度也可能为 0 或者 1。二叉树也是一个递归定义的数据结构任何一棵二叉树可以分为根和左右子树非空的左右子树又可以分为根和左右子树。5. 几个特殊的二叉树5.1 满二叉树一棵高度为 h 的二叉树每层结点数都达到最大满合计有 2^h - 1 个结点的二叉树就叫满二叉树。满二叉树的叶子结点都在最后一层且分支结点的度均为 2。满二叉树是当前高度下二叉树结点数最大的形态。等比数列前 n 项和S_n a1 * (1 - q^n) / (1 - q)其中 a1 为首项q 为公比n 是项数。高度为 h 的满二叉树的合计结点S_n 2^0 2^1 2^2 … 2^(h-1) 2^h - 1。5.2 完全二叉树一棵高度为 h 的完全二叉树前 h-1 层都是结点数达到最大满第 h 层不一定满但是要求从左到右结点是连续的。满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。高度为 h 的完全二叉树的结点数量在 [2^(h-1), 2^h - 1] 之间。完全二叉树的叶子一定只出现在最后两层且度为 1 的结点最多有 1 个剩下的结点都是度为 0 和度为 2。5.3 搜索二叉树二叉搜索树又称二叉排序树它走中序遍历是有序的它或者是一棵空树或者是具有以下性质的二叉树若它的左子树不为空则左子树上所有结点的值都小于根结点的值实践中可变形为左子树上所有结点的值都小于等于根结点的值。若它的右子树不为空则右子树上所有结点的值都大于根结点的值实践中可变形为右子树上所有结点的值都大于等于根结点的值。它的左右子树也分别为二叉搜索树。6. 二叉树的性质6.1 性质一在二叉树的第 i 层上至多有 2^(i-1) 个结点i ≥ 1这个性质是前面「m 叉树中第 i 层上至多有 m^(i-1) 个结点」在 m 2 时的特例。二叉树每个结点最多有 2 个孩子极端情况下每层都达到最大结点数则第 i 层上至多有 2^(i-1) 个结点。6.2 性质二高度为 h 的二叉树至多有 2^h - 1 个结点h ≥ 1同理这是「高度为 h 的 m 叉树至多有 (m^h - 1) / (m - 1) 个结点」在 m 2 时的特例。当每层结点数都达到最大即满二叉树时高度为 h 的二叉树结点总数最多为 2^h - 1 个。6.3 性质三对任何一棵二叉树 T如果其度为 0叶子结点数为 n0度为 2 的结点数为 n2则 n0 n2 1前面树的性质讲到树中的结点数 所有结点的度数之和 1。假设树中结点总数为 m度为 1 的结点数为 n1则m n1 2 n2 1假设树中结点总数为 m则 m n0 n1 n2化解一下可以推导出 n0 n2 1就是这个性质的结论。6.4 性质四具有 n 个结点的完全二叉树的高度为 ⌊log2 n⌋ 1⌊X⌋ 表示对 X 向下取整。完全二叉树小节我们讲到高度为 h 的完全二叉树的结点数量在 [2^(h-1), 2^h - 1] 之间我们尝试把这个不等式调整一下变成 2^(h-1) ≤ n 2^h则 h - 1 ≤ log2 n h因为 h 是整数所以 h ⌊log2 n⌋ 1。