栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java 数据结构与算法 二叉树的遍历方式

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java 数据结构与算法 二叉树的遍历方式

树是一种非线性的结构,叫做树是它的结构看起来像一颗倒挂的树。一个结点由一个根节点加上左右子树便成为了二叉树。二叉树在树的有着很重要的位置。大多数题目都是基于二叉树的。

本文主要分享二叉树的几个遍历方式,概念只做简单介绍。二叉树的几个遍历方式如下:

// 前序遍历(递归)
void preOrder(TreeNode root);
// 中序遍历(递归)
void inOrder(TreeNode root);
// 后序遍历(递归)
void postOrde(TreeNode root);
//前序遍历(非递归)
public List preorderTraversal(TreeNode root);
//中序遍历(非递归)
public List inorderTraversal(TreeNode root);
//后序遍历(非递归)
public List postorderTraversal(TreeNode root);
//层序遍历
public List> levelOrder(TreeNode root);

前置说明

二叉树的表示方法很多,我们在做题的时候,常常使用孩子表示法。

class TreeNode {
    int val;//数值域
    TreeNode left;//左孩子(结点)的引用
    TreeNode right;//右孩子(结点)的引用
    public TreeNode(int val) {
        this.val = val;
    }
}

自己来创建一颗二叉树,比如下面的一个二叉树:

这里手动创建一个二叉树。

    public void createTree() {
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(5);
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(7);

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
    }
1、前序遍历(递归)
    public void preOrder(TreeNode root) {
        //如果是空的结点,就返回
        if (root == null) return;
        //你的操作
        System.out.print(root.val + " ");
        //走树的左边
        preOrder(root.left);
        //走树的右边
        preOrder(root.right);
        
    }
2、中序遍历(递归)
    void inOrder(TreeNode root) {
        //如果是空的结点,就返回
        if (root == null) return;
        //先走树的左边
        inOrder(root.left);
        //你的操作
        System.out.print(root.val + " ");
        //走树的右边
        inOrder(root.right);
    }
3、后序遍历(递归)
    void postOrder(TreeNode root) {
        //如果是空的结点,就返回
        if (root == null) return;
        //先走树的左边
        postOrder(root.left);
        //走树的右边
        postOrder(root.right);
        //你的操作
        System.out.print(root.val + " ");
    }
4、前序遍历(非递归)
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if (root == null) {
            return res;
        }

        Deque stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
5、中序遍历(非递归) 
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        if (root == null) return list;
        Stack queue = new Stack<>();
        while (!queue.isEmpty() || root != null) {
            while (root != null) {
                queue.push(root);
                root = root.left;
            }
            root = queue.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
6、后序遍历(非递归)
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if (root == null) {
            return res;
        }

        Stack stack = new Stack<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
7、层序遍历
    public List> levelOrder(TreeNode root) {
        List> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List list = new ArrayList<>();
            while (size > 0) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                } 
                list.add(cur.val);
                --size;
            }
            ret.add(list);
        }
        return ret;
    }

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978195.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号