Java实现树的遍历及二叉树可视化
数据结构和算法
12 分钟 读完 (大约 1868 个字) 0次访问

Java实现树的遍历及二叉树可视化

1. 树的遍历说明

  • 前序遍历（根左右）

  • 中序遍历（左根右）

  • 后序遍历（左右根）

  • 层次遍历（一层层）

层次遍历使用的是BFS，而前中后是DFS，所以单独开一篇

不难发现，其实名字中的“前中后”指的是“根”的位置

2. java实现（递归和栈）

递归方式我就不多说了，栈方式的话按照如下顺序：

根节点入栈

进入左节点，节点不为空则入栈，重复直到节点为空则出栈（此时出的这个是最后一个不为空的节点）

进入右节点，节点不为空则入栈，重复直到栈为空结束

通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private List<Integer> res = new ArrayList<>();
public List<Integer> traversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
	
    while (!stack.empty() || root != null){
        if(root!=null){
            stack.push(root);
            root = root.left;
        }else {
            root = stack.pop();
            root = root.right;
        }
    }
    return res;
}

不要乱写代码，直接背下这套模板，前中后序遍历只差一句res.add(root.val);只是位置不同而已

2.1 前序遍历

力扣原题https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    private List<Integer> res = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if(root != null){
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return res;
    }
}

栈方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private List<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();

        while(!stack.empty() || root != null){
            if (root != null){
                res.add(root.val);	//前序加在这里
                stack.push(root);
                root = root.left;
            }else {
                root = stack.pop();
                root = root.right;
            }
        }
        return res;
    }
}

2.2 中序遍历

力扣原题https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

递归方式

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    private List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root != null){
            inorderTraversal(root.left);
            res.add(root.val);
            inorderTraversal(root.right);
        }
        return res;
    }
}

栈方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        
        while(!stack.empty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else {
                root = stack.pop();
                res.add(root.val);		//中序加在这里
                root = root.right;
            }
        }
        return res;
    }
}

2.3 后序遍历

递归方式

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    private List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root != null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            res.add(root.val);
        }
        return res;
    }
}

栈方式

后序遍历使用栈方式有点不同，栈方式都是：根节点入栈，左节点入栈出栈，右节点入栈出栈。res.add(root.val);前序只需要加在根节点入栈前，中序只需要加在右节点出栈前。而对于后序遍历，按理来说应该加载右节点出栈后，但是左节点出栈和右节点出栈都是同一段代码段，我们无法判断root = stack.pop();是左节点出栈还是右节点出栈，因此我们要在右节点入栈时记录下来，如果出栈时==记录，那么说明是右节点出栈。

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
class Solution {
	private List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode stored = null;     //用来记录右节点
        
        while(!stack.empty() || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.peek();	//这里不同，不要直接pop
                if (root.right == null || root.right == stored){    //这就说明是右节点已经遍历过了，准备出栈了
                    res.add(root.val);	//后序加在这里
                    stack.pop();
                    stored = root;	//记录下来
                    root = null;
                }else {
                    root = root.right;
                }
            }
        }
        return res;
    }
}

当然，如果你只记得模板，没关系，我们可以将前序遍历改造成根右左（root = root.left和root.right换一下位置），然后reverse这个列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();

        while(!stack.empty() || root != null){
            if (root != null){
                res.add(root.val);	//前序加在这里
                stack.push(root);
                root = root.right;	//先右
            }else {
                root = stack.pop();
                root = root.left;	//再左
            }
        }
        // 精髓！ -- 换一种思路来解题 -- 通过一个方向相反的近似解，最后在答案基础上做反转
        // 反转结果，得到 ： 左 -> 右 -> 根
        Collections.reverse(res);
        return res;
    }
}

这篇文章对栈的说明写的非常不错https://www.cnblogs.com/bigsai/p/11393609.html


2.4 层次遍历

层次遍历和前中后序思想和写法都完全不同

前中后序：DFS/栈

层次遍历：BFS和队列

专门开了一篇来写层次遍历 –> 传送门


附录 其他写法

1. 颜色标记法（大佬说可以前中后序遍历都相同的代码）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack,rst = [root],[]
        while stack:
            i = stack.pop()
            if isinstance(i,TreeNode):
                stack.extend([i.right,i.val,i.left])
            elif isinstance(i,int):
                rst.append(i)
        return rst

java实现详见

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/


2. 另一套模板

网上有些很简洁的版本，这个风格我是比较喜欢的，前序如下，自己摸索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null) return list;	//力扣专属测试用例
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node == null) continue;
            // 这样的输出顺序是：根 -> 左 -> 右
            list.add(node.val);
            stack.push(node.right);
            stack.push(node.left);
        }
        return list;
    }
}

3. 二叉树的可视化

根据网上的代码修改而成，完美切合力扣格式，有时候在力扣做算法题时，在测试的时候通常要先构造一棵树，但是又没办法查看就很无奈，创建两个类

代码已经上传到github，附带一个力扣题目作为demo，https://github.com/wjwABCDEFG/TreeUtil

以下是代码关键部分解释说明

为了匹配任何类型，这里用了泛型

1
2
3
4
5
6
7
8
9
10
11
/**
 * 树节点
 */
public class Node<T extends Comparable<?>> {
    public Node<T> left, right;
    public T data;

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

TreeVisualUtil代码，直接复制即可食用，要改的地方我用注释标好了

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
109
110
111
112
113
114
115
116
117
import org.junit.Test;

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

public class TreeVisualUtil {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = TreeVisualUtil.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() || TreeVisualUtil.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;

        TreeVisualUtil.printWhitespaces(firstSpaces);

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

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

        for (int i = 1; i <= endgeLines; i++) {
            for (Node<T> node : nodes) {
                TreeVisualUtil.printWhitespaces(firstSpaces - i);
                if (node == null) {
                    TreeVisualUtil.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (node.left != null) {
                    System.out.print("/");
                } else {
                    TreeVisualUtil.printWhitespaces(1);
                }

                TreeVisualUtil.printWhitespaces(i + i - 1);

                if (node.right != null) {
                    System.out.print("\\");
                } else {
                    TreeVisualUtil.printWhitespaces(1);
                }

                TreeVisualUtil.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(TreeVisualUtil.maxLevel(node.left), TreeVisualUtil.maxLevel(node.right)) + 1;
    }

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

        return true;
    }

    /**
     * 只需要修改这里按部就班构造自己的树，运行main方法即可
     */
    private static Node<String> myTree() {
        Node<String> root = new Node<>("A");
        root.left = new Node<>("B");
        root.right = new Node<>("C");
        root.left.left = new Node<>("D");
        root.left.right = new Node<>("E");
        root.left.right.left = new Node<>("F");

        return root;
    }

    @Test
    public void test() {
        //要在别的类中使用只需要调用下面这句话即可，参数传入自己的root节点
        TreeVisualUtil.printNode(myTree());
    }
}

效果如下，还不错！


其他树的题目点击这里

#
根据两序遍历推出第三序以及构建树
java主动发送http请求
关注我

分类

标签云

DL/ML http lintcode markdown mysql spring springcloud 二分查找 剑指offer 力扣 加密 动态规划 单调栈 回溯 字符串 学习记录 开发 排序 数据结构 栈 树 游戏和引擎 笔试 笔试面试 算法 递归

推荐阅读

推荐阅读

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×