【数据结构与算法】二叉树

2.10 二叉树

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

重要的二叉树结构

• 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右
• 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1

1) 存储

存储方式分为两种

1. 定义树节点与左、右孩子引用（TreeNode）
2. 使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算
   • 父 = floor((子 - 1) / 2)
   • 左孩子 = 父 * 2 + 1
   • 右孩子 = 父 * 2 + 2

2) 遍历

遍历也分为两种

1. 广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历
2. 深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）
   1. pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
   2. in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
   3. 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
[]

1. 初始化，将根节点加入队列
2. 循环处理队列中每个节点，直至队列为空
3. 每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列

注意

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

深度优先

栈暂存	已处理	前序遍历	中序遍历
[1]	1 ✔️ 左 发布者：admin，转转请注明出处：http://www.yc00.com/web/1755067111a5234918.html 数据结构与算法二叉树 admin 0 相关推荐 网站建设 【数据结构与算法】二叉树 2.10 二叉树二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子重要的二叉树结构完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右平衡二叉树（bal admin 1月前 150 发表回复 提交 评论列表（0条） 暂无评论 联系我们 400-800-8888 在线咨询： QQ交谈 邮件：admin@example.com 工作时间：周一至周五，9:30-18:30，节假日休息