搜索
首页Javajava教程Java中二叉树的基础知识及概念是什么?

    1. 树型结构

    1.1概念

    树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。

    Java中二叉树的基础知识及概念是什么?

    1.2 概念(重要)

    a.节点的度:该节点子树的个数;如上图:A的度为6,J的度为2

    b.树的度:该树中,最大结点的度就是该数的度;如上图:树的度为6

    c.叶子节点(终端节点):度为0的节点(没有子树的节点)

    d.双亲结点/父节点:如上图:D是H的父节点

    孩子节点/子节点:如上图:H是D的子节点

    e.根节点:没有双亲的节点;如上图:A

    f.节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

    g.树的高度或深度:树中节点的最大层次; 如上图:树的高度为4

    2. 二叉树(重点)

    2.1 概念

    每个节点最多只有两颗子树,度

    2.2 二叉树的基本形态

    Java中二叉树的基础知识及概念是什么?

    2.3 两种特殊的二叉树

    Java中二叉树的基础知识及概念是什么?

    a.满二叉树:非子叶度都为2

    b.完全二叉树:满二叉树缺了“右下角”

    2.4 二叉树的性质

    a.满二叉树

    1.高度为K,则有2^k-1个节点

    2.层次为K,则该层有2^(k-1)个节点

    3.边个数 = 节点个数 - 1

    4.度为0有n0个,度为2有n2个,则 n0 = n2 1

    b.完全二叉树

    1.有右孩子必有左孩子

    2.只可能有一个度为1的节点

    2.5 二叉树的存储

    二叉树的存储结构分为:顺序存储和类似于链表的链式存储。

    顺序存储:只能存完全二叉树

    链式存储:普通二叉树

    本次展示链式存储

    二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式 ,

    Java中二叉树的基础知识及概念是什么?

    以此图为例, 具体如下:

    // 孩子表示法
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
     
        public TreeNode(char val) {
            this.val = val;
        }
    }

    初始化:

        public static TreeNode build(){
            TreeNode nodeA=new TreeNode('A');
            TreeNode nodeB=new TreeNode('B');
            TreeNode nodeC=new TreeNode('C');
            TreeNode nodeD=new TreeNode('D');
            TreeNode nodeE=new TreeNode('E');
            TreeNode nodeF=new TreeNode('F');
            TreeNode nodeG=new TreeNode('G');
            TreeNode nodeH=new TreeNode('H');
            nodeA.left=nodeB;
            nodeA.right=nodeC;
            nodeB.left=nodeD;
            nodeB.right=nodeE;
            nodeE.right=nodeH;
            nodeC.left=nodeF;
            nodeC.right=nodeG;
            return nodeA;
        }

    2.6 二叉树的基本操作

    2.6.1 二叉树的遍历 (递归)

    1. NLR :前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点 ---> 根的左子树 ---> 根的右子树。

        //先序遍历 : 根左右
        public static void preOrder(TreeNode root){
            if(root==null){
                return;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

    2. LNR :中序遍历 (Inorder Traversal)—— 根的左子树 ---> 根节点 ---> 根的右子树。

        //中序遍历
        public static void inOrder(TreeNode root){
            if(root==null){
                return;
            }
            preOrder(root.left);
            System.out.print(root.val+" ");
            preOrder(root.right);
        }

    3. LRN :后序遍历 (Postorder Traversal)—— 根的左子树 ---> 根的右子树 ---> 根节点。

        //后序遍历
        public static void postOrder(TreeNode root){
            if(root==null){
                return;
            }
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(root.val+" ");
        }

    2.6.2 二叉树的遍历 (迭代)

    1.前序遍历

        //方法2(迭代)
        //先序遍历 (迭代)
        public static void preOrderNonRecursion(TreeNode root){
            if(root==null){
                return ;
            }
            Deque<TreeNode> stack=new LinkedList<>();
            stack.push(root);
            while (!stack.isEmpty()){
                TreeNode cur=stack.pop();
                System.out.print(cur.val+" ");
                if(cur.right!=null){
                    stack.push(cur.right);
                }
                if(cur.left!=null){
                    stack.push(cur.left);
                }
            }
        }

    2.中序遍历

        //方法2(迭代)
        //中序遍历 (迭代)
        public static void inorderTraversalNonRecursion(TreeNode root) {
            if(root==null){
                return ;
            }
     
            Deque<TreeNode> stack=new LinkedList<>();
            // 当前走到的节点
            TreeNode cur=root;
            while (!stack.isEmpty() || cur!=null){
                // 不管三七二十一,先一路向左走到根儿~
                while (cur!=null){
                    stack.push(cur);
                    cur=cur.left;
                }
                // 此时cur为空,说明走到了null,此时栈顶就存放了左树为空的节点
                cur=stack.pop();
                System.out.print(cur.val+" ");
                // 继续访问右子树
                cur=cur.right;
            }
        }

    3.后序遍历

        //方法2(迭代)
        //后序遍历 (迭代)
        public static void postOrderNonRecursion(TreeNode root){
            if(root==null){
                return;
            }
            Deque<TreeNode> stack=new LinkedList<>();
            TreeNode cur=root;
            TreeNode prev=null;
     
            while (!stack.isEmpty() || cur!=null){
                while (cur!=null){
                    stack.push(cur);
                    cur=cur.left;
                }
     
                cur=stack.pop();
                if(cur.right==null || prev==cur.right){
                    System.out.print(cur.val+" ");
                    prev=cur;
                    cur=null;
                }else {
                    stack.push(cur);
                    cur=cur.right;
                }
            }
        }

    2.6.3 二叉树的基本操作

    1.求结点个数(递归&迭代)

        //方法1(递归)
        //传入一颗二叉树的根节点,就能统计出当前二叉树中一共有多少个节点,返回节点数
        //此时的访问就不再是输出节点值,而是计数器 + 1操作
        public static int getNodes(TreeNode root){
            if(root==null){
                return 0;
            }
            return 1+getNodes(root.left)+getNodes(root.right);
        }
     
        //方法2(迭代)
        //使用层序遍历来统计当前树中的节点个数
        public static int getNodesNoRecursion(TreeNode root){
            if(root==null){
                return 0;
            }
            int size=0;
            Deque<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                size++;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            return size;
        }

    2.求叶子结点个数(递归&迭代)

        //方法1(递归)
        //传入一颗二叉树的根节点,就能统计出当前二叉树的叶子结点个数
        public static int getLeafNodes(TreeNode root){
            if(root==null){
                return 0;
            }
            if(root.left==null && root.right==null){
                return 1;
            }
            return getLeafNodes(root.left)+getLeafNodes(root.right);
        }
     
        //方法2(迭代)
        //使用层序遍历来统计叶子结点的个数
        public static int getLeafNodesNoRecursion(TreeNode root){
            if(root==null){
                return 0;
            }
            int size=0;
            Deque<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                TreeNode cur=queue.poll();
                if(cur.left==null && cur.right==null){
                    size++;
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            return size;
        }

    3.求第 k 层结点个数

        //求出以root为根节点的二叉树第k层的节点个数
        public static int getKLevelNodes(TreeNode root,int k){
            if(root==null || k<=0){
                return 0;
            }
            if(k==1){
                return 1;
            }
            return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
        }

    4.求树的高度

        //传入一个以root为根节点的二叉树,就能求出该树的高度
        public static int height(TreeNode root){
            if(root==null){
                return 0;
            }
            return 1+ Math.max(height(root.left),height(root.right));
        }

    5.判断二叉树数中是否存在值为value的节点

        //判断当前以root为根节点的二叉树中是否包含指定元素val,
        //若存在返回true,不存在返回false
        public static boolean contains(TreeNode root,char value){
            if(root==null){
                return false;
            }
            if(root.val==value){
                return true;
            }
            return contains(root.left,value) || contains(root.right,value);
        }

    2.7 二叉树的层序遍历

        //层序遍历
        public static void levelOrder(TreeNode root) {
            if(root==null){
                return ;
            }
     
            // 借助队列来实现遍历过程
            Deque<TreeNode> queue =new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode cur=queue.poll();
                    System.out.print(cur.val+" ");
                    if(cur.left!=null){
                        queue.offer(cur.left);
                    }
                    if(cur.right!=null){
                        queue.offer(cur.right);
                    }
                }
            }
        }

    以上是Java中二叉树的基础知识及概念是什么?的详细内容。更多信息请关注PHP中文网其他相关文章!

    声明
    本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
    云计算如何影响Java平台独立性的重要性?云计算如何影响Java平台独立性的重要性?Apr 22, 2025 pm 07:05 PM

    云计算显着提升了Java的平台独立性。 1)Java代码编译为字节码,由JVM在不同操作系统上执行,确保跨平台运行。 2)使用Docker和Kubernetes部署Java应用,提高可移植性和可扩展性。

    Java的平台独立性在广泛采用中扮演着什么角色?Java的平台独立性在广泛采用中扮演着什么角色?Apr 22, 2025 pm 06:53 PM

    Java'splatformindependenceallowsdeveloperstowritecodeonceandrunitonanydeviceorOSwithaJVM.Thisisachievedthroughcompilingtobytecode,whichtheJVMinterpretsorcompilesatruntime.ThisfeaturehassignificantlyboostedJava'sadoptionduetocross-platformdeployment,s

    容器化技术(例如Docker)如何影响Java平台独立性的重要性?容器化技术(例如Docker)如何影响Java平台独立性的重要性?Apr 22, 2025 pm 06:49 PM

    容器化技术如Docker增强而非替代Java的平台独立性。1)确保跨环境的一致性,2)管理依赖性,包括特定JVM版本,3)简化部署过程,使Java应用更具适应性和易管理性。

    Java运行时环境(JRE)的关键组件是什么?Java运行时环境(JRE)的关键组件是什么?Apr 22, 2025 pm 06:33 PM

    JRE是Java应用程序运行的环境,其作用是让Java程序在不同操作系统上运行无需重新编译。JRE的工作原理包括JVM执行字节码、类库提供预定义类和方法、配置文件和资源文件设置运行环境。

    解释JVM如何处理内存管理,而不论基础操作系统如何。解释JVM如何处理内存管理,而不论基础操作系统如何。Apr 22, 2025 pm 05:45 PM

    JVM通过自动内存管理和垃圾回收确保Java程序高效运行。1)内存分配:为新对象在堆中分配内存。2)引用计数:跟踪对象引用,检测垃圾。3)垃圾回收:使用标记-清除、标记-整理或复制算法回收不再引用的对象。

    IntelliJ IDEA是如何在不输出日志的情况下识别Spring Boot项目的端口号的?IntelliJ IDEA是如何在不输出日志的情况下识别Spring Boot项目的端口号的?Apr 19, 2025 pm 11:45 PM

    在使用IntelliJIDEAUltimate版本启动Spring...

    如何优雅地获取实体类变量名构建数据库查询条件?如何优雅地获取实体类变量名构建数据库查询条件?Apr 19, 2025 pm 11:42 PM

    在使用MyBatis-Plus或其他ORM框架进行数据库操作时,经常需要根据实体类的属性名构造查询条件。如果每次都手动...

    See all articles

    热AI工具

    Undresser.AI Undress

    Undresser.AI Undress

    人工智能驱动的应用程序,用于创建逼真的裸体照片

    AI Clothes Remover

    AI Clothes Remover

    用于从照片中去除衣服的在线人工智能工具。

    Undress AI Tool

    Undress AI Tool

    免费脱衣服图片

    Clothoff.io

    Clothoff.io

    AI脱衣机

    Video Face Swap

    Video Face Swap

    使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

    热工具

    Atom编辑器mac版下载

    Atom编辑器mac版下载

    最流行的的开源编辑器

    SublimeText3 英文版

    SublimeText3 英文版

    推荐:为Win版本,支持代码提示!

    mPDF

    mPDF

    mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

    DVWA

    DVWA

    Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

    MinGW - 适用于 Windows 的极简 GNU

    MinGW - 适用于 Windows 的极简 GNU

    这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。