【数据结构】二叉树

知识点

（一）基础概念

一 . 二叉树

二叉树每个节点最多只能有两棵子树，且有左右之分。二叉树可以看作是有 n 个有限元素的集合，该集合或为空（空二叉树），或由一个称为根的元素及两个不相交的，且被分别称为左子树和右子树的二叉树组成，属于有序树。这里的元素也就是树的结点。

二 . 有序树与无序树

有序树：树中任意节点的子结点之间有顺序关系，即左右子树不可以互换

无序树：也称为自由树，树中任意节点的 子结点之间没有顺序关系，即左右子树可以互换

三 . 完全二叉树与满二叉树

！！满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

---

一 . 求二叉树的深度 

例题： 洛谷 P4913 【深基16.例3】二叉树深度

 题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

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

输出 #1

4

#include 
#include 
#include 
#include 
using namespace std;
int n;
const int maxn=1e7+5;
struct node{
	int l,r;
}tree[maxn<<1];
int res;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void dfs(int num,int deep)
{
	if(num == 0) return; //如果搜寻到叶节点就退出
	dfs(tree[num].l,deep+1); //搜索左子树
	dfs(tree[num].r,deep+1); //搜索右子树
	res=max(res,deep); //更新数据
}
 
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		tree[i].l=read(); tree[i].r=read();
	}
	dfs(1,1);
	printf("%d",res);
	return 0;
}