二叉树遍历小结

vvpale 发布于2019-08-16 10:37 / 2447人阅读

摘要：对于任一重合元素，保证所在两个局部遍历有序，保证实现整体遍历有序重合元素所在局部局部全部有序，遍历该元素并出栈局部未全部有序，将未有序局部元素全部入栈。

二叉树遍历小结 声明

文章均为本人技术笔记，转载请注明出处：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

0 二叉树遍历概述

二叉树遍历：按照既定序，对每个节点仅访问一次；
二叉树非递归遍历思想：参考这篇博文，核心思想是存在重合元素的局部有序保证整体有序，由于二叉树的结构特点，二叉树中的每个节点（除根节点和叶子节点）均属于两个局部的重合元素。对于任一重合元素，保证所在两个局部遍历有序，保证实现整体遍历有序；

重合元素所在局部：

局部全部有序，遍历该元素并出栈；

局部未全部有序，将未有序局部元素全部入栈。由于栈是LIFO，局部元素按照逆序入栈；

二叉树节点TreeNode声明

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

1 前序遍历

lintcode 二叉树的前序遍历

1.1 非递归实现

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            // 重合节点完成所有局部有序，弹出
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: right -> left -> root
                if (top.node.right != null) {
                    stack.push(new Pair(top.node.right, false));
                }               
                if (top.node.left != null) {
                    stack.push(new Pair(top.node.left, false));
                }
                stack.push(new Pair(top.node, true));
            }
        }
        return list;
    }
}

1.2 递归实现

public class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayListlist, TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        traverse(list, root.left);
        traverse(list, root.right);
    }
}

2 中序遍历

lintcode 二叉树的中序遍历

2.1 非递归实现

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: right -> root -> left
                if (top.node.right != null) {
                     stack.push(new Pair(top.node.right, false));
                }
                stack.push(new Pair(top.node, true));
                if (top.node.left != null) {
                     stack.push(new Pair(top.node.left, false));
                }
            }
        }
        return list;
    }
}

2.2 递归实现

public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayListlist, TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(list, root.left);
        list.add(root.val);
        traverse(list, root.right);
    }
}

3 后序遍历

lintcode 二叉树的后序遍历

3.1 非递归实现

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: root -> right -> left
                stack.push(new Pair(top.node, true));
                if (top.node.right != null) {
                     stack.push(new Pair(top.node.right, false));
                }
                if (top.node.left != null) {
                     stack.push(new Pair(top.node.left, false));
                }
            }
        }

        return list;
    }
}

3.2 递归实现

public class Solution {
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayList list, TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(list, root.left);
        traverse(list, root.right);
        list.add(root.val);
    }
}

4 层序遍历

lintcode 二叉树的层序遍历，BFS按层遍历实现

public class Solution {
    public ArrayList> levelOrder(TreeNode root) {
        ArrayDeque queue = new ArrayDeque();
        ArrayList> list = new ArrayList>();
        if (root == null) {
            return list;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            int level = queue.size();
            ArrayList levelList = new ArrayList();
            // 按层BFS遍历
            for (int i = 0; i < level; i++) {
                TreeNode head = queue.poll();
                levelList.add(head.val);
                if (head.left != null) {
                    queue.offer(head.left);
                } 
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            list.add(levelList);
        }
        return list;
    }
}

云服务器 GPU云服务器二叉树遍历二叉树的遍历 JS二叉树遍历非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70127.html

学习数据结构与算法之二叉搜索树

摘要：二叉搜索树是二叉树的一种，其特征是左侧子节点存储比父节点小的值，右侧子节点存储比父节点大或等于父节点的值。实现和这个两个方法其实挺简单的，最小的节点就在二叉搜索树的最左反之，最大的就在最右。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构...

denson 2019-08-21 11:54 评论0 收藏0
计算机二级考试-数据结构-模拟试题

摘要：数据结构试题前言这里是数据结构系列文章，主要介绍计算机二级考试中的涉及到数据结构的知识点数据结构在计算机科学中处处都有存在，例如编译系统要使用栈散列表语法树等操作系统要使用队列存储管理表目录树等等。数据结构试题前言这里是数据结构系列文章，主要介绍计算机二级考试中的涉及到数据结构的知识点 /数据结构在计算...

不知名网友 2021-11-26 11:05 评论0 收藏0
Java数据结构与算法——二叉树及操作(包括二叉树遍历)

摘要：本篇主要介绍二叉树的概念二叉树的表示二叉树的操作三种遍历方式实现求二叉树的子树求节点的父节点二叉树高度，可能是考试中的，也可能是面试中的。通常二叉树的遍历根据根节点的遍历次序分为先根遍历中根遍历后根遍历。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作（三种遍历...

muddyway 2019-08-16 11:15 评论0 收藏0
js数据结构和算法（三）二叉树

摘要：同样结点树的二叉树，完全二叉树的深度最小。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。二叉树的概念二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 评论0 收藏0