二叉树的概念和静态实现 【复习笔记】

1. 二叉树的概念和种类

1.1 二叉树的定义

⼆叉树是⼀种特殊的树型结构，它的特点是每个结点最多只有 2 棵子树（可能没有，也可能只有一个），节点间有明确的父子关系，左、右子树有序（二叉树结点的孩子被称为左孩子和右孩子），不能颠倒

1.2 二叉树的种类

1. 满二叉树

满二叉树是指除最后一层无任何叶子节点（所有叶子节点都在同一层），所有非叶子节点都有两个子节点

2. 完全二叉树

在满二叉树的基础上，最后一层叶子节点从右往左依次删除若干节点，剩下的即为完全二叉树

2. 二叉树的存储

二叉树是一种特殊的树，也可以使用树的存储方法（用数组实现树的遍历），只需要标记左孩子和右孩子

二叉树还有自己的存储方法：顺序存储和链式存储

2.1 顺序存储

我们要知道二叉树结点如果根节点开始由 1 编号，编号的一些性质（结点下标为 i ）：

1. 如果存在父节点，父节点下标：i / 2 

2. 如果存在子节点，左孩子节点下标：i * 2；右孩子下标：i * 2+1

使用数组存储，数组的下标就是节点的编号（非完全二叉树，要先补全再编号），数组存储值

注意：顺序存储一般适用于完全二叉树和满二叉树，因为其他二叉树很容易浪费数组空间

2.2 链式存储

这里先使用数组静态实现，动态实现放在之后篇章。

如果给定的二叉树有编号，树我们可以使用两个数组 l [N],r [N] 分别存储左孩子和右孩子,下标为父节点

比如：

输入描述: 第一行一个整数 n ，表示节点数（ n<=1e6),根节点编号为1

                之后 n 行，第 i 行两个整数x，y，分别表示节点 i 的左右孩子编号。x=0，y=0分别表示无左右孩子 

​
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int l[N], r[N];
int n;

int main()
{
	cin >> n;
	//编号从1开始
	for (int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	return 0;
}

​

3. 二叉树的遍历

和树一样，二叉树也有深度优先遍历和宽度优先遍历

3.1 深度优先遍历

和常规的树不一样，二叉树的深度优先遍历有自己独特的特性:先序遍历，中序遍历，后序遍历

遍历顺序：

先序遍历：根   左   右

中序遍历：左   根   右

后序遍历：左   右   根

比如：

输入描述: 第一行一个整数 n ，表示节点数（ n<=1e6),根节点编号为1

                之后 n 行，第 i 行两个整数x，y，分别表示节点 i 的左右孩子编号。x=0，y=0分别表示无左右孩子 

const int N = 1e6 + 10;
int l[N];
int r[N];
int n;

void dfs1(int x)
{
	if (x == 0) return;
	//根
	cout << x << " ";
	//左子树
	dfs1(l[x]);
	//右子树
	dfs1(r[x]);
}

void dfs2(int x)
{
	if (x == 0) return;
	dfs2(l[x]);
	cout << x << " ";
	dfs2(r[x]);
}

void dfs3(int x)
{
	if (x == 0) return;
	dfs3(l[x]);
	dfs3(r[x]);
	cout << x << " ";
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}

	//先序遍历
	dfs1(1);
	//中序遍历
	dfs2(2);
	//后序遍历
	dfs3(3);
	return 0;
}

3.2 宽度优先遍历

和树一样，可以用队列实现

#include<queue>;
const int N = 1e6 + 10;
int l[N];
int r[N];
int n;

void bfs()
{
	queue<int> q;
	q.push(1);

	while (q.size())
	{
		auto u = q.front();
		q.pop();
		cout << u << " ";

		//左、右孩子入队
		if(l[u]) q.push(l[u]);
		if(r[u]) q.push(r[u]);
	}
	cout << endl;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	//宽度优先遍历
	bfs();
	return 0;
}