开发者社区> 负债程序猿> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

二叉树的三种遍历方式,含demo(递归与非递归)

简介: 前置知识: 什么是二叉树:一个递归的树形数据结构,每个节点最多有两个子节点;二叉树一般都是二分查找树,每个节点的值大于它左子节点的值,小于它右子节点的值
+关注继续查看
(福利推荐:你还在原价购买阿里云服务器?现在阿里云0.8折限时抢购活动来啦!4核8G企业云服务器仅998元/3年,立即抢购>>>:9i0i.cn/aliyun

福利推荐:阿里云、腾讯云、华为云等大品牌云产品全线2折优惠活动来袭,4核8G云服务器899元/3年,新老用户共享优惠,点击这里立即抢购>>>

前置知识:

什么是二叉树:一个递归的树形数据结构,每个节点最多有两个子节点;二叉树一般都是二分查找树,每个节点的值大于它左子节点的值,小于它右子节点的值

20210308122821282.png

二叉树遍历:

递归遍历:


前序遍历:先访问根节点,再访问左子节点,最后访问右子节点

上图中前序遍历结果:30、20、5、28、50、38、58


中序遍历:先访问左子节点,再访问根节点,最后访问右子节点

上图中中序遍历结果:5、20、28、30、38、50、58


后序遍历:先访问左子节点,再访问右子节点,最后访问根节点

上图中后序遍历结果:5、28、20、38、58、50、30


非递归遍历:


常用的是利用栈的先进后出特性,不断地将节点入栈,然后再出栈

非递归前序遍历和非递归中序遍历两种方式很好理解,控制遍历时机即可,而非递归后序遍历较为复杂,需要额外维护一个最后访问节点


二叉树demo


详细实现原理都在注释中,花了几天写的,球球你好好看看,来都来了

public class MyBinaryTree {
    //根节点
    private MyNode root;

    //注意,这是私有方法,对用户开放的新增方法在下面,其它几个方法也是
    private MyNode addNode(MyNode current, int value) {
        //如果根节点为空,直接new个新节点
        if (current == null) return new MyNode(value);
        if (value < current.value) {
            //如果当前插入节点的值小于根节点,则在树的左边递归插入
            current.left = addNode(current.left, value);
        } else if (value > current.value) {
            //如果当前插入节点的值大于根节点,则在树的右边递归插入
            current.right = addNode(current.right, value);
        } else {
            //如果等于,直接返回
            return current;
        }
        return current;
    }

    public void addNode(int value) {
        //指定当前根节点
        root = addNode(root, value);
    }

    private boolean isContainNode(MyNode current, int value) {
        //如果当前根节点不存在,直接返回false
        if (current == null) return false;
        //如果根节点存在并且值等于当前查找值,返回true
        if (current.value == value) return true;
        //如果目标值大于当前节点值,则在右子树递归查找,反之在左子树递归查找
        return value > current.value ? isContainNode(current.right, value) : isContainNode(current.left, value);
    }

    public boolean isContainNode(int value) {
        //从根节点开始找
        return isContainNode(root, value);
    }

    //删除节点比较复杂,或许会让你看了以后疯狂怀疑自己,请酌情查看
    private MyNode deleteNode(MyNode current, int value) {
        //如果节点不存在,就不删咯
        if (!isContainNode(value) || current == null) return null;
        //如果目标节点等于根节点
        if (current.value == value) {
            //目标节点无子节点,直接删除目标节点
            if (current.left == null && current.right == null) return null;
            //目标节点只有左子节点,直接删除目标节点,并将目标节点的父节点指向左子节点
            if (current.right == null) return current.left;
            //目标节点只有右子节点,直接删除目标节点,并将目标节点的父节点指向右子节点
            if (current.left == null) return current.right;
            //目标节点既有左子节点又有右子节点,这种比较复杂
            //需要将目标节点右子节点的最左节点,或者目标节点左子节点的最右节点替换成目标节点,然后将目标节点删除
            //我们这里是替换目标节点右子节点的最左节点,所以需要找到目标节点右子节点下面最小的那个节点,即左最节点
            int i = findSmallerNode(current.right);
            //将目标节点替换成找到的最左节点
            current.value = i;
            //递归删除,满足上面能删除的三种情况
            current.right = deleteNode(current.right, i);
            return current;
        } else if (current.value > value) {
            current.left = deleteNode(current.left, value);
            return current;
        } else {
            current.right = deleteNode(current.right, value);
            return current;
        }
    }

    public boolean deleteNode(int value) {
        MyNode node = deleteNode(root, value);
        if (node == null) return false;
        return true;
    }

    //中序递归遍历
    private void centerShow(MyNode root) {
        if (root != null) {
            //先递归遍历左子树
            centerShow(root.left);
            //遍历根节点
            System.out.print(root.value + " ");
            //再递归遍历右子树
            centerShow(root.right);
        }
    }

    public void centerShow() {
        System.out.print("\n中序递归遍历:");
        centerShow(root);
    }

    public void centerShowPro() {
        System.out.print("\n中序非递归遍历:");
        //利用栈的先进后出
        Stack<MyNode> nodeStack = new Stack<>();
        while (root != null || !nodeStack.isEmpty()) {
            //将根节点遍历入栈
            while (root != null) {
                nodeStack.push(root);
                root = root.left;
            }
            //取出栈顶元素作为根节点并删除栈顶元素,此时栈顶元素为最左节点的值
            root = nodeStack.pop();
            //遍历左节点,因为是从根往左入栈,所以出栈是从左到根
            System.out.print(root.value + " ");
            //找到下一个节点,依次往右遍历
            root = root.right;
        }
    }

    private void preShow(MyNode root) {
        if (root != null) {
            //先遍历根节点
            System.out.print(root.value + " ");
            //然后遍历左节点
            preShow(root.left);
            //再遍历右节点
            preShow(root.right);
        }
    }

    public void preShow() {
        System.out.print("\n先序递归遍历:");
        preShow(root);
    }

    public void preShowPro() {
        System.out.print("\n先序非递归遍历:");
        Stack<MyNode> nodeStack = new Stack<>();
        while (root != null || !nodeStack.isEmpty()) {
            while (root != null) {
                //同中序非递归遍历,只是这里先遍历根节点
                System.out.print(root.value + " ");
                nodeStack.push(root);
                root = root.left;
            }
            root = nodeStack.pop();
            root = root.right;
        }
    }

    private void afterShow(MyNode root) {
        if (root != null) {
            afterShow(root.left);
            afterShow(root.right);
            System.out.print(root.value + " ");
        }
    }

    public void afterShow() {
        System.out.print("\n后序递归遍历:");
        afterShow(root);
    }

    public void afterShowPro() {
        System.out.print("\n后序非递归遍历:");
        Stack<MyNode> nodeStack = new Stack<>();
        MyNode lastNode = null;
        while (root != null || !nodeStack.isEmpty()) {
            while (root != null) {
                nodeStack.push(root);
                root = root.left;
            }
            //取出栈顶元素但不删除
            root = nodeStack.peek();
            //如果栈顶元素的右节点为空或者它是最后一次访问的节点
            if (root.right == null || root.right == lastNode) {
                //遍历当前节点
                System.out.print(root.value + " ");
                lastNode = nodeStack.pop();
                root = null;
            } else {
                root = root.right;
            }
        }
    }

    private int findSmallerNode(MyNode root) {
        //删除节点用的,用来找到节点的最左子节点
        return root.left == null ? root.value : findSmallerNode(root.right);
    }

    //节点,为了演示方便,只支持存放int数字
    private class MyNode {
        private int value;
        private MyNode left;
        private MyNode right;

        public MyNode(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
}

测试:

public class MyBinaryTest {
    public static void main(String[] args) {
        deleteTest();
        testPre();
        testPrePro();
        testCenter();
        testCenterPro();
        testAfter();
        testAfterPro();
    }

    public static void deleteTest() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        System.out.println("是否存在28:"+tree.isContainNode(28));
        tree.deleteNode(28);
        System.out.println("删除28后是否还存在28:"+tree.isContainNode(28));
    }

    public static void testCenter() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        tree.centerShow();
    }

    public static void testCenterPro() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        tree.centerShowPro();
    }

    public static void testPre() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        tree.preShow();
    }

    public static void testPrePro() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        tree.preShowPro();
    }

    public static void testAfter() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        tree.afterShow();
    }

    public static void testAfterPro() {
        MyBinaryTree tree = new MyBinaryTree();
        tree.addNode(30);
        tree.addNode(20);
        tree.addNode(5);
        tree.addNode(28);
        tree.addNode(50);
        tree.addNode(38);
        tree.addNode(58);
        tree.afterShowPro();
    }

}

运行结果:

是否存在28:true
删除28后是否还存在28:false

先序递归遍历:30 20 5 28 50 38 58 
先序非递归遍历:30 20 5 28 50 38 58 
中序递归遍历:5 20 28 30 38 50 58 
中序非递归遍历:5 20 28 30 38 50 58 
后序递归遍历:5 28 20 38 58 50 30 
后序非递归遍历:5 28 20 38 58 50 30 

还是那句话,家里有条件的一定一定一定复制到idea跑一跑

ok我话说完,skr~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
再次搞定 Ali 云函数计算 FC
原本早就该写完了微信 SDK 授权服务上云计划由于对 Ali 云函数计算 FC 的不熟悉遇到了很多的坑,再前面的文章中还吐槽了一通。在服务顺利跑通后,这回实打实的来总结一下顺利上云的保守指南~
22904 0
特稿|过去5年,阿里云是如何打造云原生数据库PolarDB的
阿里云在云原生数据库领域的自研创新突围。
23650 0
初识Serverless函数计算
Serverless 并不是没有服务器,而是开发者不再需要关心服务器。在传统 Serverful 架构下,部署一个应用需要购买服务器,部署操作系统,搭建开发环境,编写代码,构建应用,部署应用,配置负载均衡机制,搭建日志分析与监控系统,应用上线后,继续监控应用的运行情况。而在 Serverless 架构下,开发者只需要关注应用的开发构建和部署,无需关心服务器相关操作与运维,在函数计算架构下,开发者只需要编写业务代码并监控业务运行情况。这将开发者从繁重的运维工作中解放出来,把精力投入到更有意义的业务开发上。
26762 0
如何优雅的消除系统重复代码
在程序猿的日常工作中,不仅要跟随业务侧的发展不断开发新的需求,同时也需要维护老的已有平台。无论是开发新需求还是维护老系统,我们都会遇到同样一个问题,系统中总是充斥着很多重复的代码。
24278 0
【AI征文】对DeepRec认识以及了解
对DeepRec认识以及了解
76967 0
业务中台之上的低代码应用开发平台
中台低代码平台帮助开发者掌握全栈能力,促进开发者提高工作效率,基于企业数字化业务能力组件,可以实现业务应用的敏捷按需装配,成为企业组装式应用创新平台,进而实现企业业务能力的持续优化和复用,促进从组织到企业甚至行业的业务能力集约与创新。
112681 0
Tensorflow Serving部署模型与调用
本文以mnist为数据集,使用keras 构建CNN网络,将训练获取的模型通过Tensorflow Serving方式部署提供Rest Full接口,分别使用PostMan和Python调用服务,代码编辑调试使用阿里云PAI DSW实例,模型部署使用阿里云ECS虚拟机。
6090 0
十分钟生成影视级室内设计效果,红星美凯龙设计云如何升级传统家居行业
依托于阿里云强大的弹性云上GPU算力,红星美凯龙可以为客户提供快速的、高质量的渲染,实现秒级的门店快速设计。
69101 0
+关注
负债程序猿
知道的越多,不知道的越多
119
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载


http://www.vxiaotou.com