【数据结构】树、二叉树总结（一）

知识结构

树的基本概念和定义

树的性质（重要）

1. 树中的节点树等于所有节点的度树加1

• 总度数等于根节点的所有子节点，当n=3，则度为2
• 总结点数等于度加1

2. 度为m的树第i层最多有 $m^{i-1}$mi−1 个节点
把树每层看做等比数列, 每一层看作一项, 则第1到第i层分别为: $a_1, a_2 \dots a_i$a1​,a2​…ai​ ;度即为等比梳理的公比q=m, 首项为 $a_1$a1​=1(一棵树只有一个根节点);

$\because$∵ 等比通项公式: $a_n = a_1*q^{(n-1)}$an​=a1​∗q(n−1)

$\therefore$∴ 由上式得 $a_i = 1 * m^{(i-1)} \Rightarrow a_i=m^{(i-1)}$ai​=1∗m(i−1)⇒ai​=m(i−1),

即第i层的节点数等于 $m^{(i-i)}$m(i−i)

3. 高度为h的m叉树, 最多有 $\frac{m^h-1}{m-1}$m−1mh−1​ 个节点
仍把数的每层看作等比数列, 可得到: $a_1 = 1 ,q=m , n=h$a1​=1,q=m,n=h

$\because S_n=\frac{a_1*(1-q^n)}{(1-q)} \ (q\neq 1)$∵Sn​=(1−q)a1​∗(1−qn)​ (q​=1)

$\therefore S_i =\frac{1*(1-m^h)}{1-m} =\frac{-(m^h-1)}{-(m-1)} \Rightarrow \frac{m^h-1}{m-1}$∴Si​=1−m1∗(1−mh)​=−(m−1)−(mh−1)​⇒m−1mh−1​

4. 具有n个节点的m叉树, 最小高度为 $\log_{m}(n(m-1)+1)$logm​(n(m−1)+1) 向上取整.

二叉树

特点：

• 至多由两个子节点
• 两个节点有左右之分
• 节点可以为空
  

满二叉树

• 除叶子节点外每个节点都有两个子节点
• 只有最后一次有叶子节点，h-1全是父节点
• 高度为h的满二叉树共有 $2^{h}-1$2h−1个节点
• 第i层共有 $2^{h-1}$2h−1个节点
• 满二叉树的节点为奇数个, 去掉根为偶数个

完全二叉树

• 有n(n>2)层的完全二叉树, 叶节点在n和n-1层
• 按照层序编号, 当 $i\leq\lfloor\frac{n}{2}\rfloor$i≤⌊2n​⌋时, i为双亲(父)节点, 否则为叶子节点
• 完全二叉树的节点树可能为奇树或偶数, 为奇数时最后一个双亲节点无左孩子; 为偶数时有左孩子.(可看上图加以理解)
• $i\leq n-1$i≤n−1时, 第i层共有 $2^{h-1}$2h−1个节点

二叉树性质(重要)

1. 非空二叉树的叶子节点数等于度为2的节点数加1, 即 $n_0 = n_2+1$n0​=n2​+1
2. 非空二叉树第i层最多有 $2^{i-1}$2i−1个节点, $(i\geq1)$(i≥1).
3. 高度为h的二叉树最多有 $2^h-1$2h−1个节点(此时为满二叉树), $h\geq1$h≥1.
4. 对二叉树进行层序编号

• 当i>1, 双亲编号为 $\lfloor \frac{i}{2} \rfloor$⌊2i​⌋, i为偶数无须向下取整
• 当 $2i\leq n$2i≤n, 节点左孩子编号为2i, 否则无左孩子.
• 当 $2i+1\leq n$2i+1≤n, 节点右孩子编号为2i+1, 否则无右孩子
• 节点i所在层次或深度为 $\lfloor \log_2i \rfloor+1$⌊log2​i⌋+1

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