二叉树一、定义二叉树是nn≥0个结点的有限集合满足可以为空空二叉树n0n0n0非空时由根结点、左子树、右子树三部分组成每个结点最多只有2棵子树分左子树、右子树左右不能颠倒有序树。重点区分普通树子树不分顺序二叉树的子树严格区分左、右。二、基本术语结点存储数据指向子结点的指针。根结点二叉树最顶层结点没有前驱。父结点双亲拥有子结点的结点。子结点孩子一个结点的左、右后继结点分左孩子、右孩子。叶子结点终端结点没有孩子的结点左右子树都为空。分支结点非终端结点至少有一个孩子的结点。度结点拥有子结点的个数。二叉树结点的度只能是0、1、2。层次根在第1层根的孩子第2层依次往下。深度高度深度从根到该结点经过的层数树的深度 最大层次。高度从该结点往下到最远叶子的层数树高等于树深度。路径从一个结点到另一个结点之间的结点序列。满二叉树每层结点数都达到最大值。深度kkk结点总数2k−12^k-12k−1。完全二叉树除最后一层外其余各层全部满最后一层结点靠左连续排列。满二叉树是特殊的完全二叉树。三、二叉树性质考试高频设nnn结点总数n0n_0n0​叶子数n1n_1n1​度为1结点n2n_2n2​度为2结点树深度hhh。性质1在二叉树中n0n21n_0 n_2 1n0​n2​1叶子结点数量 度为2的结点数量 1最常考性质2二叉树第iii层最多有2i−1\boldsymbol{2^{i-1}}2i−1个结点i≥1i\ge1i≥1性质3深度为hhh的二叉树最多结点总数2h−1\boldsymbol{2^h -1}2h−1满二叉树性质4有nnn个结点的二叉树最小深度⌊log⁡2n⌋1\lfloor \log_2n \rfloor1⌊log2​n⌋1✅ 完全二叉树专属性质nnn个结点的完全二叉树深度h⌊log⁡2n⌋1h\lfloor \log_2n \rfloor1h⌊log2​n⌋1对完全二叉树按层序编号根为1号结点iii的左孩子2i2i2i结点iii的右孩子2i12i12i1结点iii的双亲⌊i/2⌋\lfloor i/2 \rfloor⌊i/2⌋注意编号从0开始时公式会变化考试默认从1编号。nnn个结点的完全二叉树如果nnn为偶数叶子数n0n/2n_0n/2n0​n/2如果nnn为奇数叶子数n0(n1)/2n_0(n1)/2n0​(n1)/2完全二叉树度为1的结点n1n_1n1​只能是0或1。一句话速记二叉树是有序树结点最多两个孩子叶子永远比二度结点多1满二叉层层铺满完全二叉最后一层结点靠左挤。