二叉树需要声明一个Node节点，包含节点得值，以及左右两个子节点

Node节点代码如下

1
2
3
4
5
6
7
8
9
10
11
12
package com.code.note.tree;

public class Node<T extends Comparable>{
    T value;
    Node left;
    Node right;

    Node(T value) {
        this.value = value;
    }
}

BinaryTree代码如下

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package com.code.note.tree;

import com.code.note.listnode.ListNode;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class BinaryTree<T extends Comparable> {
    private Node<T> root;

    public void put(T value) {
        root = put(root, value);
    }

    private Node<T> put(Node<T> x, T value) {
        if (x == null) {
            return new Node<>(value);
        }
        int cmp = value.compareTo(x.value);
        if (cmp < 0) {
            x.left = put(x.left, value);
        } else if (cmp > 0) {
            x.right = put(x.right, value);
        } else {
            return x;
        }

        return x;
    }

    public void print() {
        BTreePrinter.printNode(root);
    }

    public void traverse() {
        traverse(root);
    }

    public int count() {
        return count(root);
    }

    private int count(Node x) {
        if (x == null) {
            return 0;
        }
        return 1 + count(x.left) + count(x.right);
    }

    private void traverse(Node node) {
        // 前序遍历
        if (node == null) return;
        log.info("{}", node.value);
        traverse(node.left);
        // 中序遍历
        traverse(node.right);
        // 后序遍历
    }

    //反转二叉树
    public void reverse() {
        reverse(root);
    }

    private void reverse(Node x) {

        if (x == null) return;

        Node tmp = x.left;
        x.left = x.right;
        x.right = tmp;

        reverse(x.left);
        reverse(x.right);

    }

    // 树得深度
    public int getDepth() {
        return getDepth(root);
    }

    private int getDepth(Node x) {
        if (x == null) return 0;
        return 1 + Math.max(getDepth(x.left), getDepth(x.right));
    }

    ListNode<Comparable> listNode = new ListNode<>();

    public ListNode toListNode() {

        toListNode(root);
        return listNode;
    }


    // 树转单链表
    private void toListNode(Node node) {
        // 前序遍历
        if (node == null) return;
        listNode.addToTail(node.value);

        toListNode(node.left);
        // 中序遍历
        toListNode(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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package com.code.note.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BTreePrinter {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<Node<T>> newNodes = new ArrayList<Node<T>>();
        for (Node<T> node : nodes) {
            if (node != null) {
                System.out.print(node.value);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("/");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }
}

测试用例

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
27
28
29
30
31
32
33
34
35
package com.code.note.tree;

import lombok.extern.slf4j.Slf4j;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

@Slf4j
public class BinaryTreeTest {
    public static void main(String[] args) {

        BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
        binaryTree.put(3);
        binaryTree.put(5);
        binaryTree.put(1);
        binaryTree.put(2);

        binaryTree.put(10);


        binaryTree.traverse();

        int count = binaryTree.count();
        log.info("count:{}", count);

        int depth = binaryTree.getDepth();
        log.info("depth:{}", depth);


        // 翻转二叉树
        binaryTree.print();
        binaryTree.reverse();
        binaryTree.print();

    }
}

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[2020-11-07 18:04:20,793] [INFO ] [main ] [traverse] [BinaryTree:52] - 3
[2020-11-07 18:04:20,811] [INFO ] [main ] [traverse] [BinaryTree:52] - 1
[2020-11-07 18:04:20,811] [INFO ] [main ] [traverse] [BinaryTree:52] - 0
[2020-11-07 18:04:20,811] [INFO ] [main ] [traverse] [BinaryTree:52] - 2
[2020-11-07 18:04:20,812] [INFO ] [main ] [traverse] [BinaryTree:52] - 5
[2020-11-07 18:04:20,812] [INFO ] [main ] [traverse] [BinaryTree:52] - 4
[2020-11-07 18:04:20,812] [INFO ] [main ] [traverse] [BinaryTree:52] - 10
[2020-11-07 18:04:20,812] [ERROR] [main ] [main] [BinaryTreeTest:25] - count:7
[2020-11-07 18:04:20,839] [ERROR] [main ] [main] [BinaryTreeTest:28] - depth:3
   3       
  / \   
 /   \  
 1   5   
/ \ / \ 
0 2 4 10 
                
[2020-11-07 18:04:20,843] [INFO ] [main ] [traverse] [ListNode:78] - 3
[2020-11-07 18:04:20,843] [INFO ] [main ] [traverse] [ListNode:78] - 1
[2020-11-07 18:04:20,844] [INFO ] [main ] [traverse] [ListNode:78] - 0
[2020-11-07 18:04:20,844] [INFO ] [main ] [traverse] [ListNode:78] - 2
[2020-11-07 18:04:20,844] [INFO ] [main ] [traverse] [ListNode:78] - 5
[2020-11-07 18:04:20,844] [INFO ] [main ] [traverse] [ListNode:78] - 4
[2020-11-07 18:04:20,844] [INFO ] [main ] [traverse] [ListNode:78] - 10