首页  

二叉树遍历     所属分类 algo 浏览量 823
二叉树 Binary tree

深度遍历 广度遍历
深度遍历 前序 中序 后序 
广度遍历 层次遍历

深度优先遍历 DFS  Depth First Search
广度优先遍历 BFS  Breadth First Search

二叉树的前序 中序 后序遍历,可以认为是深度优先遍历


树递归定义  ,递归实现深度遍历

广度遍历  需要其他数据结构支撑  
譬如 双端队列  ArrayDeque 或 ArrayDeque

前序遍历  根结点 左子树 右子树
中序遍历  左子树 根结点 右子树
后序遍历  左子树 右子树 根结点

前序遍历 递归
public static void preOrderTraverse1(Node root) {
    if (root == null) {
        return;
    }
    System.out.print(root.value + " ");
    preOrderTraverse1(root.left);
    preOrderTraverse1(root.right);
}


基于LinkedList实现的层次遍历

    public static void levelTraversalUseLinkedList(Node root) {
        if (root == null) {
            return;
        }
        LinkedList queue = new LinkedList<>();
        // offer add linkLast
        // queue.offer(root);

        queue.add(root);

        while (!queue.isEmpty()) {
            // poll unlinkFirst
            // Node node = queue.poll();
            // remove removeFirst unlinkFirst
            Node node = queue.remove();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    


例子代码
https://gitee.com/dyyx/algo/blob/master/src/main/java/dyyx/BinaryTreeTravel.java

上一篇     下一篇
Dubbo路由简介

geohash简介

根据经纬度计算距离

快慢指针的妙用

MySQLTEXT类型最大长度

高效会议六大原则