企业官网建设流程全解析

淘宝内部卷网站建设,企业做国际站哪个网站好,企业网站建设需要多少钱知乎,开发一个婚恋app需要多少钱一、二叉树的核心性质满二叉树的结点数#xff1a;深度为 kkk 的满二叉树#xff0c;其结点总数为 2k−12^k - 12k−1。这是因为每一层的结点数为 2i−12^{i-1}2i−1#xff08;第 iii 层#xff09;#xff0c;从第 1 层到第 kkk 层求和即得#xff1a; ∑i1k2i−12k−1…一、二叉树的核心性质满二叉树的结点数深度为kkk的满二叉树其结点总数为2k−12^k - 12k−1。这是因为每一层的结点数为2i−12^{i-1}2i−1第iii层从第 1 层到第kkk层求和即得∑i1k2i−12k−1 \sum_{i1}^{k} 2^{i-1} 2^k - 1i1∑k​2i−12k−1终端结点与度 2 结点的关系在任意二叉树中设终端结点叶子个数为n0n_0n0​度为 2 的结点个数为n2n_2n2​则有n0n21 n_0 n_2 1n0​n2​1推导依据是总边数等于所有结点出度之和也等于父结点指向孩子的边数。完全二叉树的深度含有nnn个结点的完全二叉树其深度为⌊log⁡2n⌋1 \lfloor \log_2 n \rfloor 1⌊log2​n⌋1因为前k−1k-1k−1层构成满二叉树结构最多包含2k−1−12^{k-1}-12k−1−1个结点。二、二叉树的分类结合图示类型定义说明满二叉树深度为kkk且总节点数为2k−12^k - 12k−1的二叉树每一层都达到最大节点数量。例如深度为 3 的满二叉树有 7 个结点。完全二叉树深度为kkk结点数为nnn且这些结点对应于深度为kkk的满二叉树中编号为 1 到nnn的结点。特点是除最后一层外其余层全满最后一层结点连续靠左排列。非完全二叉树不满足“最后一层结点从左到右连续”的条件如某个内部结点缺少左孩子但存在右孩子或下层结点中间出现空缺如图 3-18© 中 6 号结点左侧无兄弟。三、二叉树的顺序存储结构存储方式使用数组按层次遍历顺序自上而下、自左至右存放结点适用于完全二叉树能高效利用空间并快速计算父子关系。对于编号为iii的结点1≤i≤n1 \leq i \leq n1≤i≤n双亲结点若i1i 1i1其双亲编号为⌊i2⌋\left\lfloor \frac{i}{2} \right\rfloor⌊2i​⌋当i1i 1i1时为根结点无双亲。左孩子结点若2i≤n2i \leq n2i≤n左孩子编号为2i2i2i否则不存在左孩子。右孩子结点若2i1≤n2i1 \leq n2i1≤n右孩子编号为2i12i12i1否则不存在右孩子。注该编号规则基于从 1 开始编号。若编程中使用从 0 开始的数组索引则需调整公式为父节点⌊i−12⌋\left\lfloor \frac{i-1}{2} \right\rfloor⌊2i−1​⌋左孩子2i12i 12i1右孩子2i22i 22i2要证明在任意二叉树中叶子结点终端结点个数 $ n_0 $ 与度为 2 的结点个数 $ n_2 $ 满足关系n0n21 n_0 n_2 1n0​n2​1我们可以通过结点总数和边的总数两个角度进行推导。证明过程设一棵二叉树中有$ n_0 $度为 0 的结点数即叶子结点$ n_1 $度为 1 的结点数只有左孩子或右孩子$ n_2 $度为 2 的结点数有两个孩子则整棵树的总结点数为nn0n1n2(1) n n_0 n_1 n_2 \tag{1}nn0​n1​n2​(1)另一方面从边的数量来看每个结点除根结点外都由一条边连接到其父结点。所以总的边数为$ n - 1 $而这些边也可以通过各结点的出度孩子数来计算度为 1 的结点贡献 1 条边度为 2 的结点贡献 2 条边度为 0 的结点贡献 0 条边。因此总边数也可表示为边数0⋅n01⋅n12⋅n2n12n2 \text{边数} 0 \cdot n_0 1 \cdot n_1 2 \cdot n_2 n_1 2n_2边数0⋅n0​1⋅n1​2⋅n2​n1​2n2​又因为边数等于 $ n - 1 $所以有n12n2n−1(2) n_1 2n_2 n - 1 \tag{2}n1​2n2​n−1(2)将式 (1) 中的 $ n n_0 n_1 n_2 $ 代入式 (2)n12n2(n0n1n2)−1 n_1 2n_2 (n_0 n_1 n_2) - 1n1​2n2​(n0​n1​n2​)−1两边同时减去 $ n_1 $2n2n0n2−1 2n_2 n_0 n_2 - 12n2​n0​n2​−1移项得2n2−n2n0−1⇒n2n0−1 2n_2 - n_2 n_0 - 1 \Rightarrow n_2 n_0 - 12n2​−n2​n0​−1⇒n2​n0​−1即n0n21 n_0 n_2 1n0​n2​1✅ 得证。直观理解这个性质的本质是每一个新增的“分叉”即度为 2 的结点都会增加一个额外的分支路径从而最终导致多出一个叶子。根结点开始是一个叶子单节点树每增加一个度为 2 的结点相当于把一个叶子变成内部结点并生成两个新叶子净增一个叶子。