前言

在计算机科学的领域中，树与二叉树是极为重要且基础的结构。它们不仅具有理论上的深度与魅力，更在实际应用中发挥着关键作用。理解树与二叉树的概念、特性和操作方法，是掌握众多数据结构与算法的基石。

通过对树与二叉树的深入研究和总结，我们能够更好地洞察数据的组织与管理方式，为解决各种复杂问题提供有力的工具和思路。

树

树的定义

树是一种具有层次结构的数据结构，它由结点组成，有且仅有一个根结点，每个结点可以有零个或多个子结点，除根结点外，子结点与父结点通过边相连，树可以有多个分支，没有子结点的结点为叶子结点。树是n（n>0）个结点的有限集。当n=0时，称作空树。树的根结点没有前驱，除根结点外的所有结点有且仅有一个前驱，树所有的结点可以有零个或多个后继。

任意混淆的地方：

	特性	特性	特性
度为m的树	任意结点的度<=m	至少有一个结点的度=m	一定是非空树，至少有m+1个结点
m叉树	任意结点的度<=m	允许所有结点的度都<m	可以是空树

树的特性

树中的结点数等于所有结点数的度数加1。

解释：结点数 = 所有结点数的度数 + 1；你也可以这样认为：结点数=树的所有边数+1。
2. 度为m的树中第i层上至多有mi−1m^{i-1}mi−1 个结点（i大于等于1）。

解释：依次举例就可以看透规律。
3. 高度为h的m叉树至少有h个结点。

解释：因为高度为h，每一层必须有一个结点。
4. 高度为h的m叉树至多有（mkm^{k}mk-1）/（m-1）个结点。

解释：把每层个数相加，形成一个等比数列求和就可以得到这个式子。
5. 高度为h、度为m的树至少有（h+m-1）个结点。

解释：高度为h：h层中每层都有一个结点；度为m：树中至少有一个结点的度为m；要求至少的结点，我们就可以去除其他结点只保留h个保持高度，在一层中最少要保持有m个结点，因为在有m个结点的那一层中有一个结点是用来保持高度为h的，这样就可以得到h+m-1的式子了。
6. 具有n个结点的m叉树的最小高度为⌈log⁡m(n(m−1)+1)⌉ \lceil\log_m(n(m-1)+1)\rceil⌈logm(n(m−1)+1)⌉。

解释：（==前h-1层有（mh−1m^{h-1}mh−1-1）/（m-1）个结点 < n <= 前h层（mhm^{h}mh-1）/（m-1）)个结点==，我们对这个不等式进行操作，把h变量放在两边得：==h-1 < log⁡m(n(m−1)+1)\log_m(n(m-1)+1)logm(n(m−1)+1) <=h==，最终得出最小高度为⌈log⁡m(n(m−1)+1)⌉ \lceil\log_m(n(m-1)+1)\rceil⌈logm(n(m−1)+1)⌉。

二叉树

二叉树的定义

二叉树是一种重要的数据结构，它是由结点组成的树状结构。每个结点最多有两个子结点，即左子结点和右子结点。二叉树可以是空树，即没有任何结点；也可以由一个根结点以及它的左子树和右子树构成。二叉树的的子树有左右之分，其次序不能任意颠倒。

特殊的二叉树

满二叉树：
- 定义：一颗高度为h，且含有2k−12^{k}-12k−1个结点的二叉树称为满二叉树。
- 特点：对于编号为i的结点
  - 双亲编号为⌊i2⌋\lfloor\frac{i}{2}\rfloor⌊2i⌋。
  - 若有左孩子，则左孩子编号为2*i。
  - 若有右孩子，则右孩子编号为2*i-1。
完全二叉树：
- 定义：高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时称为完全二叉树。
- 特点：
  - 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
  - 若有度为1的结点，则只可能有一个，且该结点只有左结点没有右结点。
  - 按层次编号后，一旦出现某编号为i的结点为叶子节点或只有左孩子，则编号大于i的结点都是叶子结点。
  - 若n（结点数）为奇数，则每个分支结点都有左孩子和右孩子。
  - 若n（结点数）为偶数，则编号最大的分支结点只有左孩子，没有右孩子，其他分支结点左右孩子都有。
二叉排序树：
- 定义：左子树上所有的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一颗二叉排序树。
平衡二叉树：
- 定义：树上任一结点的左子树和右子树的深度之差不超过1。

二叉树的性质

非空二叉树上的叶子结点数等于度为2的结点数加1。

过程：n0为度为0的结点数、n1为度为1的结点数、n2为度为2的结点数、n为总结点数

* n0+n1+n2=n
* n1+2\*n2+1=n (树的特性：结点数 = 所有结点数的度数 + 1) 结合2个等式可得：n2+1=n0

非空二叉树上第k层上至多有2k−12^{k-1}2k−1个结点。
高度为h的二叉树至多有2k−12^{k}-12k−1个结点。
对完全二叉树按从上到下，从左到右的顺序依次编号1，2，……，n，则有一下关系：

* 当i>1时，结点i的双亲的编号为⌊i2⌋\lfloor\frac{i}{2}\rfloor⌊2i⌋，即当i为偶数时，其双亲的编号为i/2，它是双亲的左孩子；当i为奇数时，其双亲的编号为（i-1）/2，它是双亲的右孩子。
* 当2i<=n时，结点i的左孩子编号为2i，否则无左孩子。
* 当2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子。
* 结点i所在层次为⌊log⁡2i⌋+1\lfloor\log\_2 i\rfloor+1⌊log2i⌋+1。

具有n个（n>0）结点的完全二叉树的高度为⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil ⌈log2(n+1)⌉或⌊log⁡2i⌋+1\lfloor\log_2 i\rfloor+1⌊log2i⌋+1。

过程：h为所在高度

* 通过（前h-1层结点数）2h−1−12^{h-1}-12h−1−1<n<=2h−12^{h}-12h−1（前h层结点数），化简可得h-1<log⁡2(n+1)\log\_2(n+1)\\log2(n+1)<=h，因为h为正数可得h=⌈log⁡2(n+1)⌉\lceil\log\_2(n+1)\rceil ⌈log2(n+1)⌉。
* 上式（前h-1层结点数+1）2h−12^{h-1}2h−1<=n<2h2^{h}2h（前h层结点数-1），化简可得h-1<=log⁡2n\log\_2n\\log2n<h，因为h为正数可得h=⌊log⁡2i⌋+1\lfloor\log\_2 i\rfloor+1⌊log2i⌋+1。

对于完全二叉树，可以由结点数n推出度为0，1和2的结点个数为n0、n1和n2。

* 完全二叉树最多只有一个度为1的结点，即n1为0或1。
* 因为n2+1=n0，所以n2+n0 = 2\*n2 +1为奇数。
* 由上面两点可得：当完全二叉树有2k（偶数）个结点，则n1=1 ,n0=k，n2=k-1；当完全二叉树有2k-1（奇数）个结点，则n1=0，n0=k，n2=k-1。

小结

了解了树与二叉树的概念与特性，我们就可以深入了解树的遍历和树的应用等。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有