Java实现二叉树的深度优先遍历和广度优先遍历算法示例

针对“Java实现二叉树的深度优先遍历和广度优先遍历算法示例”的题目，下面给出完整的攻略。

什么是二叉树深度优先遍历和广度优先遍历

在学习Java实现二叉树深度优先遍历和广度优先遍历之前，我们需要先了解什么是二叉树深度优先遍历和广度优先遍历。

二叉树深度优先遍历是先访问根节点，再遍历左子树，最后再遍历右子树。而广度优先遍历则是一层一层地访问树节点，即先访问第一层，在访问第二层，直到所有的节点都被访问。

二叉树深度优先遍历

深度优先遍历有三种方式：前序遍历、中序遍历和后序遍历。

1.前序遍历

前序遍历的步骤是：

1.访问根节点
2.遍历左子树
3.遍历右子树

实现示例：

class Node {  
    int val;  
    Node left;  
    Node right;  

    public Node(int val) {  
        this.val = val;  
    }  
}  
public class BinaryTree {  
    //前序遍历  
    public static void preOrder(Node root) {  
        if (root != null) {  
            System.out.println(root.val);  
            preOrder(root.left);  
            preOrder(root.right);  
        }  
    }  

    public static void main(String[] args) {  
        Node node1 = new Node(1);  
        Node node2 = new Node(2);  
        Node node3 = new Node(3);  
        Node node4 = new Node(4);  
        Node node5 = new Node(5);  
        Node node6 = new Node(6);  
        Node node7 = new Node(7);  
        Node node8 = new Node(8);  
        node1.left = node2;  
        node1.right = node3;  
        node2.left = node4;  
        node3.left = node5;  
        node3.right = node6;  
        node4.right = node7;  
        node5.left = node8;  
        preOrder(node1);  
    }  
} 

2.中序遍历

中序遍历的步骤是：

1.遍历左子树
2.访问根节点
3.遍历右子树

实现示例：

class Node {  
    int val;  
    Node left;  
    Node right;  

    public Node(int val) {  
        this.val = val;  
    }  
}  
public class BinaryTree {  
    //中序遍历  
    public static void inOrder(Node root) {  
        if (root != null) {  
            inOrder(root.left);  
            System.out.println(root.val);  
            inOrder(root.right);  
        }  
    }  

    public static void main(String[] args) {  
        Node node1 = new Node(1);  
        Node node2 = new Node(2);  
        Node node3 = new Node(3);  
        Node node4 = new Node(4);  
        Node node5 = new Node(5);  
        Node node6 = new Node(6);  
        Node node7 = new Node(7);  
        Node node8 = new Node(8);  
        node1.left = node2;  
        node1.right = node3;  
        node2.left = node4;  
        node3.left = node5;  
        node3.right = node6;  
        node4.right = node7;  
        node5.left = node8;  
        inOrder(node1);  
    }  
}

3.后序遍历

后序遍历的步骤是：

1.遍历左子树
2.遍历右子树
3.访问根节点

实现示例：

class Node {  
    int val;  
    Node left;  
    Node right;  

    public Node(int val) {  
        this.val = val;  
    }  
}  
public class BinaryTree {  
    //后序遍历  
    public static void postOrder(Node root) {  
        if (root != null) {  
            postOrder(root.left);  
            postOrder(root.right);  
            System.out.println(root.val);  
        }  
    }  

    public static void main(String[] args) {  
        Node node1 = new Node(1);  
        Node node2 = new Node(2);  
        Node node3 = new Node(3);  
        Node node4 = new Node(4);  
        Node node5 = new Node(5);  
        Node node6 = new Node(6);  
        Node node7 = new Node(7);  
        Node node8 = new Node(8);  
        node1.left = node2;  
        node1.right = node3;  
        node2.left = node4;  
        node3.left = node5;  
        node3.right = node6;  
        node4.right = node7;  
        node5.left = node8;  
        postOrder(node1);  
    } 
}

二叉树广度优先遍历

广度优先遍历可以使用队列来实现。

实现示例：

import java.util.LinkedList;  
import java.util.Queue;  
class Node {  
    int val;  
    Node left;  
    Node right;  

    public Node(int val) {  
        this.val = val;  
    }  
}  
public class BinaryTree {  
    //广度优先遍历  
    public static void bfs(Node root) {  
        if (root == null) {  
            return;  
        }  
        Queue<Node> queue = new LinkedList<Node>();  
        queue.offer(root);  
        while (!queue.isEmpty()) {  
            Node node = queue.poll();  
            System.out.println(node.val);  
            if (node.left != null) {  
                queue.offer(node.left);  
            }  
            if (node.right != null) {  
                queue.offer(node.right);  
            }  
        }  
    }  

    public static void main(String[] args) {  
        Node node1 = new Node(1);  
        Node node2 = new Node(2);  
        Node node3 = new Node(3);  
        Node node4 = new Node(4);  
        Node node5 = new Node(5);  
        Node node6 = new Node(6);  
        Node node7 = new Node(7);  
        Node node8 = new Node(8);  
        node1.left = node2;  
        node1.right = node3;  
        node2.left = node4;  
        node3.left = node5;  
        node3.right = node6;  
        node4.right = node7;  
        node5.left = node8;  
        bfs(node1);  
    }  
}

通过上面给出的Java实现二叉树深度优先遍历和广度优先遍历算法示例，你已经能够学会如何实现这两种二叉树遍历方式了。