【数据结构六】图文结合详解二叉树(五千字)

二叉树

        树是一种非线性的数据结构,它是由n个结点组成的具有层次关系的集合,把他叫做树是因为它的根朝上,叶子朝下,看起来像一颗倒挂的树。二叉树是一种最多只有两个节点的树型结构。这篇文章会用Java代码手撕二叉树的实现,从概念到实现,到oj题训练,你不仅能学会二叉树,还能加深对它的理解和运用。

1.树形结构的概念

在树形结构中,子树之间不能有交集,否则就不是树型结构,它具有以下的特点

  • 子树是不相交的;
  • 除了根节点外,每个节点有且仅有一个父节点;
  • 一颗N个结点的树有N-1条边。

 

 树中的相关概念

结点的度:一个结点含有子树的个数称为该结点的度; 如上图: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)棵互不相交的树组成的集合称为森林
 

树的应用

     树的思想和应用在我们周围应用非常广泛也非常重要,比如树的遍历运用递归的思想,电脑中的文件管理系统(目录和文件)运用树形结构存储。

2.二叉树的性质

二叉树是一个节点的有限集合,要么为空,要么是由一个根节点加上两颗被称为左子树和右子树的二叉树组成。如下图所示:

 两种特殊的二叉树:

1. 满二叉树: 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。


 

 二叉树的性质:

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^i-1 (i>0)个结点
  2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是2^k - 1 (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,否则无右孩
     

3.如何构造一个二叉树

常见树的表示方式有很多种,如:双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法等等。

二叉树用代码进行表示时有两种方法,一是通过数组形式的顺序存储,二是类似于链表的链式存储。

顺序存储:将元素存储到数组中,利用二叉树的性质5进行存储,设i为节点在数组中的下标,则:

  • 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
  • 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
  • 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子
     

完全二叉树 

                                                                  一般二叉树

tips: 对于非完全二叉树,则不适合使用顺序方式进行存储,,空间中必须存储空节点,导致空间利用率很低。

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

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

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

4.二叉树的基本操作

二叉树遍历分为四种:

  • 前序遍历——访问根结点--->根的左子树--->根的右子树。
  • 中序遍历——根的左子树--->根节点--->根的右子树。
  • 后序遍历——根的左子树--->根的右子树--->根节点。
  • 层序遍历——第一层--->第二层--->第三层--->...最后一层

下面是用代码分别实现这四种遍历方式的过程。

package Mytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:莎土比亚
 * Date:2024-03-08
 * Time:18:06
 */
public class Mytree {
    class Node{
        public Node(int val) {
            this.val=val;
        }
        int val;
        Node left;
        Node right;
    }
    private int usedsize;
    Node root;
    public Mytree(){
        root=null;
        usedsize=0;
    }
    public void createBinaryTree(){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }
    // 前序遍历
    public void preOrder(Node root) {
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    public void inOrder(Node root) {
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    public void postOrder(Node root){
     if(root==null){
         return;
     }
     postOrder(root.left);
     postOrder(root.right);
     System.out.print(root.val+" ");
    }
    //层序遍历
    public void LeOrder(Node root){
        Queue<Node> list=new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()){
            Node cur=list.poll();
            if(cur!=null){
            System.out.print(cur.val+" ");
            list.add(cur.left);
            list.add(cur.right);
           }
        }
    }

    public static void main(String[] args) {
        Mytree tree=new Mytree();
        tree.createBinaryTree();
        System.out.println("前序遍历");
        tree.preOrder(tree.root);
        System.out.println("\n中序遍历");
        tree.inOrder(tree.root);
        System.out.println("\n后序遍历");
        tree.postOrder(tree.root);
        System.out.println("\n层序遍历");
        tree.LeOrder(tree.root);
    }
}

 二叉树的常见方法:

// 获取树中节点的个数
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);

// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root);

创建一个MyTree类实现一个自己的二叉树并包含上述方法: 

    // 获取树中节点的个数
    int size(Node root) {
        int num=0;
        if(root==null){
            return 0;
        }
        num+=size(root.left);
        num+=size(root.right);
        num++;
        return num;
    }

    // 获取叶子节点的个数
    int getLeafNodeCount(Node root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null) {
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

   //  获取第K层节点的个数
    int getKLevelNodeCount(Node root,int k) {
     if(k==1){
         return 1;
     }
     return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

   // 获取二叉树的高度
   int getHeight(Node root) {
        if(root==null){
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
   }

    // 检测值为value的元素是否存在
    Node find(Node root, int val){
        if (root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        Node left=find(root.left,val);
        Node right=find(root.right,val);
        if(left!=null){
            return left;
        }
        return right;
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(Node root) {
        if(root==null){
            return true;
        }
        if((root.left==null&&root.right!=null)||(root.left!=null&&root.right==null)){
            return false;
        }
        return isCompleteTree(root.left)&&isCompleteTree(root.right);
    }


 

总结:解决二叉树相关问题时要善用子问题思路,将原问题简化为从左子树和右子树中求原始结果,在套用方法递归即可得到问题答案。

5.二叉树相关oj题训练

1.翻转二叉树

2.检查两颗二叉树是否相同

3.判断一颗二叉树是否是平衡二叉树

4.根据一棵树的前序遍历和中序遍历构造二叉树

5.根据二叉树创建字符串

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

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

相关文章

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的木材表面缺陷检测系统(深度学习+Python代码+UI界面+训练数据集)

摘要&#xff1a;开发高效的木材表面缺陷检测系统对于提升木材加工行业的质量控制和生产效率至关重要。本篇博客详细介绍了如何运用深度学习技术构建一个木材表面缺陷检测系统&#xff0c;并提供了完整的实现代码。该系统采用了强大的YOLOv8算法&#xff0c;并对YOLOv7、YOLOv6…

汽车大灯汽车尾灯破裂裂纹破损破洞掉角崩角等问题能修复吗?修复后灯罩颜色和之前相比有什么变化?

答案是肯定的&#xff0c;汽车大灯汽车尾灯破裂裂纹破损破洞掉角崩角等问题是可以修复的。 修复后的汽车灯罩颜色可能会与之前有所不同&#xff0c;这主要取决于修复的方法和使用的材料。 首先&#xff0c;如果修复过程中使用了喷漆翻新&#xff0c;那么灯罩的颜色可能会与原来…

工业涂装行业的物联网解决方案

工业涂装行业的物联网解决方案 工业涂装行业在制造业中占据重要地位&#xff0c;其产品质量直接影响到最终产品的外观和性能。然而&#xff0c;传统涂装生产线容易出现质量问题&#xff0c;如色差、光泽度不均、橘皮现象等。为了解决这些问题&#xff0c;工业涂装行业需要寻求…

一条 sql 语句可能导致的表锁和行锁以及死锁检测

锁 MDL 当对一个表做增删改查操作的时候&#xff0c;加 MDL 读锁&#xff1b;当要对表做结构变更操作的时候&#xff0c;加 MDL 写锁 ALTER TABLE tbl_name NOWAIT add column ... ALTER TABLE tbl_name WAIT N add column ... …

2000-2023年7月全国各省专利侵权结案案件数量数据

2000-2023年7月全国各省专利侵权结案案件数量数据 1、时间&#xff1a;2000-2023年7月 2、指标&#xff1a;地区、年份、专利侵权纠纷行政案件-结案数目 3、范围&#xff1a;31省 4、来源&#xff1a;国家知识产权局&#xff0c;并由该局每个月公布的数据汇总而成 5、指标…

Linux学习笔记(一)Linux基本指令

文章目录 前言目录常见命令1. pwd 打印当前所在路径2. cd 改变路径、切换路径3. 家目录 回到顶级目录4. 当前路径和上一路径5. 上一次路径6. 绝对路径和相对路径7. ls 列出目录内容8. mkdir 创建目录9. rmdir 删除目录10. touch 创建文件11. mv 修改文件目录、移动路径12. cp 复…

12、设计模式之代理模式(Proxy)

一、什么是代理模式 代理模式属于结构型设计模式。为其他对象提供一种代理以控制对这个对象的访问。 在某些情况下&#xff0c;一个对象不适合或者不能直接引用另一个对象&#xff0c;而代理对象可以在客户端和目标对象之间起到中介的作用。 二、分类 代理模式分为三类&#…

java-单列集合-set系列

set集合继承collection,所以API都差不多&#xff0c;我就不多加介绍 直接见图看他们的特点 我们主要讲述的是set系列里的HashSet、LinkedHashSet、TreeSet HashSet HashSet它的底层是哈希表 哈希表由数组集合红黑树组成 特点&#xff1a;增删改查都性能良好 哈希表具体是…

Seata 2.x 系列【8】Spring Cloud 集成客户端

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Seata 版本 2.0.0 本系列Spring Boot 版本 3.2.0 本系列Spring Cloud 版本 2023.0.0 源码地址&#xff1a;https://gitee.com/pearl-organization/study-seata-demo 文章目录 1. 前言2. 问题演…

如何解决跨网文件交换行为分散难管控等问题?

跨网文件交换是指在不同的网络环境之间&#xff0c;如内网和外网&#xff0c;安全地传输文件的过程。这通常涉及到网络隔离的场景&#xff0c;比如政府机构、金融机构、大型企业等&#xff0c;它们为了安全和保密的需要&#xff0c;会通过物理隔离、逻辑隔离等方式&#xff0c;…

《向量数据库指南》——Milvus Cloud BYOC:为数据安全而生?

最近,整个硅谷都在关注 OpenAI 和 Anthropic 的动态。先是 Anthropic 发布了 Claude 3,剑指 GPT-4,被媒体认为“打破了 OpenAI 不可战胜的神话”。这也点燃了整个科技圈的热情,纷纷期待 OpenAI 放出 GPT-5 应战。随后(美东时间 3 月 5 日),OpenAI 发布一则官方公告,主题…

算法打卡day14|二叉树篇03|104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

算法题 Leetcode 104.二叉树的最大深度 题目链接:104.二叉树的最大深度 大佬视频讲解&#xff1a;二叉树的最大深度视频讲解 个人思路 可以使用层序遍历&#xff0c;因为层序遍历会有一个层数的计算&#xff0c;最后计算到的层数就是最大深度&#xff1b; 解法 迭代法 就是…

基于SWOT的智能手机企业财务战略研究1.62

摘 要 近些年&#xff0c;网络技术日新月异&#xff0c;智能手机深受消费者喜爱&#xff0c;人们通过网络&#xff0c;手机应用&#xff0c;可以极大地方便人们学习&#xff0c;工作等等。由于国家对电信行业的大力支持&#xff0c;中国消费者群体逐步成为最具潜力的手机购买者…

基于单片机的IC 卡门禁系统设计

摘要:针对传统门锁钥匙易丢失、配置不便和忘记携带等问题,提出了一种基于STC89C52 的IC 卡门禁系统设计。该系统以STC89C52 单片机为核心来控制电子锁模块的开关。主要过程是由RFID 模块读取IC卡ID 并通过串口发送至STC89C52 单片机模块,STC89C52 单片机模块可以实现在线对I…

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的吸烟检测系统(深度学习+Python代码+PySide6界面+训练数据集)

摘要&#xff1a;本文详细说明了如何利用深度学习开发一个用于监测吸烟行为的系统&#xff0c;并分享了完整的代码实现。该系统采用了先进的YOLOv8算法&#xff0c;同时还使用YOLOv7、YOLOv6、YOLOv5算法&#xff0c;并对它们进行了性能比较&#xff0c;呈现了不同模型的性能指…

VS中配置生成事件

一、为什么需要使用生成事件&#xff1f; 在实际开发过程中&#xff0c;在项目生成DLL后&#xff0c;需要被复制到不同的目录下被引用&#xff0c;很麻烦。 我们可以利用VS中的项目生成事件属性来进行生成后的DLL复制到指定的目录&#xff0c;或者进去其他的操作&#xff0c;比…

C/C++——Tchisla求解器(多线程高性能版本)

前言 之前一篇文章中介绍的使用Python写的Tchisla求解器Python——Tchisla求解器&#xff08;暴力搜索法&#xff09;在我实际使用中有比较大的缺陷&#xff0c;首先是太慢了&#xff0c;对于每日一题中四位数的目标数字&#xff0c;往往搜索数个小时都找不完1~9的全部最优解&…

重学SpringBoot3-ErrorMvcAutoConfiguration类

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-ErrorMvcAutoConfiguration类 ErrorMvcAutoConfiguration类的作用工作原理定制 ErrorMvcAutoConfiguration示例代码1. 添加自定义错误页面2.自定义错误控…

【小白学机器学习8】统计里的自由度DF=degree of freedom, 以及关于df=n-k, df=n-k-1, df=n-1 等自由度公式

目录 1 自由度 /degree of freedom / df 1.1 物理学的自由度 1.2 数学里的自由度 1.2.1 数学里的自由度 1.2.2 用线性代数来理解自由度&#xff08;需要补充&#xff09; 1.2.3 统计里的自由度 1.3 统计学里自由度的定义 2 不同对象的自由度 2.1 纯公式的自由度&#…

汤唯N次被封后,除了人美外,这些也许你没想到!

汤唯N次被封后&#xff0c;除了人美外&#xff0c;这些也许你没想到&#xff01; 引言&#xff1a;影坛的璀璨明星 #李秘书讲写作#注意到&#xff0c;在光鲜亮丽的电影圈&#xff0c;有一位女演员以其独特的气质和深入人心的演技&#xff0c;成为了众多观众心中的璀璨明星。她…