2.17日学习总结

今天对二叉树进行了更深的了解 

二叉树： 

1、定义：

 二叉树是每个节点最多有两个子树的树结构。二叉树是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2、特点：

（1）每个结点最多有两棵子树（二叉树不存咋大于2的结点）。

（2）二叉树的子树有左右顺序之分，其子树的次序不能颠倒。

（3）即使树中的某结点只有一棵子树，也要区分它是左子树还是右子树。

3、基本形态：

（1）空二叉树；

（2）只有一个根结点；

（3）根结点只有左子树；

（4）根结点只有右子树；

（5）根结点既有左子树又有右子树。

4、二叉树的种类：

（1）满二叉树

定义：一个二叉树每个层的结点数都达到了最大值。

【即如果一个二叉树的层数为n，则结点总数是（2^k）-1】

满二叉树是一种特殊的完全二叉树！！

特点：

a.叶子只能出现在最下一层。出现在其他层就不可能达到平衡。

b.非叶子结点的度一定为2。

c.在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

（2）完全二叉树 （效率高）

 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

特点：

a.叶子结点只能出现在最下两层。

b.最下层的叶子一定集中在左部连续位置。

c.倒数第二层，如果有叶子结点，一定都在右部连续位置。

d.如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。

e.同样结点数的二叉树，完全二叉树的深度最小。

（3）斜树：向哪边斜就叫啥斜树！！

左斜树：所有的结点都只有左子树的二叉树。

右斜树：所有的结点都只有右子树的二叉树。

5、二叉树的性质：

（1）若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)  (i>0)个结点。

（2）若规定只有根结点的二叉树的深度为1，则深度为k的二叉树的最大结点数是2^k-1 (k>=1)。

（3）对任何一棵二叉树，如果其叶结点个数为n0，度为2的非叶结点个数为n2，则有n0=n2+1。

（4）具有n个结点的完全二叉树的深度k为[log2n]+1上取整。（[x]表示不大于x的最大整数）

（5）对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有结点从0开始编号，对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2； i=0，i为根结点编号， 无双亲结点。
若2i+1<n，左孩子序号：2i+1，否则无左孩子。
若2i+2<n，右孩子序号：2i+2，否则无右孩子。

 6、二叉树的存储：二叉树的存储结构分为顺序存储和类似于链表的链式存储。

链式存储：

//孩子表示法
 
class Node6 
{
    int val;     //数据域
    Node6 left;  //左孩子的引用，常常代表左孩子为根的整棵左子树
    Node6 right; //右孩子的引用，常常代表右孩子为根的整棵右子树
}
 
//孩子双亲表示法public class Node7 
 
{
    int val;      //数据域
    Node7 left;   //左孩子的引用，常常代表左孩子为根的整棵左子树
    Node7 right;  //右孩子的引用，常常代表右孩子为根的整棵右子树
    Node7 parent; //当前结点的根结点
}

 
题目一：

题目描述
乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料，凭3个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。
 
请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的n瓶饮料，最后他一共能喝到多少瓶饮料。
 
输入格式
一个整数 
n，表示开始购买的饮料数量。（0<n<10000）
 
输出格式
一个整数，表示实际得到的饮料数。
 
输入输出样例
输入
100
输出 
149
 
输入
101
输出 
151

思路：

 这道题的思路非常清晰：实际得到的饮料数量=购买的数量+换购的数量。考虑到两种情况，一种是刚好是3的倍数，全部换完，另一种是不是3的倍数。

AC代码：

#include <iostream>
#include<cmath>
using namespace std;
 
int maxl;
void exchange(int n)
{
    if(n<3)
    {
        return;
    }
    maxl=maxl+n/3;            //n瓶饮料可以换购几瓶
    if(n%3==0)
    {
        n=n/3;               //n正好是3的倍数可以换几瓶
    }
    else
    {
        n=(n/3)+(n%3);       //n瓶换后还剩几瓶没换
    }
    return exchange(n);
}
int main()
{
    int n;
    scanf("%d",&n);
    maxl=n;               //将饮料购买数量初始化
    exchange(n);
    printf("%d",maxl);
    return 0;
}

题目二：

[蓝桥杯 2018 省 AB] 全球变暖
 
题目描述
 
你有一张某海域 N*N 像素的照片，`.` 表示海洋、 `#` 表示陆地，如下所示:
 
.......
.##....
.##....
....##.
..####.
...###.
.......
 
 
其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
 
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。
 
例如上图中的海域未来会变成如下样子：
 
.......
.......
.......
.......
....#..
.......
.......
 
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
 
输入格式
 
第一行包含一个整数N。(1 <= N <= 1000)。
 
以下N行N列代表一张海域照片。
 
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
 
输出格式
 
一个整数表示答案。
 
样例 
样例输入 
 
 
7 
.......
.##....
.##....
....##.
..####.
...###.
.......
 
 
样例输出 
 
1

思路：

本题主要是用搜索，主要思想是到达某个点后就看这个点是否遍历过，如果没有，那么就从这个点开始向四个方向开始遍历，并且把a数组变为1表示遍历过，终止条件是超出边界或者这个点为海域。 

AC代码：

#include <iostream>
#include<string>
 
using namespace std;
 
const int maxl=1005;
int a[maxl][maxl];
string island[maxl];
int n;
int flag=1,sum;
 
void dfs(int x,int y)
{
    if(island[x][y]=='#'&&!a[x][y])
    {
        a[x][y]=1;
    }
    else
        return;
    if(island[x][y+1]=='#'&&island[x][y-1]=='#'&&island[x+1][y]=='#'&&island[x-1][y]=='#')
        flag=1;
    dfs(x,y+1);
    dfs(x,y-1);
    dfs(x+1,y);
    dfs(x-1,y);
 
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;++i)
        cin>>island[i];
    for(i=0;i<n;++i)
    {
        for(j=0;j<n;++j)
        {
            if(island[i][j]=='#'&&a[i][j]==0)
            {
                flag=0;
                dfs(i,j);
                if(!flag)
                {
                    ++sum;
                }
            }
 
        }
 
    }
    printf("%d",sum);
    return 0;
}