Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

下面是Java实现的二叉树常用操作的完整攻略：

前置知识

在学习本攻略之前，需要掌握以下基础知识：

Java的基本语法以及面向对象编程的理解
二叉树的定义与性质

二叉树的定义

二叉树是一种树状结构，其中每个节点最多有两个子节点。二叉树的定义如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

每个节点都有一个值(val)和左右子节点(left, right)，可以通过递归的方式定义一棵树。

前序建树

前序建树是指根据给定的前序遍历序列(preorder)构建一棵二叉树。前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

前序建树的基本思路是：

先读取当前节点的值val
如果val为null，说明此处没有树节点，返回null
否则，新建节点，并将当前节点指向新节点
递归构建左子树
递归构建右子树

Java实现如下：

public static TreeNode buildTree(Scanner scanner) {
    int val = scanner.nextInt(); // 读取当前节点的值
    if (val == -1) { // 如果是-1，说明此处没有树节点，返回null
        return null;
    }
    TreeNode root = new TreeNode(val); // 否则，新建树节点
    root.left = buildTree(scanner); // 递归构建左子树
    root.right = buildTree(scanner); // 递归构建右子树
    return root;
}

示例1：假设给定一棵二叉树的前序遍历序列：1 2 -1 -1 3 4 -1 -1 5 -1 -1，其中-1表示无树节点，需要根据此序列构建一棵二叉树。在Java中调用如下：

Scanner scanner = new Scanner(System.in);
TreeNode root = buildTree(scanner);

示例2：假设给定一棵二叉树的前序遍历序列：5 6 -1 7 -1 -1 8 -1 -1，其中-1表示无树节点，需要根据此序列构建一棵二叉树。在Java中调用如下：

Scanner scanner = new Scanner(System.in);
TreeNode root = buildTree(scanner);

前中后递归遍历

前中后序遍历是二叉树最基本也是最常用的遍历方法。前序遍历的顺序是：根节点 -> 左子树 -> 右子树；中序遍历的顺序是：左子树 -> 根节点 -> 右子树；后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

递归实现的基本思路是：

对于当前节点，先遍历它的左子树
然后遍历当前节点
最后遍历当前节点的右子树

Java实现如下：

public static void preorder(TreeNode root) { // 前序遍历
    if (root == null) { // 如果当前节点为null，返回
        return;
    }
    System.out.print(root.val + " "); // 遍历当前节点
    preorder(root.left); // 递归遍历左子树
    preorder(root.right); // 递归遍历右子树
}

public static void inorder(TreeNode root) { // 中序遍历
    if (root == null) { // 如果当前节点为null，返回
        return;
    }
    inorder(root.left); // 递归遍历左子树
    System.out.print(root.val + " "); // 遍历当前节点
    inorder(root.right); // 递归遍历右子树
}

public static void postorder(TreeNode root) { // 后序遍历
    if (root == null) { // 如果当前节点为null，返回
        return;
    }
    postorder(root.left); // 递归遍历左子树
    postorder(root.right); // 递归遍历右子树
    System.out.print(root.val + " "); // 遍历当前节点
}

示例1：假设给定一棵二叉树：

前序遍历的输出结果为：1 2 3 4 5；中序遍历的输出结果为：2 1 4 3 5；后序遍历的输出结果为：2 4 5 3 1。在Java中调用如下：

preorder(root);
inorder(root);
postorder(root);

示例2：假设给定一棵二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

前序遍历的输出结果为：1 2 4 5 3 6 7；中序遍历的输出结果为：4 2 5 1 6 3 7；后序遍历的输出结果为：4 5 2 6 7 3 1。在Java中调用如下：

preorder(root);
inorder(root);
postorder(root);

前中后非递归遍历

前中后序遍历可以使用非递归算法实现，非递归算法通常需要使用到栈。我们对于前序遍历进行非递归遍历的解析，中序遍历和后序遍历的实现方式类似。

前序遍历非递归实现基本思路是：

把根节点放到栈中
如果栈不为空，弹出栈顶元素，并遍历该节点
遍历完该节点后，先把右子树压栈，再把左子树压栈

Java实现如下：

public static void preorderNonRecursive(TreeNode root) { // 非递归前序遍历
    Stack<TreeNode> stack = new Stack<>();
    if (root != null) { // 如果不是空树，将根节点入栈
        stack.push(root);
    }
    while (!stack.isEmpty()) { // 栈不为空时循环
        TreeNode node = stack.pop(); // 取出栈顶元素
        System.out.print(node.val + " "); // 遍历当前节点
        if (node.right != null) { // 先把右子树入栈
            stack.push(node.right);
        }
        if (node.left != null) { // 再把左子树入栈
            stack.push(node.left);
        }
    }
}

示例1：假设给定一棵二叉树：

非递归前序遍历的输出结果为：1 2 3 4 5。在Java中调用如下：

preorderNonRecursive(root);

示例2：假设给定一棵二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

非递归前序遍历的输出结果为：1 2 4 5 3 6 7。在Java中调用如下：

preorderNonRecursive(root);

层序遍历

层序遍历也叫广度优先遍历，是二叉树另一种常用的遍历方法，它需要使用队列进行实现。

层序遍历的基本思路是：

将根节点放入队列中
当队列不为空时，循环执行以下操作：
1. 弹出队首元素并遍历
2. 将队首元素的左子树和右子树入队

Java实现如下：

public static void levelorder(TreeNode root) { // 层序遍历
    Queue<TreeNode> queue = new LinkedList<>();
    if (root != null) { // 如果不是空树，将根节点入队
        queue.offer(root);
    }
    while (!queue.isEmpty()) { // 队列不为空时循环
        TreeNode node = queue.poll(); // 取出队首元素
        System.out.print(node.val + " "); // 遍历当前节点
        if (node.left != null) { // 左子树入队
            queue.offer(node.left);
        }
        if (node.right != null) { // 右子树入队
            queue.offer(node.right);
        }
    }
}

示例1：假设给定一棵二叉树：

层序遍历的输出结果为：1 2 3 4 5。在Java中调用如下：

levelorder(root);

示例2：假设给定一棵二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

层序遍历的输出结果为：1 2 3 4 5 6 7。在Java中调用如下：

levelorder(root);

到这里，Java实现的二叉树常用操作就讲解完了。希望对您有所帮助！

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】 - Python技术站

Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

前置知识

二叉树的定义

前序建树

前中后递归遍历

前中后非递归遍历

层序遍历

相关文章