用Java实现一个简单二叉树-阿里云开发者社区

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

用Java实现一个简单二叉树

简介: 前置知识: 什么是二叉树:一个递归的树形数据结构,每个节点最多有两个子节点;二叉树一般都是二分查找树,每个节点的值大于它左子节点的值,小于它右子节点的值
+关注继续查看

前置知识:

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

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 管理控制台上修改实例登录密码。
10089 0
认识红黑树,解决二叉树删除后遗症 | 带你学《Java语言高级特性》之四十一
在上一节的学习中不难发现,二叉树节点增减后,其结构可能会发生左右子树不平衡的问题,导致其查找效率大打折扣。本节将为读者介绍红黑树的概念及其对于二叉树来说增加的内容与节点规则。
1180 0
浅谈二叉树节点删除之道 | 带你学《Java语言高级特性》之四十
二叉树能够提升查询效率得益于其特殊的结构,而删除节点意味着其他节点也将受到影响,删除的节点的位置也决定了该次删除操作的复杂程度。本节将具体介绍二叉树删除节点功能的实现。
1116 0
【leetcode刷题】27.二叉树的直径——Java版
⭐欢迎订阅《leetcode》专栏,每日一题,每天进步⭐ 可以将二叉树的直径转换为:二叉树的每个节点的左右子树的高度和的最大值。 ——leetcode此题热评
11 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13891 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11893 0
javascript二叉树基本功能实现
都是常用的功能。 删除是最复杂的。。 test function BinarySearchTree(){ var Node = function(key){ this.
838 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7365 0
+关注
负债程序猿
知道的越多,不知道的越多
119
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础HTML入门教程》
立即下载
《零基础CSS入门教程》
立即下载