【数据结构与算法】二叉树
2.10 二叉树
二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子
重要的二叉树结构
- 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右
- 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1
1) 存储
存储方式分为两种
- 定义树节点与左、右孩子引用（TreeNode）
- 使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算
- 父 = floor((子 - 1) / 2)
- 左孩子 = 父 * 2 + 1
- 右孩子 = 父 * 2 + 2
2) 遍历
遍历也分为两种
- 广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历
- 深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）
- pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
- in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
- post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点
广度优先
本轮开始时队列 | 本轮访问节点 |
|---|---|
[1] | 1 |
[2, 3] | 2 |
[3, 4] | 3 |
[4, 5, 6] | 4 |
[5, 6] | 5 |
[6, 7, 8] | 6 |
[7, 8] | 7 |
[8] | 8 |
[] |
- 初始化，将根节点加入队列
- 循环处理队列中每个节点，直至队列为空
- 每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列
注意
- 以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树
- 对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序
深度优先
栈暂存 | 已处理 | 前序遍历 | 中序遍历 |
|---|---|---|---|
[1] | 1 ✔️ 左 本文发布于:2025-08-13，感谢您对本站的认可！ 版权声明:本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。  福州电脑网_福州电脑维修_福州电脑之家_福州iThome 福州电脑维修网(fzithome.com)专业的电脑维修,笔记本维修,上门维修各种电脑,笔记本,平板等,快速上门.电脑知识频道内容覆盖:计算机资讯,电脑基础应用知识,各种电脑故障维修学习,电脑外设产品维修维护,病毒，软件,硬件,常识. |
发布评论