数据结构与算法 - 二叉树

1. 概述

二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子

完全二叉树：是一种二叉树结构，除了最后一层以外，每一层都必须填满，填充时要遵循从左到右

平衡二叉树：是一种二叉树结构，其中每个节点的左右子树高度相差不超过1

2. 存储

存储方式分为两种:

①定义树结点与左、右孩子引用（TreeNode）

②使用数组，若用0作为树的根节点，索引可以通过以下方式计算

• 父 = floor((子 - 1) / 2)
• 左孩子 = 父 * 2 + 1
• 右孩子 = 父 * 2 + 2

3. 遍历

遍历方式也分为两种：

①广度优先遍历：尽可能先访问距离根节点最近的节点，也称为层序遍历

②深度优先遍历：对于二叉树，可以进一步划分为三种（要深入到叶子节点）

• pre-order前序遍历：对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
• in-order中序遍历：对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
• post-order后续遍历：对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

3.1 广度优先遍历

1. 初始化，将根节点加入队列

2. 循环处理队列中每个节点，直至队列为空

3. 每次循环内处理节点后，将它的孩子节点（即下一层节点）加入队列

注意：

• 以上用队列来实现层序遍历是针对TreeNode这种方式表示的二叉树
• 对于数组实现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序

3.2 深度优先遍历