树和图的遍历及java代码实现

深度遍历要使用栈或者递归 （递归就是基于栈实现的）

public class Bianli {

    private static class Node{

        public Node(Integer data) {
            this.data = data;
        }

        public Node() {
        }

        private Integer data;
        public Node lChild;
        public Node rChild;

    }

    //先序遍历
    public static void pre(Node root){
        if (root == null){
            return;
        }
        System.out.println(root.data);
        pre(root.lChild);
        pre(root.rChild);
    }

    //中序遍历
    public static void mid(Node root){

        if (root == null){
            return;
        }
        mid(root.lChild);
        System.out.println(root.data);
        mid(root.rChild);
    }

    //后序遍历
    public static void post(Node root){

        if (root == null){
            return;
        }
        post(root.lChild);
        post(root.rChild);
        System.out.println(root.data);
    }

    public static void main(String[] args) {

        Node node = new Node(1);
        node.lChild = new Node(2);
        node.rChild = new Node(3);
        node.lChild.lChild = new Node(4);
        node.lChild.rChild = new Node(5);
        node.rChild.lChild = new Node(6);
        node.rChild.rChild = new Node(7);

        pre(node);//先序
        mid(node);//后序
        post(node);//后序
    }

}

基于栈实现的

public class StackBianLiTree {

    public static class Node{
        public Integer data;
        public Node lChild;
        public Node rChild;

        public Node(Integer data) {
            this.data = data;
        }
    }

    //先序遍历
    public static void pre(Node root){
        if (root !=null){
            Stack stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()){
                root= stack.pop();//root重新指向栈弹出的元素
                System.out.println(root.data);
                if (root.rChild!=null){
                    stack.push(root.rChild);
                }
                if (root.lChild!=null){
                    stack.push(root.lChild);
                }
            }
        }

    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.lChild = new Node(2);
        root.rChild = new Node(3);
        root.lChild.lChild = new Node(4);
        root.lChild.rChild = new Node(5);
        root.rChild.lChild = new Node(6);
        root.rChild.rChild = new Node(7);

        pre(root);

    }

}

广度遍历需要使用队列

public class QueueCengCiBianLiTree {

    public static class Node {
        public Integer data;
        public Node lChild;
        public Node rChild;

        public Node(Integer data) {
            this.data = data;
        }
    }

    public static void cengCi(Node root){
        linkedList queue = new linkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            root = queue.remove();//root指向队列中弹出的元素
            System.out.println(root.data);
            if (root.lChild != null){
                queue.add(root.lChild);
            }
            if (root.rChild != null){
                queue.add(root.rChild);
            }
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.rChild = new Node(2);
        root.lChild = new Node(3);
        root.lChild.lChild = new Node(4);
        root.lChild.rChild = new Node(5);
        root.rChild.lChild = new Node(6);
        root.rChild.rChild = new Node(7);

        cengCi(root);
    }

}

public class BianLi {

    
    private static class Vertex{
        int data;

        public Vertex(int data) {
            this.data = data;
        }
    }
    
    private static class Graph{
        private int size;
        private Vertex[] vertices;
        private linkedList linkedList[];

        public Graph(int size) {
            //初始化顶点和邻接链表
            this.size = size;
            vertices = new Vertex[size];
            linkedList = new linkedList[size];
            for (int i = 0; i < size; i++) {
                vertices[i] = new Vertex(i); // 初始化顶点
                linkedList[i] = new linkedList(); //初始化链表
            }
        }
    }

    
    public static void dfs(Graph graph,int start,boolean[] visited){
        if (visited[start]){
            return;
        }
        System.out.println(graph.vertices[start].data);
        visited[start] = true;
        for (Integer index : graph.linkedList[start]) {
            dfs(graph,index,visited); //使用递归
        }

    }

    

    public static void bfs(Graph graph,int start,boolean[] visited,linkedList queue){
        queue.add(graph.vertices[start].data);
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            if (visited[poll]){//已经遍历过
                continue;
            }
            System.out.println(graph.vertices[poll].data);
            visited[poll]=true;
            //将它连接的全部入队
            for (Integer index : graph.linkedList[poll]) {
                queue.add(index);
            }
        }


    }


    public static void main(String[] args) {
        Graph graph = new Graph(4); //new 的时候已经初始化顶点
        // 现在要向链表中添加数据也就是边
        //初始化一个无向图，有向图和无向图一个道理，就是多个边
        graph.linkedList[0].add(1);
        graph.linkedList[0].add(2);

        graph.linkedList[1].add(0);
        graph.linkedList[1].add(3);

        graph.linkedList[2].add(0);
        graph.linkedList[2].add(3);

        graph.linkedList[3].add(1);
        graph.linkedList[3].add(2);
        System.out.println("图的深度优先遍历");
        dfs(graph,1,new boolean[graph.size]);
        System.out.println("图的广度优先遍历");
        bfs(graph,0,new boolean[graph.size],new linkedList());
    }
}

总结： 其实对于树和图这两种数据结构，深度优先遍历要使用栈，广度优先遍历要使用队列，不知道是不是只限于这两种数据结构，我觉得其他的数据结构也符合这个规律