（数据结构）二叉树

8.二叉树

8.1概述

二叉树是一种基本的非线性数据结构，它是由n（n>=0）个节点构成的有限集合。在二叉树中，每个节点最多有两个子节点，通常被称作左孩子（left child）和右孩子（right child）。此外，二叉树还具有以下特点：每个节点包含一个值（也可以包含其他信息）。有一个被称为根（root）的特殊节点，它是二叉树的起点，没有父节点。如果一个节点存在左子节点，则该节点称为左子节点的父节点；同样，如果存在右子节点，则称为右子节点的父节点。每个节点的所有子孙（包括子节点、孙子节点等）构成了该节点的子树（subtree）。左子树和右子树本身也是二叉树，且可以为空。

8.2 二叉树遍历

遍历：

        广度优先遍历（Breadth-First Search, BFS）和深度优先遍历（Depth-First Search, DFS）是两种在图或树这类非线性数据结构中搜索节点的常用策略。

        广度优先遍历（BFS）：从根节点开始，首先访问所有与根节点直接相连的节点（即第一层邻居节点），然后按顺序访问它们的子节点（第二层），接着是孙子节点（第三层），以此类推。使用队列作为辅助数据结构，将起始节点入队，每次从队列头部取出一个节点进行访问，并将其未被访问过的相邻节点全部加入队列尾部，直到队列为空为止。在二叉树场景下，BFS通常实现为层序遍历，它会按照从上到下、从左到右的顺序依次访问各个节点。

        深度优先遍历（DFS）：从根节点开始，尽可能深地探索图或树的分支，直到到达叶子节点或者无法继续深入时返回上一层节点，再尝试探索其他分支。深度优先遍历有多种方式：前序遍历（先访问根节点，再遍历左子树，最后遍历右子树）、中序遍历（先遍历左子树，再访问根节点，最后遍历右子树）、后序遍历（先遍历左子树，再遍历右子树，最后访问根节点）以及反向的前后序遍历等。在二叉树的DFS中，通常使用递归的方式实现。另外，也可以借助栈这一数据结构，模拟递归过程进行非递归实现。总结来说，BFS保证了同一层次的节点会被一起访问到，而DFS则是沿着一条路径尽可能深地探索，直至无法继续前进时回溯至另一条路径。这两种遍历方式在解决不同的问题时各有优势，如寻找最短路径、拓扑排序等场景常常会用到BFS，而解决迷宫求解、判断连通性等问题时DFS则更为常见。

8.3 深度优先遍历

深度优先遍历（DFS）分为：

        前序遍历（Preorder Traversal）：在前序遍历中，访问顺序为：根节点 -> 左子树 -> 右子树。递归地对当前节点的左子树进行前序遍历。递归地对当前节点的右子树进行前序遍历。

        中序遍历（Inorder Traversal）：在中序遍历中，访问顺序为：左子树 -> 根节点 -> 右子树。递归地对当前节点的左子树进行中序遍历。访问当前节点。递归地对当前节点的右子树进行中序遍历。

        后序遍历（Postorder Traversal）：在后序遍历中，访问顺序为：左子树 -> 右子树 -> 根节点。递归地对当前节点的左子树进行后序遍历。递归地对当前节点的右子树进行后序遍历。访问当前节点。

8.3.1 递归实现遍历


public class TreeTraversal {public static void main(String[] args) {TreeNode tree = new TreeNode(new TreeNode(new TreeNode(4), 2, null),1,new TreeNode(new TreeNode(5), 3, new TreeNode(6)));preOrder(tree);System.out.println();inOrder(tree);System.out.println();postOrder(tree);System.out.println();
}/** 前序遍历 根节点=》左子树=》右子树* *///递归实现static void preOrder(TreeNode treeNode){if(treeNode==null){return;}System.out.print(treeNode.val+"\t");//根节点preOrder(treeNode.left);//左子树preOrder(treeNode.right);//右子树}/** 中序遍历 左子树=》=》根节点=》右子树* */static void inOrder(TreeNode treeNode){if(treeNode==null){return;}inOrder(treeNode.left);//左子树System.out.print(treeNode.val+"\t");//根节点inOrder(treeNode.right);//右子树}/** 后序遍历 左子树=》右子树 =》根节点* */static void postOrder(TreeNode treeNode){if(treeNode==null){return;}postOrder(treeNode.left);//左子树postOrder(treeNode.right);//右子树System.out.print(treeNode.val+"\t");//根节点}
}

8.3.2 非递归实现遍历

//非递归实现
public class TreeTraversal2 {public static void main(String[] args) {TreeNode tree = new TreeNode(new TreeNode(new TreeNode(4), 2, null),1,new TreeNode(new TreeNode(5), 3, new TreeNode(6)));preOrder(tree);System.out.println();inOrder(tree);System.out.println();postOrder(tree);System.out.println();}/** 前序遍历 根节点=》左子树=》右子树* */static void preOrder(TreeNode treeNode){LinkedList<TreeNode> stack = new LinkedList<>();//定义一个指针,当前节点TreeNode curr = treeNode;//去的路径为前序遍历，回的路径为中序遍历while (curr != null||!stack.isEmpty()) {if (curr != null) {stack.push(curr);//压入栈，为了记住返回的路径System.out.print("前序" + curr.val + "\t");curr = curr.left;}else {TreeNode peek = stack.peek();TreeNode pop=stack.pop();curr= pop.right;}}}/** 中序遍历 左子树=》=》根节点=》右子树* */static void inOrder(TreeNode treeNode){LinkedList<TreeNode> stack = new LinkedList<>();//定义一个指针,当前节点TreeNode curr = treeNode;//去的路径为前序遍历，回的路径为中序遍历while (curr != null||!stack.isEmpty()) {if (curr != null) {stack.push(curr);//压入栈，为了记住返回的路径curr = curr.left;}else {TreeNode peek = stack.peek();TreeNode pop=stack.pop();System.out.print("中序" + pop.val + "\t");curr= pop.right;}}}/** 后序遍历 左子树=》右子树 =》根节点* */static void postOrder(TreeNode treeNode){LinkedList<TreeNode> stack = new LinkedList<>();//定义一个指针,当前节点TreeNode curr = treeNode;//去的路径为前序遍历，回的路径为中序遍历TreeNode pop = null;while (curr != null || !stack.isEmpty()) {if (curr != null) {stack.push(curr);//压入栈，为了记住返回的路径curr = curr.left;} else {TreeNode peek = stack.peek();//右子树为null，或者最近一次弹栈的元素与当前元素的右子树相等 说明全部子树都处理完了if (peek.right == null||peek.right==pop) {//最近一次弹栈的元素pop= stack.pop();System.out.print("后序" + pop.val + "\t");} else {curr = peek.right;}}}}
}

8.3.2 非递归实现遍历2


//非递归实现
public class TreeTraversal3 {public static void main(String[] args) {TreeNode tree = new TreeNode(new TreeNode(new TreeNode(4), 2, null),1,new TreeNode(new TreeNode(5), 3, new TreeNode(6)));postOrder(tree);System.out.println();}static void postOrder(TreeNode treeNode){LinkedList<TreeNode> stack = new LinkedList<>();//定义一个指针,当前节点TreeNode curr = treeNode;//去的路径为前序遍历，回的路径为中序遍历TreeNode pop = null;while (curr != null || !stack.isEmpty()) {if (curr != null) {//压入栈，为了记住返回的路径stack.push(curr);//待处理左子树System.out.println("前序"+curr.val);curr = curr.left;} else {TreeNode peek = stack.peek();//右子树为null，无需处理if (peek.right == null) {//最近一次弹栈的元素System.out.println("中序"+peek.val);pop= stack.pop();System.out.println("后序"+pop.val);}else if(peek.right==pop) {//最近一次弹栈的元素与当前元素的右子树相等 说明右子树都处理完了pop= stack.pop();System.out.println("后序"+pop.val);}else {//待处理右子树System.out.println("中序"+peek.val);curr = peek.right;}}}}
}