遍历多叉树

迈不过友情╰ 2023-10-18 09:22 114阅读 0赞

[https://www.jianshu.com/p/dee8284b2dc4][https_www.jianshu.com_p_dee8284b2dc4]

[![96][]][96 1] [beg4][96 1] 关注

2018.03.22 15:14\* 字数 334 阅读 172评论 0喜欢 1

![webp][]

随便画一个树,写代码遍历它

OK,树的结构这么描述

public class TreeNode {
            private String name;
            private TreeNode parent;
            private List<TreeNode> children = new ArrayList<>();
            //setter,getter
    }

#### 递归 ####

public static void Recursion(TreeNode root) {
        System.out.print(root.getName());
        for (TreeNode treeNode : root.getChildren()) {
            Recursion(treeNode);
        }
    }
    //结果为:ABEHIJFCDG

但如果这个树的**非常复杂**,**非常深**,该怎么办?

递归这种方式有什么缺点?

先从jvm的栈讲起,先来一张栈帧的结构图

![webp 1][]

每当启动一个新线程的时候,java虚拟机都会为它分配一个java栈。java以栈帧为单位保存线程的运行状态。虚拟机只会对java栈执行两种操作：以栈帧为单位的压栈或者出栈。

通俗点说,每个方法就是一个栈帧,方法要执行就得压栈,return或者抛异常了就出栈.

递归就会在当前线程的栈中不断的入栈,入的多了就爆了,就会抛出java.lang.StackOverflowError

另外,对于一个方法,内存调用是这样的

![webp 2][]

刚才在栈帧中的局部变量,如果是对象就会是一个引用,ref只有4byte,但对象本身会在堆(heap)中创建,递归执行完了,出栈了,栈不用管了,但堆里面的对象就得等GC了.

这么一说,递归还真不好用呢,所以非递归方式怎么写呢?  
遍历有两种方式,广度优先和深度优先

#### 广度优先 ####

/**
     * 广度优先需要构建一个先进先出的队列
     *
     * @param root
     */
    public static void breadthFirst(TreeNode root) {
        Deque<TreeNode> nodeDeque = new LinkedList<>();
        TreeNode node = root;
        nodeDeque.push(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            System.out.print(node.getName());
            for (TreeNode treeNode : node.getChildren()) {
                nodeDeque.addLast(treeNode);
            }
        }
    }
    //结果为ABCDEFGHIJ

#### 深度优先 ####

/**
     * 深度优先需要构建一个后进先出的栈,
     * 不使用Stack是因为java的Stack功能略多
     *
     * @param root
     */
    public static void depthFirst(TreeNode root) {
        Deque<TreeNode> nodeDeque = new LinkedList<>();
        TreeNode node = root;
        nodeDeque.push(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            System.out.print(node.getName());
            for (TreeNode treeNode : node.getChildren()) {
                nodeDeque.push(treeNode);
            }
        }
    }
    //结果为ADGCBFEJIH

[https_www.jianshu.com_p_dee8284b2dc4]: https://www.jianshu.com/p/dee8284b2dc4
[96]: https://upload.jianshu.io/users/upload_avatars/10885509/44640234-ffd0-4fdf-a7cb-58e22a65210c?imageMogr2/auto-orient/strip%7CimageView2/1/w/96/h/96
[96 1]: https://www.jianshu.com/u/bc6c29ae28ee
[webp]: https://upload-images.jianshu.io/upload_images/10885509-66080fd82625e1bb.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/393/format/webp
[webp 1]: https://upload-images.jianshu.io/upload_images/10885509-52dabb5995deb7d9..png?imageMogr2/auto-orient/strip%7CimageView2/2/w/642/format/webp
[webp 2]: https://upload-images.jianshu.io/upload_images/10885509-550989b899c08176?imageMogr2/auto-orient/strip%7CimageView2/2/w/404/format/webp