1 树的基本性质

性质 1 ：树中的节点数等于所有节点度数加 1

每个节点的度数分别对应节点的子节点，设所有节点的度数为 d，总结点数为n，则 n = d + 根节点，即 n = d + 1。
设总结点数为n，树中除根节点外，每个节点都对应一个分支，因此 树中总分支数为 n - 1。

性质 2 ：度为 m 的树中第 i 层至多有 $m^{i-1}$mi−1个节点（$i\geq 1$i≥1)

使用归纳法证明：

1. 第一层，即 i = 1。至多有 $m^0 = 1$m0=1 个节点
2. 设第 i - 1层至多有 $m^{i-2}$mi−2 个节点
3. 则第 i 层，由于节点的度为 m ，则节点数为$m^{i-2} * m = m^{i-1}$mi−2∗m=mi−1

性质 3： 高度为 h 的 m 叉树至多有 $\frac{m^{h}-1}{m-1}$m−1mh−1​个节点

节点数最多，则每层都有$m^{i-1}$mi−1个节点（$i\geq 1$i≥1)。则总结点数 $n=m^0 + m^1 + m^2 + \cdots +m^{h-1}$n=m0+m1+m2+⋯+mh−1，用等比数列求和公式可得 $n=\frac{m^{h}-1}{m-1}$n=m−1mh−1​

性质 4 ：具有 n 个节点的 m 叉树的最小高度为 $\lceil log_m (n*(m-1)+1) \rceil$⌈logm​(n∗(m−1)+1)⌉ (对数意义）

高度最小，则每个节点的度都为 m，即每层都有最多节点。由性质 3 得：$n=\frac{m^h-1}{m-1}$n=m−1mh−1​，整理可得：$m^h-1=n*(m-1)\Longrightarrow h=log_m (n*(m-1)+1)$mh−1=n∗(m−1)⟹h=logm​(n∗(m−1)+1)。
由于多余节点也是一层，所以需要向上取整，所以 $h=\lceil log_m (n*(m-1)+1) \rceil$h=⌈logm​(n∗(m−1)+1)⌉

性质 5 ：满m叉树节点编号为 i 的第 k 个孩子节点编号为$(i-1)*m+k+1（1\leq k\leq m)$(i−1)∗m+k+1（1≤k≤m)

设节点 i 为该 m 叉树的第 h 层（h=1，2，3…)，
则前 h-1 层层共有$N_1=\frac{m^{h-1}-1}{m-1}$N1​=m−1mh−1−1​（树的基本性质3）个节点，
则 前 h 层共有$N_2=\frac{m^h-1}{m-1}$N2​=m−1mh−1​（树的基本性质3）个节点，
显然，i 为第 h 层的第 $i-N_1$i−N1​个节点，
$\Longrightarrow$⟹ i 有$i-N_1-1$i−N1​−1个左兄弟，
$\Longrightarrow$⟹节点 i 的第一个孩子 j 有$(i-N_1-1)*m$(i−N1​−1)∗m个左兄弟，
$\Longrightarrow$⟹节点 i 的第一个孩子 j 在第 h+1 层的次序为$(i-N_1-1)*m+1$(i−N1​−1)∗m+1，
$\Longrightarrow$⟹节点 i 的第一个孩子 j 在树中的编号为$N_2+(i-N_1-1)*m+1$N2​+(i−N1​−1)∗m+1
$\begin{cases} N_2=\frac{m^h-1}{m-1} \\ j = N_2+(i-N_1-1)*m+1 \end{cases}${N2​=m−1mh−1​j=N2​+(i−N1​−1)∗m+1​

$\Longrightarrow 节点 i 的第一个孩子 j=(i-1)*m+2$⟹节点i的第一个孩子j=(i−1)∗m+2。
又 树为m叉树，
$\Longrightarrow 节点 i 的最后一个孩子 j=(i-1)*m+2+m-1=(i-1)*m+m+1$⟹节点i的最后一个孩子j=(i−1)∗m+2+m−1=(i−1)∗m+m+1
$\Longrightarrow$⟹ 编号为 i 的节点的孩子节点编号$(i-1)*m+k+1（1\leq k\leq m)$(i−1)∗m+k+1（1≤k≤m)

性质 6 ：满m叉树孩子节点编号为 j 的双亲节点编号$i=\lfloor(j-2)/m \rfloor +1$i=⌊(j−2)/m⌋+1

由树的基本性质5，节点 i 的第一个孩子 $j=(i-1)*m+2$j=(i−1)∗m+2
$\Longrightarrow i=\lfloor(j-2)/m \rfloor +1$⟹i=⌊(j−2)/m⌋+1

2 二叉树的基本性质

性质 1 ：非空二叉树的叶子节点数等于度为 2 的节点数加1 ，即$n_0=n_2+1$n0​=n2​+1

设度为0、1、2的节点个数为$n_0,n_1,n_2$n0​,n1​,n2​，则节点总数$n=n_0+n_1+n_2$n=n0​+n1​+n2​。
设B为分支总数，则 $n=B+1$n=B+1，由于这些分支是度为1和度为2的节点射出的，所以$B=n_1+2n_2$B=n1​+2n2​
$\begin{cases} n=n_0+n_1+n_2 \\ n=B+1 \\ B=n_1+2n_2 \\ \end{cases}$⎩⎪⎨⎪⎧​n=n0​+n1​+n2​n=B+1B=n1​+2n2​​
$\Longrightarrow n_0=n_2+1$⟹n0​=n2​+1

性质 2 ：非空二叉树第 k 层至多有$2^{k-1}$2k−1个节点（$k\geq 1$k≥1)

由树的基本性质2，取树的度m=2

性质 3 ：高度为 h 的二叉树至多有 $2^h-1$2h−1个节点（$h\geq 1$h≥1)

由树的基本性质3，取树的度m=2

性质 4 ：完全二叉树的性质（完全二叉树的定义）

1. $i > 1$i>1时，节点 $i$i 的双亲编号为$\lfloor i/2 \rfloor$⌊i/2⌋。
   即：
   若 $i$i 为偶数，双亲编号为$i/2$i/2 ；
   若 $i$i 为奇数，双亲编号为$(i-1)/2$(i−1)/2 。
2. $2i \leq n$2i≤n时，节点 $i$i 的左孩子编号为 $2i$2i ，否则无左孩子
3. $2i+1 \leq n$2i+1≤n时，节点 $i$i 的右孩子编号为 $2i+1$2i+1 ，否则无右孩子
4. 节点 $i$i 的层次深度为$\lfloor log_2i \rfloor + 1$⌊log2​i⌋+1（证明：下述性质5）

性质 5 ：具有n个节点的完全二叉树的高度为$\lfloor log_2n \rfloor + 1$⌊log2​n⌋+1或$\lceil log_2 (n+1) \rceil$⌈log2​(n+1)⌉

证明1：

由二叉树性质3和完全二叉树的定义有
$2^{h-1}-1\lt n\leq 2^{h}-1 或 2^{h-1}\leq n\lt 2^{h}$2h−1−1<n≤2h−1或2h−1≤n<2h
解得：$h= \lfloor log_2n \rfloor + 1或h= \lceil log_2 (n+1)\rceil$h=⌊log2​n⌋+1或h=⌈log2​(n+1)⌉

证明2：

由二叉树性质3得，$n=2^{h}-1 （h\geq 1)$n=2h−1（h≥1)

$\Longrightarrow n+1=2^{h} \Longrightarrow h=log_2(n+1) \Longrightarrow h= \lceil log_2 (n+1)\rceil$⟹n+1=2h⟹h=log2​(n+1)⟹h=⌈log2​(n+1)⌉

---

对数

对数是由数学家约翰·纳皮尔（1550-1617）发明。在中学数学中，我们先是学习了指数，比如$2^3=8$23=8。然后，我们才学习了指数的逆运算——对数，比如求出2的多少次方才会等于8，我们可以用对数来表示这个数，即$log_2(8)$log2​(8)，其结果就是$log_2(8)=3$log2​(8)=3。我们用更一般的表达式来表示指数函数$y=a^x$y=ax，写成对数形式$x=log_a(y)$x=loga​(y)（这里需要满足a>0，且a≠1）。因此，指数和对数互为逆运算。

然而，在历史上，对数函数其实先出现，后来才出现指数函数。这是因为对数发明的初衷并不是用于求解指数的幂，而是用于求解多个数的连乘之积。当时，随着科学技术的发展，人们在计算过程中所用到的数字随之越来越大。由于没有计算器的帮助，想要算出几个很大数字的乘积，往往需要耗费大量的时间。对数的出现大大减少了计算乘积所需的工作量，这得益于对数的独特性质：$log_a(bc)=log_a(b)+log_a(c)，log_a(b)=log_c(b)/log_c(a)，log_a(b^c)=clog_a(b)$loga​(bc)=loga​(b)+loga​(c)，loga​(b)=logc​(b)/logc​(a)，loga​(bc)=cloga​(b)等等。只要通过查对数表，就能很快计算出一些较为繁琐的运算。例如，我们想要计算567.89和3141.59的乘积。假设：

$x=567.89×3141.59$x=567.89×3141.59

两边同时取以10为底的对数，得到：

$log_{10}(x)=log_{10}(567.89×3141.59)=log_{10}(567.89)+log_{10}(3141.59)$log10​(x)=log10​(567.89×3141.59)=log10​(567.89)+log10​(3141.59)

$log_{10}(x)=log_{10}(10^2×5.6789)+log_{10}(10^3×3.14159)$log10​(x)=log10​(102×5.6789)+log10​(103×3.14159)

$log_{10}(x)=2+log_{10}(5.6789)+3+log_{10}(3.14159)=5+log_{10}(5.6789)+log_{10}(3.14159)$log10​(x)=2+log10​(5.6789)+3+log10​(3.14159)=5+log10​(5.6789)+log10​(3.14159)

其中$log_{10}(5.6789)$log10​(5.6789)和$log_{10}(3.14159)$log10​(3.14159)可以在对数表中查出，把它们相加之后，再查反对数就能得到最终结果。在没有电子计算器的时代，通过对数计算一些繁琐的运算可以大大减轻计算量。

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。