树与二叉树
树的计算公式：
树的性质：
性质1：树中的结点树等于所有结点的度数之和加1。
性质2：度为m的树中第i层最多有个结点(i>=1)。
性质3：高度为h的m次数最多有个结点。
性质4：具有n个结点的m次树的最小高度为[]（m为底。
树的总节点数：
1.每层节点数之和：
Sn=N1+N2+N3+···+NK（K代表第K层的节点数）
2.所有不同度数的节点数之和：
Sn=N0+N1+N2+···+NM（M代表度为M的节点数）
3.所有节点度数和+1：
Sn=N0×0+N1×1+N2×2+···+NM×M+1（NM表示度为M的节点数）
二叉树的公式：
满二叉树：每层结点均满，每层均具有最大结点数
1.深度为H的满二叉树：总结点数N=2H-1
2.深度为H的满二叉树：叶子节点数N0=2H-1
3.K层上的结点数：2K-1
注意：满二叉树的各值都是二叉树的最大值MAX。
完全二叉树：只有度为0和度为2的节点，从右侧缺失
1.完全二叉树总节点个数N：N=N0+N2
2.叶子结点数N0：N0=N2+1
3.具有N个节点的完全二叉树深度为：[log2N]+1
例1：总节点数N=845，叶子结点数N0=45,求度为1的节点数N1：
①根据公式得出N2=44
| 0 | 1 | 2 |
|---|---|---|
| 45 | X | 44 |
②根据总结点数公式得：45+X+44=845 ==》 X=756
例2：深度H=7，叶子结点数N0=64，求求度为1的节点数N1：
| 0 | 1 | 2 |
|---|---|---|
| 64 | X | 63 |
①根据公式得出：45+X+44最多等于27-1=127
此处是特殊情况：X恰好为0.
例3：完全二叉树，深度H=7，总结点数N=125，求叶子结点数N0=？
①假设满二叉树的情况下总结点数N=27-1=128-1=127，比现有的125总结点数多2.
②假设满二叉树的情况下叶子节点数N0=27-1=64
需要注意的是：完全二叉树少的两个叶子结点全是从最右边缺少的，所以缺失两个叶子结点让一个父结点裸露为叶子结点，故而叶子节点数为64-2+1=63个。
例3：完全二叉树，深度H=5，总结点数不可能为：A
A.15 B.16 C.17 D.18
NMAX=25-1=31 这是节点数的最大值
5层的最多结点数25-1=16
31-16+1=16这是结点数的最小值
不重要：具有N个节点的完全二叉树，某节点序号为I，则其双亲节点的序号为[I/2],其左孩子为2I（2I≤N，否则无左孩子）右孩子为2I+1（2I+1≤N，否则无右孩子）文章来源：https://www.toymoban.com/news/detail-727738.html
二叉树的遍历：
修改：后序遍历错误
文章来源地址https://www.toymoban.com/news/detail-727738.html
到了这里，关于计算机二级：树与二叉树速记公式及特殊例题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构] 树与二叉树](https://imgs.yssmx.com/Uploads/2024/03/837706-1.png)
