【java数据结构-二叉树(上)】

java数据结构-二叉树(上)

  • 二叉树的概念
    • 二叉树的节点介绍
  • 二叉树构造
    • 如何使用兄弟表示法构造二叉树
    • 两种特别的二叉树
    • 二叉树的基本性质:
  • 二叉树的存储
  • 二叉树的遍历:
    • 前序遍历:
    • 中序遍历:
    • 后序遍历:
    • 层序遍历
  • 二叉树的基础操作

在这里插入图片描述
🔥个人主页: 努力学编程’
🔥内容管理: java数据结构
请添加图片描述

hello,今天带大家学习数据结构中非常重要的一个知识点二叉树,二叉树主体的实现使用的是递归的知识,通过二叉树我们可以更好的理解递归的应用。今天就带大家学习一下二叉树的一些知识。

二叉树的概念

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

  • 有一个特殊的结点,称为根结点,根结点没有前驱结点

  • 除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm,其中每一个集合Ti (1 <= i <=
    m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

  • 树是递归定义的

在这里插入图片描述

二叉树的节点介绍

在这里插入图片描述

  • 结点的度:一个结点含有子树的个数称为该结点的度; 如上图:A的度为6

  • 树的度:一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6

  • 叶子结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I…等节点为叶结点

  • 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点

  • 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点

  • 根结点:一棵树中,没有双亲结点的结点;如上图:A

  • 结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推

  • 树的高度或深度:树中结点的最大层次; 如上图:树的高度为4
    树的以下概念只需了解,在看书时只要知道是什么意思即可:

  • 非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G…等节点为分支结点

  • 兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点

  • 堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为兄弟结点

  • 结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先

  • 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙

  • 森林:由m(m>=0)棵互不相交的树组成的集合称为森林.

二叉树构造

那么如何构造一个二叉树呢?
实际中树有很多种表示方式,如:双亲表示法孩子表示法孩子双亲表示法孩子兄弟表示法 等等。我们这里就简单的了解其中最常用的孩子兄弟表示法

如何使用兄弟表示法构造二叉树

孩子兄弟法(Child-Sibling Representation)是一种用来表示树的方法,其中每个节点都有两个子节点:一个指向其第一个孩子节点,另一个指向它的下一个兄弟节点。这种表示方法可以用来构造二叉树,具体步骤如下:

  1. 创建一个类,和一个头结点,结构中包含节点的值以及指向其第一个孩子节点和下一个兄弟节点的指针。
  2. 为每个节点分配内存,并设置节点的值。
  3. 根据孩子兄弟法的规则,构造二叉树:
    遍历树的每个节点,对于每个节点,找到它的第一个孩子节点和下一个兄弟节点。
  4. 将第一个孩子节点作为其左子节点,将下一个兄弟节点作为其右子节点。如果没有孩子节点或兄弟节点,则相应的指针为空。
    重复步骤3,直到树的所有节点都处理完毕。

这里使用孩子兄弟法创建一个二叉树:

static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
       //建立一个简单的数
        public TreeNode creatTree(){
           TreeNode A=new TreeNode('A');
           TreeNode B=new TreeNode('B');
           TreeNode C=new TreeNode('C');
           TreeNode D=new TreeNode('D');
           TreeNode E=new TreeNode('E');
           TreeNode F=new TreeNode('F');
           TreeNode G=new TreeNode('G');
           TreeNode H=new TreeNode('H');

           A.left=B;
           A.right=C;
           B.left=D;
           B.right=E;
           C.left=F;
           C.right=G;
           E.right=H;

           return A;
        }

好了,我们之前在学习链表和顺序表的时候,都涉及到它的基础操作遍历这个数据结构,那么在二叉树中我们如何遍历这些节点呢?

两种特别的二叉树

满二叉树
一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。也就是说,如果一棵二叉树的层数为K,且结点总数是2*k-1 ,则它就是满二叉树。
完全二叉树
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完
要注意的是满二叉树是一种特殊的完全二叉树

在这里插入图片描述

二叉树的基本性质:

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (i>0)个结点
  2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 (k>=0)
  3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1
  4. 具有n个结点的完全二叉树的深度k为log2(n+1) 上取整
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i
    的结点有:
    若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
    若2i+1<n,左孩子序号:2i+1,否则无左孩子
    若2i+2<n,右孩子序号:2i+2,否则无右孩子

二叉树的存储

通常二叉树的存储,我们使用链式存储,和顺序存储,今天带大家使用类似于链表的结构实现二叉树。

// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}

二叉树的遍历:

前序遍历:

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

public void preOrder(TreeNode root){
           if(root==null){
               return;
           }
            System.out.print(root.val+ " ");
           preOrder(root.left);
           preOrder(root.right);
        }

中序遍历:

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

 //2.中序遍历
        public void inOrder(TreeNode root){
           if(root==null){
               return;
           }
          inOrder(root.left);
           System.out.println(root.val);
           inOrder(root.right);

        }

后序遍历:

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

public void postOrder(TreeNode root){
           if(root==null){
               return;
           }
           postOrder(root.left);
           postOrder(root.right);
            System.out.println(root.val);
        }

在这里插入图片描述

  • 前序遍历结果:1 2 3 4 5 6
  • 中序遍历结果:3 2 1 5 4 6
  • 后序遍历结果:3 1 5 6 4 1

层序遍历

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层
上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
在这里插入图片描述

二叉树的基础操作

我们介绍了二叉树了一些基础知识,如何构造,如何遍历二叉树,接着我们还要学习如何进行二叉树的基础操作。

// 获取树中节点的个数
int size(Node root);
// 获取叶子节点的个数
int getLeafNodeCount(Node root);
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k);
// 获取二叉树的高度
int getHeight(Node root);
// 检测值为value的元素是否存在
Node find(Node root, int val);
//层序遍历
void levelOrder(Node root);

这里的代码比较简单,我们都使用递归实现,递归的代码相对来说比较简单的去理解,主要需要我们多多画图,理解这个递归的整个过程。
我把自己实现的代码给大家,有问题的话大家私信我哦~~~

public class TestBinaryTree {
    //建立一个二叉树的基本信息
   static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
       //建立一个简单的数
        public TreeNode creatTree(){
           TreeNode A=new TreeNode('A');
           TreeNode B=new TreeNode('B');
           TreeNode C=new TreeNode('C');
           TreeNode D=new TreeNode('D');
           TreeNode E=new TreeNode('E');
           TreeNode F=new TreeNode('F');
           TreeNode G=new TreeNode('G');
           TreeNode H=new TreeNode('H');

           A.left=B;
           A.right=C;
           B.left=D;
           B.right=E;
           C.left=F;
           C.right=G;
           E.right=H;

           return A;
        }
        //树的一些基本操作
        //1.前序遍历
        public void preOrder(TreeNode root){
           if(root==null){
               return;
           }
            System.out.print(root.val+ " ");
           preOrder(root.left);
           preOrder(root.right);
        }

        //2.中序遍历
        public void inOrder(TreeNode root){
           if(root==null){
               return;
           }
          inOrder(root.left);
           System.out.println(root.val);
           inOrder(root.right);

        }
        //3.后续排序
        public void postOrder(TreeNode root){
           if(root==null){
               return;
           }
           postOrder(root.left);
           postOrder(root.right);
            System.out.println(root.val);
        }
        //获取数的节点个数
        public int size(TreeNode root){
           if(root==null){
               return -1;
           }
           int ret=size(root.left)+size(root.right)+1;
           return ret;
        }
        public static int nodeSize;
        public void size2(TreeNode root) {
            if (root == null){
                return ;
            }
            nodeSize++;
            size2(root.left);
            size2(root.right);
        }
        //求叶子节点的个数
        public int getLeafNodeCount(TreeNode root){
            if(root==null){
                return -1;
            }
            if(root.right==null&&root.left==null){
                return 1;
            }
            return getLeafNodeCount(root.right)+getLeafNodeCount(root.left);

        }
        public int leafSize;
        public void getLeafNodeCount2(TreeNode root){
            if(root==null){
                return;
            }
            if(root.left==null&&root.right==null){
                leafSize++;
            }
            getLeafNodeCount2(root.left);
            getLeafNodeCount2(root.right);
         }
     }

好了今天就带大家学习这么多,下次带大家做几道二叉树的算法题,让大家对二叉树有一个更深刻的认识。谢谢大家~~~

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/518683.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

最新ChatGPT4.0工具使用教程:GPTs,Midjourney绘画,AI换脸,GPT语音对话,文档分析一站式系统

一、前言 ChatGPT3.5、GPT4.0、相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容甚至也可以和用户进行创作交流。 然而&#xff0c;GPT-4对普通用户来说都是需要额外付费才可以…

基于RDMA的云服务能力实践与探索

01 背景 随着基于大数据大模型构建的数据系统越来越有商业价值&#xff0c;机器学习的玩家也越来越多&#xff0c;数据量越来越大。为解决海量数据在服务器之间的同步效率问题&#xff0c;RDMA(Remote Direct Memory Access) 技术逐渐走进了网络技术人员的视野。RDMA为什么…

yolov8多分支任务头训练

目前已知的yolov8可以针对多个任务进行单独训练,但是暂时还没有开放针对多个任务头同时进行训练的教程,本文章针对yolov8的多任务训练进行详细介绍。 先放上效果图: 三个任务,分别是目标检测、可行驶区域、车道线,具体步骤请往下看。 一、环境配置 从如下github下载代码…

Flutter Don‘t use ‘BuildContext‘s across async gaps.

Flutter提示Don‘t use ‘BuildContext‘s across async gaps.的解决办法—flutter里state的mounted属性

10-热点文章-定时计算

xxl-Job分布式任务调度 1 今日内容 1.1 需求分析 目前实现的思路&#xff1a;从数据库直接按照发布时间倒序查询 问题1&#xff1a; 如何访问量较大&#xff0c;直接查询数据库&#xff0c;压力较大 问题2&#xff1a; 新发布的文章会展示在前面&#xff0c;并不是热点文章 …

交叉验证(Cross-Validation)

交叉验证的基本概念 交叉验证通常用于评估机器学习模型在未知数据上的性能。它将数据集分成k个不同的子集&#xff0c;然后进行k次训练和验证。在每次迭代中&#xff0c;选择一个子集作为测试集&#xff0c;其余的子集作为训练集。这样&#xff0c;每个子集都用作过测试集&…

Debian安装1panel管理面板教程-最新

1Panel 是一个现代化、开源的 Linux 服务器运维管理面板。 1Panel面板是一个强大的服务器管理工具&#xff0c;它通过提供一站式管理、易于使用的界面、高度的可定制性、安全可靠的性能、强大的扩展性以及活跃的社区支持&#xff0c;为用户提供了一个高效、便捷的管理解决方案…

华为云1核2G免费使用一年

个人用户专享云服务器、云数据库产品每天上午9:30开抢&#xff0c;其他产品每天0点开放领取&#xff0c;企业用户所有产品每天0点开放领取&#xff1b; 云产品体验名额有限&#xff0c;领完即止。详情&#xff1a;https://www.vpspick.com/vps/591.html 通用入门型 T6 云服务…

实验06_IPv6实验

目录 实验拓扑 实验需求 实验配置及其现象验证&#xff1a; (1)R1---R4的IPv6的地址配置&#xff0c;根据设备编码配置IPv6 (2)R6 通过无状态自动获取 IPv6 地址 (3)OSPFv3 配置&#xff0c;通过 OSPFv3 实现全网通&#xff08;区域划分根据拓扑图&#xff09; 实验拓扑 …

Linux存储的基本管理

实验环境&#xff1a; 系统里添加两块硬盘 ##1.设备识别## 设备接入系统后都是以文件的形式存在 设备文件名称&#xff1a; SATA/SAS/USB /dev/sda,/dev/sdb ##s SATA, dDISK a第几块 IDE /dev/hd0,/dev/hd1 ##h hard VIRTIO-BLOCK /de…

蓝桥杯(5):python动态规划DF[2:背包问题]

1 0-1背包介绍【每件物品只能拿1件或者不拿】 1.1 简介 贪心是不可以的&#xff01;&#xff01;&#xff01; 1.2 状态 及状态转移 转移解释&#xff1a;要么不选 则上一个直接转移过来【dp[i-1][j]】&#xff0c;要么是选这个之后体积为j 则上一个对应的就是【dp[i-1][j-wi]…

Vue 样式技巧总结与整理[中级局]

SFC&#xff08;单文件组件&#xff09;由 3 个不同的实体组成&#xff1a;模板、脚本和样式。三者都很重要&#xff0c;但后者往往被忽视&#xff0c;即使它可能变得复杂&#xff0c;且经常导致挫折和 bug。 更好的理解可以改善代码审查并减少调试时间。 这里有 7 个奇技淫巧…

CSS设置网页颜色

目录 前言&#xff1a; 1.颜色名字&#xff1a; 2.十六进制码&#xff1a; 3.RGB&#xff1a; 4.RGBA&#xff1a; 5.HSL&#xff1a; 1.hue&#xff1a; 2.saturation&#xff1a; 3.lightness&#xff1a; 6.HSLA&#xff1a; 前言&#xff1a; 我们在电脑显示器&…

高血压的常见症状,你是否了解并警惕?

高血压是一种慢性心血管疾病&#xff0c;它的形成和发展与很多种因素密切相关。导致高血压的重要因素之一就是不良的生活饮食习惯。 高血压严重危害着人的心脏、肾脏、大脑等这些人体重要的器官&#xff0c;会容易带来心脏病、肾功能衰竭等一系列疾病。今天我在来为大家讲解一…

CorelDRAW2024序列号破解版下载以及CorelDRAW新功能介绍

CorelDRAW Graphics Suite 2024破解版介绍 CorelDRAW Graphics Suite 2024 破解版是领先的专业图形设计软件套件&#xff0c;旨在提供多个精心设计的工具和丰富的功能&#xff0c;轻松提高您的技能睡哦平&#xff0c;您可以更好的完成矢量插图、完美的布局、高级的照片编辑和高…

Jeecg commonController 任意文件上传漏洞复现

0x01 产品简介 Jeecg(J2EE Code Generation)是一款基于代码生成器的低代码开发平台,使用JEECG可以简单快速地开发出企业级的Web应用系统。 0x02 漏洞概述 JEECG(J2EE Code Generation) 是开源的代码生成平台,目前官方已停止维护。由于 /api 接口鉴权时未过滤路径遍历,攻…

中高级前端? 这些一元运算符,你真的搞清楚了吗

前言 一元运算符&#xff0c;不太起眼&#xff0c;作用很大&#xff0c;请别忽视她&#xff01; 走近她&#xff0c;爱上她&#xff01; 定义 只需要一个操作数的运算符称为一元运算符。 还是代码容易懂&#xff1a; 1 // 一个操作数1 2 // 两个操作数一元运算符清单 运…

基于Springboot的学校防疫物资管理平台(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的学校防疫物资管理平台&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系…

安装typora 免费版(beta版)

前言 typora 2021年11 月 23日后&#xff0c;推出付费的正式版本。不想花钱购买&#xff0c;除了破解脚本&#xff0c;还有其他的办法吗&#xff1f; 程序下载 答案是有的。可以安装免费的Typora Beta 版本&#xff0c;该旧版本基本的功能一应俱全&#xff0c;应付轻度的mar…

若依自带vue-cropper上传图片(可旋转、缩放)

2024.4.4今天我学习了如何使用若依的vue-cropper上传图片组件&#xff0c;在工作中遇到一个需求&#xff0c;需要对上传的图片进行旋转的操作&#xff0c;然后我先找到el-upload组件&#xff0c;使用之后发现它有一个自动上传和非自动上传的功能&#xff0c;是不是就可以通过非…