中级天翼
rt
谁有
武建豪在2021-08-02 17:25:58追加了内容
或者递归的也许
新手光能
树的性质、二叉树的定义、二叉树遍历 课后讲义(C2)
一、树
子结点：和父结点相对，一个结点的后继结点。
父结点：和子结点相对，一个结点的前驱结点。
根结点：没有父结点的结点。
叶子结点：没有子结点的结点。
祖先：从根结点到当前结点路径上的所有点（除了自己）。
兄弟：具有同一个父结点的所有结点，互为兄弟结点。
结点的度：一个结点的子结点的数量。
树的度：树中每个结点最多可以拥有的子结点的数量。
结点层次（结点深度）:根结点看成是第1层，子结点的层数是其父结点的层数加1。有的时候结点的深度有可能从0开始。
树的高度（树的深度）：树中所有结点的层次的最大值。
堂兄弟：属于同一个层次的所有结点，父结点不同，互为堂兄弟。
子树：以树中某一结点为根结点的所有子结点构成的树。空树是任意树的子树。
空树：没有结点的树。
森林：多个不同的树在一起共同构成森林。
注：树的定义同样可以用于二叉树。
二、二叉树
树型数据结构中，最常用的是二叉树。
树是由结点和结点之间相连的边组成的数据结构。二叉树是对于每个结点，最多有两个子结点。左边的结点叫做左孩子，右边的结点叫做右孩子。以左孩子为根结点的子树叫做原树的左子树，以右孩子为根结点的子树叫做原树的右子树。
除了根节点之外，每个结点都有且只有一个父结点。
递归定义
- 空结点，单个结点是一个二叉树
- 二叉树的左右子树也是一个二叉树
二叉树的5种形态
- 空二叉树（一个结点都没有）
- 只有根结点的二叉树
- 只有左子树的二叉树
- 只有右子树的二叉树
- 左右子树均不为空的二叉树
性质
性质1
二叉树的第i层最多有2^{i-1}2i−1个结点
根结点定义为第1层，一个结点的子结点的层数加1
性质2
二叉树的前i层最多共有2^i-12i−1个结点
深度（二叉树的最大层数）为i的二叉树最多共有2^i-12i−1个结点
证：2^0+2^1+2^2+...+2^{i-1}=2^i-120+21+22+...+2i−1=2i−1
性质3
-
结点的度：一个结点的子结点的数量
如果一个二叉树，共有n个结点，度为0的结点（叶子结点）数量是n_0n0，度为1的结点数量是n_1n1，度为2的结点数量是n_2n2。
n_0=n_2+1n0=n2+1
证：① 根据数量：n=n_0+n_1+n_2n=n0+n1+n2
②根据孩子结点数量：n=n_1+2n_2+1n=n1+2n2+1 -
树的度：树中所有结点的度的最大值
满二叉树
如果一个二叉树，每层结点数都是这层的最大值，这个树就是一个满二叉树。
完全二叉树
如果一个二叉树从上往下，每层从左往右，依次编号为，1、2、3、……。如果每个结点的编号和满二叉树中对应位置的结点的编号完全一样，那么这个树是一个完全二叉树。
如果一个二叉树，除了最后一层以外，是一个满二叉树。最后一层结点是从最左边往右依次长满。是一个完全二叉树。
性质4
n个结点的完全二叉树的深度是\lfloor{log_2n}\rfloor+1⌊log2n⌋+1
性质5
对于一个n个结点的完全二叉树，从上往下，从左往右依次编号为1到n。
对于任意一个结点i，如果其有左孩子，则左孩子编号是2*i2∗i
对于任意一个结点i，如果其有右孩子，则右孩子编号是2*i+12∗i+1
对于任意一个结点i，如果其有父结点，则父结点编号是i/2i/2
对于完全二叉树，可以使用数组存储。
三、树的基本性质NOIP初赛真题
-
2018NOIP普及 根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ A ）个结点。
A (kh+1 - 1)/(k - 1)
B k h-1
C kh
D (k h-1) / (k - 1) -
NOIP2017普及 设G是有n个结点、m条边(n≤m)的连通图，必须删去G的( A )条边,才能使得G变成一棵树。
A m - n + 1
B m - n
C m + n + 1
D n - m + 1 -
NOIP2016普及 约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有_____个叶子结点；一棵结点数为2016的二叉树最小的高度值是___________。（1 11）
-
NOIP2015普及 如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ B ）。
A 5
B 6
C 7
D 8 -
NOIP2015普及 —棵结点数为 2015 的二叉树最多有_____个叶子结点。（1008）
-
NOIP2014普及 一棵具有5层的满二叉树中结点数为( A )。
A 31
B 32
C 33
D 16 -
NOIP2013普及 已知一棵二叉树有10 个节点，则其中至多有（ A ）个节点有 2 个子节点。
A 4
B 5
C 6
D 7 -
NOIP2011普及 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ B ）。
A 10
B 11
C 12
D 13 -
NOIP2010普及 如果树根算第1层，那么一棵n层的二叉树最多有（ A ）个结点
A 2n-1
B 2n
C 2n+1
D 2n+1
四、二叉树的遍历
如图所示：
先序遍历：根-左子树-右子树
中序遍历：左子树-根-右子树
后序遍历：左子树-右子树-根
按照上述三种遍历方式：
先序遍历：ABDECFG
中序遍历：DBEAFCG
后序遍历：DEBFGCA
如果已知先序遍历、中序遍历，求后序遍历
先序遍历可以确定根结点，再根据根结点，在中序遍历中确定对于当前根结点的左子树和右子树，递归求解还原二叉树。
根据后序遍历的特点：左子树-右子树-根
对于当前树的根 是最后输出
先递归求左子树，再递归求右子树，最后递归 输出根
不能通过先序遍历+后序遍历 确定唯一的二叉树
五、树的遍历NOIP初赛真题
- 2015NOIP普及 前序遍历序列与中序遍历序列相同的二叉树为（ D ）。
A 根结点无左子树的二叉树
B 根结点无右子树的二叉树
C 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D 只有根结点的二叉树或非叶子结点只有右子树的二叉树 - 2013NOIP普及 二叉树的（ A ）第一个访问的节点是根节点。
A 先序遍历
B 中序遍历
C 后序遍历
D 以上都是 - 2012NOIP普及 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ C ）。
A ABC
B CBA
C ACB
D BAC - 2010NOIP普及 一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ A ）。
A 2
B 3
C 4
D 5 - 2019NOIP普及 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，其前序遍历序列为（ B ）。
A ABCDEFGHIJ
B ABDEGHJCFI
C ABDEGHJCFI
D ABDEGHJFIC
缔造者之神
我只有冲刺班树的纸质讲义，怎么办？
在网上搜也可以：https://www.csdn.net/tags/MtjakgzsMDAtZG93bmxvYWQO0O0O.html
缔造者之神
getline(cin,s);
for(int i=0;i<s.size();i++)
{
if(s[i]>='a'&&s[i]<='y') s[i]++;
else if(s[i]=='z') s[i]-=25;
}
cout<<s;注意：是else if，不是if，否则y会变成a
缔造者之神
是的，没有空格就不要费神了
另外，你再编几组样例试试
重点测试数字，大写字母是否变化，小写字母y,z,a是否转化正常
缔造者之神
long long sum=0,m,n,d,cnt=0;
cin>>m>>n>>d;
while(sum<m)
{
sum+=n;
n+=d;
cnt++;
}
cout<<cnt;应该没错，自己顺便可以测试一下（我也不知道对不对）
