02顺序二叉树+深度标记：二叉树深度

【深基16.例3】二叉树深度

题目描述

有一个 $n(n \le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 0 0。

建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

输入格式

第一行一个整数 $n$，表示结点数。

之后 $n$ 行，第 $i$ 行两个整数 $l$、$r$，分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点，$r=0$ 同理。

输出格式

一个整数，表示最大结点深度。

样例 #1

样例输入 #1

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

样例输出 #1

4

本蒟蒻的小记

这道题的步骤划分为两个：

第一步：根据要求建树，对于这种1-7元素都有的这种树，除了传统的顺序存储，和传统的链式存储，还可以用数组顺序存储链式存储混合存储（即数组中的每个元素都是一个结构体，都有leftchild和rightchild的下标，通过下表实现“指向”的概念）

第二步：广度优先搜索算法：这个比较简单直接看代码

#include<iostream>
#include<cstdlib>
#include<string>
#include<queue>
#define max_size 1000005
using namespace std;
typedef struct bit{
	long long depth=1;
	long long number;
	long long lchild;
	long long rchild;
}bitree;
bitree bi[max_size];//树的数组是全局变量
queue<bitree> q;//广搜需要队列
long long bfs()//广度优先搜索算法部分
{
	q.push(bi[1]);
	long long max=0;
	while(!q.empty())
	{
		if(q.front().lchild!=-1)
		{
			bi[q.front().lchild].depth =q.front().depth+1;
			q.push(bi[q.front().lchild]);
		}
		if(q.front().rchild!=-1)
		{
			bi[q.front().rchild].depth =q.front().depth+1;
			q.push(bi[q.front().rchild]);
		}
		if(q.front().lchild==-1 && q.front().rchild==-1  && q.front().depth>max)
		{
			max=q.front().depth;
		}
		q.pop();
	}
	return max;
}
int main()
{
	long long n,lch,rch,ans;
	cin>>n;
	for(int i=1;i<=n;i++)//这个循环实现了建树功能
	{
		cin>>lch>>rch;
		bi[i].number =i;
		bi[i].lchild =lch==0?-1:lch;
		bi[i].rchild =rch==0?-1:rch;
	}
	ans=bfs();
	cout<<ans<<endl;
	return 0;
}

完结撒花