二叉树的遍历

遍历二叉树一共有四种方式:前序遍历,中序遍历,后序遍历,层序遍历(广度优先)

准备

先定义一个结点类(后续代码需要使用)

public class Node<V> {
    public V value;
    public Node<V> left;
    public Node<V> right;
    public Node(V value) {
        this.value = value;
    }
}

前序遍历

操作步骤如下:

  1. 访问根结点
  2. 递归遍历左子树
  3. 递归遍历右子树

假设一个二叉树的结构如下图所示:二叉树
则遍历结果为:1 2 4 5 3 6
实现方式:

  • 递归方式
public class PreOrderRecursivelyVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        System.out.println(node.value + " ");
        visit(root.left, output);
        visit(root.right, output);
    }
}
  • 非递归方式

借助栈(先进后出)来实现
代码如下:

public class PreOrderVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        Stack<Node<V>> help = new Stack<>();
        // 1. 根结点入栈
        help.push(root);
        while (!help.isEmpty()) {
            // 2. 栈顶结点出栈
            Node<V> node = help.pop();
            // 3. 访问出栈结点
            System.out.println(node.value + " ");
            // 4. 依次将该结点的右,左孩子入栈
            if (node.right != null) {
                help.push(node.right);
            }
            if (node.left != null) {
                help.push(node.left);
            }
        }
    }
}

中序遍历

操作步骤如下:

  1. 递归遍历左子树
  2. 访问根结点
  3. 递归遍历右子树

假设一个二叉树的结构如下图所示:二叉树
则遍历结果为:4 2 5 1 3 6
实现方式:

  • 递归方式
public class InOrderRecursivelyVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        visit(root.left, output);
        System.out.println(node.value + " ");
        visit(root.right, output);
    }
}
  • 非递归方式
public class InOrderVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        Stack<Node<V>> help = new Stack<>();
        // 定义一个当前结点遍历并指向根结点
        Node<V> current = root;
        while (current != null || !help.isEmpty()) {
            if (current != null) {
                // 若当前结点不为空,则入栈
                help.push(current);
                // 将当前结点指向该结点的左孩子
                current = current.left;
            } else {
                // 若当前结点为空(即当前已经没有可访问的左子树了),则出栈
                current = help.pop();
                // 访问出栈结点
                System.out.println(current.value + " ");
                // 将当前结点指向出栈结点的右孩子
                current = current.right;
                // (若该结点存在,则重复执行上面的if分支将该结点的左子树依次入栈)
            }
        }
    }
}

后序遍历

操作步骤如下:

  1. 递归遍历左子树
  2. 递归遍历右子树
  3. 访问根结点

假设一个二叉树的结构如下图所示:二叉树
则遍历结果为:4 5 2 6 3 1
实现方式:

  • 递归方式
public class PostOrderRecursivelyVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        visit(root.left, output);
        visit(root.right, output);
        System.out.println(node.value + " ");
    }
}
  • 非递归方式

这种方式稍微复杂一点,因为要先遍历完左右子树,再访问根结点,所以需要知道左右子树的访问状态。

public class PostOrderVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        Stack<Node<V>> help = new Stack<>();
        // 根结点入栈
        help.push(root);
        // top指向栈顶元素
        Node<V> top = null;
        // visited表示刚刚访问过的结点(初始指向根结点)
        Node<V> visited = root;
        while (!help.isEmpty()) {
            // 获取栈顶元素,但是不进行出栈操作
            top = help.peek();
            if (top.left != null && top.left != visited && top.right != visited) {
                // 若栈顶元素的左孩子结点存在,且左右孩子都未被访问过,则左孩子入栈
                help.push(top.left);
            } else if (top.right != null && top.right != visited) {
                // 若栈顶元素的右孩子结点存在,且右孩子未被访问过,则右孩子入栈
                help.push(top.right);
            } else {
                // 栈顶元素出栈,并访问该结点
                System.out.println(help.pop().value + " ");
                // 记录已访问过的结点
                visited = top;
            }
        }
    }
}

层序遍历

也可称为广度优先遍历
操作步骤如下:
从上往下,从左至右依次访问每层的结点
假设一个二叉树的结构如下图所示:二叉树
则遍历结果为:1 2 3 4 5 6
实现方式:
借助队列(先进先出)来实现
代码如下:

public class LevelOrderVisitor {
    public <V> void visit(Node<V> root) {
        if (root == null) {
            return;
        }
        Queue<Node<V>> queue = new LinkedList<>();
        // 根结点进入队尾
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 出队列
            Node<V> node = queue.poll();
            // 访问该结点
            System.out.println(node.value + " ");
            // 依次将该结点的左右孩子入队列
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}

以上就是遍历二叉树的几种方式,完整代码可查看二叉树的遍历。如有错误,请指正,谢谢。

评论

暂无评论