二叉树的遍历

结点

1
2
3
4
5
6
7
8
public static class Node{
        public String value;
        public Node left;
        public Node right;
        public Node(String value){
            this.value=value;
        }
    }

生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**     前序遍历：ABDEGCF 中序遍历：DBGEACF 后序遍历：DGEBFCA
     * 第一层:A 第二层：B、C 第三层:D、E、F 第四层：G
     *          A
     *      B       C
     *   D      E        F
     *        G
     */
    public static Node getNodeList(){
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        a.left=b;
        a.right=c;
        b.left=d;
        b.right=e;
        c.right=f;
        e.left=g;
        return a;
    }

前中后序遍历(递归版)

前序

1
2
3
4
5
6
7
8
public static void recursionPre(Node head){
        if (head==null) {
            return;
        }
        System.out.print(head.value);
        recursionPre(head.left);
        recursionPre(head.right);
    }

中序

1
2
3
4
5
6
7
8
public static void recursionIn(Node head){
        if (head==null) {
            return;
        }
        recursionIn(head.left);
        System.out.print(head.value);
        recursionIn(head.right);
    }

后序

1
2
3
4
5
6
7
8
public static void recursionPos(Node head){
        if (head==null) {
            return;
        }
        recursionPos(head.left);
        recursionPos(head.right);
        System.out.print(head.value);
    }

前中后序遍历(栈实现)

前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void  stackPre(Node head){
        if (head==null) {
            return;
        }
        Stack<Node> s = new Stack<>();
        s.push(head);
        while (!s.isEmpty()){
            Node tmp = s.pop();
            System.out.print(tmp.value);
            if (tmp.right!=null) {
                s.push(tmp.right);
            }
            if (tmp.left!=null) {
                s.push(tmp.left);
            }
        }
    }

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void  stackIn(Node head){
        if (head==null) {
            return;
        }
        Stack<Node> s = new Stack<>();
        Node tmp =head;
        while (!s.isEmpty()||tmp!=null){
            while (tmp!=null){
                s.push(tmp);
                tmp=tmp.left;
            }
            Node node =s.pop();
            System.out.print(node.value);
            if (node.right!=null) {
                tmp=node.right;
            }
        }
    }

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void  stackPos(Node head){
        if (head==null) {
            return;
        }
        Stack<Node> s = new Stack<>();
        Stack<Node> s2 = new Stack<>();
        s.push(head);
        while (!s.isEmpty()){
            Node tmp = s.pop();
            s2.push(tmp);
            if (tmp.left!=null) {
                s.push(tmp.left);
            }
            if (tmp.right!=null) {
                s.push(tmp.right);
            }
        }
        while (!s2.isEmpty()){
            System.out.print(s2.pop().value);
        }
    }

层序遍历(队列实现)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void queueFloor(Node head){
        if (head==null) {
            return;
        }
        Queue<Node> q = new LinkedList<>();
        q.add(head);
        while (!q.isEmpty()){
            Node node = q.remove();
            System.out.print(node.value);
            if (node.left!=null) {
                q.add(node.left);
            }
            if (node.right!=null) {
                q.add(node.right);
            }
        }
    }

打印每一层的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static List<List<String>> queueFloorAndPrint(Node head){
        if (head==null) {
            return null;
        }
        List<List<String>> list = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        q.add(head);
        List<String> tmp;
        while (!q.isEmpty()){
            int size = q.size();
            tmp=new ArrayList<>();
            while (size-->0){
                Node node = q.remove();
                System.out.print(node.value);
                tmp.add(node.value);
                if (node.left!=null) {
                    q.add(node.left);
                }
                if (node.right!=null) {
                    q.add(node.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }