$\large前沿：核心考点 （ 抓主要矛盾）$

树

树是一种递归的数据结构

属性: (默认从1开始) 结点的层次（深度）—―从上往下数 结点的高度――从下往上数 树的高度（深度）――总共多少层

结点的度――有几个孩子（分支) 树的度――各结点的度的最大值

==常见考点1:结点数=总度数+1==

==常见考点2:度为m的树、m叉树的区别==

==常见考点3:度为m的树第i层至多有$m^{i-1}$个结点(i≥1)== , ==m叉树第i层至多有$m^{i-1}$个结点（i≥1)==

==常见考点4:高度为h的m叉树至多有 $\frac{m^h-1}{m-1}$ 个结点。==

==常见考点5:高度为h的m叉树至少有h个结点，高度为h、度为m的树至少有h+m-1个结点。==

==常见考点6:具有n个结点的m叉树的最小高度为$\lceil \log_m(n(m - 1)+1)\rceil$==

等比数列求和公式:$a + aq + aq^2+…+aq^{n-1}= \frac{a_1(1-q^{n项})}{1-q}$

二叉树

二叉树是n (n≥0）个结点的有限集合: ①或者为空二叉树，即n = 0。 ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

特点: ①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树) 注意区别:(度为2的有序树)

【性质重点】

$满二叉树节点数量2^n-1,仅最后一层有叶子节点 \ 完全二叉树按顺序编号：性质2重要，最多只有一个度为1的节点$

二叉排序树

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树: 左子树上所有结点的关键字均小于根结点的关键字; (左 < 根 < 右) 右子树上所有结点的关键字均大于根结点的关键字。 左子树和右子树又各是一棵二叉排序树。（递归）

二叉树的性质: 树的结点数=总度数+1 ⇒叶子结点数=二分支结点数+1