（数据结构）二叉树

时间：2024-03-05 16:14:47

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;
                }
            }
        }
    }
}

相关文章