二叉树

二叉树简介

每个节点最多有两个子节点

• 满二叉树

一棵二叉树，除叶子节点外，每个节点都有左右两个子节点，总节点个数 = 2^n - 1，n 为层数

• 完全二叉树

一棵二叉树，所有叶子节点都在最后一层或者倒数第二层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他各层节点个数都要达到最大

二叉树的遍历和查找

（1）深度优先遍历（DFS）:

• 前序遍历: 先输出父节点，再遍历左子树和右子树
• 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
• 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

（2）广度优先遍历（BFS）：

按照高度顺序，从上往下逐层遍历节点；先遍历上层节点再遍历下层节点

（3）层级遍历

深度优先遍历

中序+后序、中序+先序可以唯一确定一棵二叉树