8.二叉树
8.1概述
二叉树是一种基本的非线性数据结构,它是由n(n>=0)个节点构成的有限集合。在二叉树中,每个节点最多有两个子节点,通常被称作左孩子(left child)和右孩子(right child)。此外,二叉树还具有以下特点: 每个节点包含一个值(也可以包含其他信息)。 有一个被称为根(root)的特殊节点,它是二叉树的起点,没有父节点。 如果一个节点存在左子节点,则该节点称为左子节点的父节点;同样,如果存在右子节点,则称为右子节点的父节点。 每个节点的所有子孙(包括子节点、孙子节点等)构成了该节点的子树(subtree)。 左子树和右子树本身也是二叉树,且可以为空。
遍历:
广度优先遍历(Breadth-First Search, BFS)和深度优先遍历(Depth-First Search, DFS)是两种在图或树这类非线性数据结构中搜索节点的常用策略。
广度优先遍历(BFS): 从根节点开始,首先访问所有与根节点直接相连的节点(即第一层邻居节点),然后按顺序访问它们的子节点(第二层),接着是孙子节点(第三层),以此类推。 使用队列作为辅助数据结构,将起始节点入队,每次从队列头部取出一个节点进行访问,并将其未被访问过的相邻节点全部加入队列尾部,直到队列为空为止。 在二叉树场景下,BFS通常实现为层序遍历,它会按照从上到下、从左到右的顺序依次访问各个节点。
深度优先遍历(DFS): 从根节点开始,尽可能深地探索图或树的分支,直到到达叶子节点或者无法继续深入时返回上一层节点,再尝试探索其他分支。 深度优先遍历有多种方式:前序遍历(先访问根节点,再遍历左子树,最后遍历右子树)、中序遍历(先遍历左子树,再访问根节点,最后遍历右子树)、后序遍历(先遍历左子树,再遍历右子树,最后访问根节点)以及反向的前后序遍历等。 在二叉树的DFS中,通常使用递归的方式实现。另外,也可以借助栈这一数据结构,模拟递归过程进行非递归实现。 总结来说,BFS保证了同一层次的节点会被一起访问到,而DFS则是沿着一条路径尽可能深地探索,直至无法继续前进时回溯至另一条路径。这两种遍历方式在解决不同的问题时各有优势,如寻找最短路径、拓扑排序等场景常常会用到BFS,而解决迷宫求解、判断连通性等问题时DFS则更为常见。
前序遍历(Preorder Traversal): 从根节点开始,首先访问根节点,然后按照相同的方式遍历左子树,最后遍历右子树。用文字描述就是: 访问当前节点(即根节点)。 递归地对当前节点的左子树进行前序遍历。 递归地对当前节点的右子树进行前序遍历。
中序遍历(Inorder Traversal): 在中序遍历中,访问顺序为:左子树 -> 根节点 -> 右子树。 递归地对当前节点的左子树进行中序遍历。 访问当前节点。 递归地对当前节点的右子树进行中序遍历。
后序遍历(Postorder Traversal): 在后序遍历中,访问顺序为:左子树 -> 右子树 -> 根节点。 递归地对当前节点的左子树进行后序遍历。 递归地对当前节点的右子树进行后序遍历。 访问当前节点。