今天一天都在刷题，在刷题的过程中也学到了一些二叉树的知识，简单的二叉树题目还是会做了。下午又看了一遍大话数据结构关于二叉树的讲解，几乎没有新的收获，能看懂，但是书中的代码不会用，不过写题时没用到。对我来说做题比看书看资料的收获要大得多。
二叉树深度
题目描述
给出每个节点的两个儿子节点，建立一棵二叉树（根节点为 11），如果是叶子节点，则输入0 0。建好树后希望知道这棵二叉树的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。
最多有 10^6106 个结点。
输入格式
无
输出格式
无
输入输出样例
输入 #1
7 2 7 3 6 4 5 0 0 0 0 0 0 0 0
输出 #1
4
#include<bits/stdc++.h>
using namespace std;
struct node{
int lc,rc;
}tree[100000];
int maxid=0;
void f(int i,int n)
{
if(i==0)return ; //当值为0的时候返回
maxid=max(maxid,n); //取最大深度
f(tree[i].lc,n+1);
f(tree[i].rc,n+1);
}
int main()
{
int x;
cin>>x;
for (int i=1;i<=x;i++)
cin>>tree[i].lc>>tree[i].rc;
f(1,1); //1为根结点，深度为1
cout<<maxid;
return 0;
}朋友
题目背景
小明在 A 公司工作，小红在 B 公司工作。
题目描述
这两个公司的员工有一个特点：一个公司的员工都是同性。
A 公司有 NN 名员工，其中有 PP 对朋友关系。B 公司有 MM 名员工，其中有 QQ 对朋友关系。朋友的朋友一定还是朋友。
每对朋友关系用两个整数 (X_i,Y_i)(Xi,Yi) 组成，表示朋友的编号分别为 X_i,Y_iXi,Yi。男人的编号是正数，女人的编号是负数。小明的编号是 11，小红的编号是 -1−1。
大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。
输入格式
输入的第一行，包含 44 个空格隔开的正整数 N,M,P,QN,M,P,Q。
之后 PP 行，每行两个正整数 X_i,Y_iXi,Yi。
之后 QQ 行，每行两个负整数 X_i,Y_iXi,Yi。
输出格式
输出一行一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。
输入输出样例
输入 #1
4 3 4 2 1 1 1 2 2 3 1 3 -1 -2 -3 -3
输出 #1
2
#include<bits/stdc++.h>
using namespace std;
int c[1000010],d[1000010],a[1000010],b[1000010];
const int N=1000005; //指定并查集所能包含元素的个数（由题意决定）
int pre[N]; //存储每个结点的前驱结点
void init(int n) //初始化函数，对录入的 n个结点进行初始化
{
for(int i = 1; i <= n; i++)
pre[i] = i; //每个结点的上级都是自己
}
int find(int x) //改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低
{
if(pre[x] == x) return x; //递归出口：x的上级为 x本身，即 x为根结点
return pre[x] = find(pre[x]); //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx
}
bool isSame(int x, int y) //判断两个结点是否连通
{
return find(x) == find(y); //判断两个结点的根结点（即代表元）是否相同
}
void join(int x,int y) //合并x和y
{
int fx=find(x), fy=find(y); //寻找x和y的代表元
if(fx != fy) //如果不一样
pre[fx]=fy; //任意选一个作为代表元
}
int main()
{
int n,m,p,q;
cin>>n>>m>>p>>q;
init(n+m);
for(int i=1;i<=p;i++){
cin>>c[i]>>d[i];
join(c[i]+m,d[i]+m);
}
int t=0;
for(int i=1+m;i<=n+m;i++){
if(isSame(i,m+1))t++;
}
for(int i=1;i<=q;i++){
cin>>a[i]>>b[i];
join(a[i]+m+1,b[i]+m+1);
}
int w=0;
for(int i=1;i<=m;i++){
if(isSame(i,m))w++;
}
cout<<min(t,w);
return 0;
}