二叉树的三种遍历方式,含demo(递归与非递归)-阿里云开发者社区

开发者社区> 负债程序猿> 正文

二叉树的三种遍历方式,含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~

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

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9473 0
二叉树的非递归遍历
二叉树的非递归遍历 ? java的非递归后续遍历
921 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2920 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的,?mysql的 3306,?mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建. ? have?fun! ?将编程看作是一门艺术,而不单单是个技术。
10839 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11493 0
二叉树遍历非递归算法
递归算法非常的简单。先访问跟节点,然后访问左节点,再访问右节点。如果不用递归,那该怎么做呢?仔细 一.先序遍历   看一下递归程序,就会发现,其实每次都是走树的左分支(left),直到左子树为空,然后开始从递归的最深处返回,然后开始恢复递归现场,访问右子树。
712 0
二叉树的三种遍历方式,含demo(递归与非递归)
前置知识: 什么是二叉树:一个递归的树形数据结构,每个节点最多有两个子节点;二叉树一般都是二分查找树,每个节点的值大于它左子节点的值,小于它右子节点的值
14412 0
二叉树的非递归先序,中序,后序遍历
#include #include #include #include #include using namespace std; struct Tree{ int x; Tree *lchild, *rchild; Tree(){ ...
800 0
+关注
负债程序猿
知道的越多,不知道的越多
118
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载


http://www.vxiaotou.com