亲宝软件园·资讯

展开

Java二叉树的四种遍历 Java二叉树的四种遍历(递归与非递归)

funtrin 人气:0
想了解Java二叉树的四种遍历(递归与非递归)的相关内容吗,funtrin在本文为您仔细讲解Java二叉树的四种遍历的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java二叉树,递归遍历,非递归遍历,下面大家一起来学习吧。

一、先序遍历与后序遍历

先序遍历根节点,再遍历左子树,再遍历右子树。

后序遍历先遍历左子树,再遍历右子树,再遍历根节点。

先序遍历递归实现:

public static void preOrderByRecursion(TreeNode root) {
    // 打印节点值
    System.out.println(root.value);
    preOrder(root.left);
    preOrder(root.right);
}

先序遍历的非递归实现:

非递归实现需要借助栈这样一个数据结构,实际上递归实现也是依靠栈,只不过是隐式的。

  1. 先将根节点压入栈中。
  2. 弹出栈中的节点,将弹出节点的右子节点压入栈中,再将弹出节点的左子树压入栈中。
  3. 重复步骤2,直到栈为空。
public static void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        // 打印节点值
        System.out.print(node.value + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

后序遍历递归实现:先序遍历反过来,就不赘述了。

public static void postOrderByRecursion(TreeNode root) {
    postOrderByRecursion(root.left);
    postOrderByRecursion(root.right);
    System.out.println(root.value);
}

后序遍历非递归实现:后序遍历就是先序遍历反过来,所以需要两个栈,多出来的栈用来反向输出。

public static void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(root);
    while (!s1.empty()) {
        TreeNode node = s1.pop();
        s2.push(node);
        if (node.left != null) {
            s1.push(node.left);
        }
        if (node.right != null) {
            s1.push(node.right);
        }
    }
    while (!s2.empty()) {
        System.out.println(s2.pop().value);
    }
}

二、中序遍历

中序遍历先遍历左子树,再遍历根节点,再遍历右子树。

递归遍历:

public static void inOrderByRecursion(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderByRecursion(root.left);
    // 打印节点值
    System.out.println(root.value);
    inOrderByRecursion(root.right);
}

非递归遍历:

  1. 将二叉树的左侧“边”从上到下依次压入栈中。
  2. 从栈中弹出节点
  3. 对以弹出节点的右子节点为根节点的子树,重复步骤1。
  4. 重复2、3步骤,直到栈为空。
public static void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }

    while (!stack.empty()) {
        TreeNode node = stack.pop();
        System.out.println(node.value);
        cur = node.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }
}

三、层序遍历

层序遍历顾名思义就是一层一层,从左到右的遍历二叉树。需要用到队列这一数据结构。

  1. 将根节点推入队列。
  2. 从队列中取出一个节点。
  3. 先将取出节点的左子节点推入队列,再将取出节点的右子节点推入队列。
  4. 重复2、3步骤直到队列中无节点可取。
public static void floorOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论