当前位置: 首页 > news >正文

二叉树超详细解析

二叉树

目录

  • 二叉树
  • 一级目录
    • 二级目录
      • 三级目录
    • 1.树的介绍
      • 1.1树的定义
      • 1.2树的基本术语
      • 1.3相关性质
    • 2.二叉树介绍
      • 2.1定义
      • 2.2 性质
    • 3.二叉树的种类
      • 3.1 满二叉树
      • 3.2完全二叉树
      • 3.3 二叉查找树
        • 特点:
        • 二叉查找树的节点包含的基本信息:
      • 3.4 平衡二叉树
    • 4.二叉树的遍历方式
      • 4.1深度优先遍历
      • 4.2广度优先遍历

一级目录

二级目录

三级目录

1.树的介绍

1.1树的定义

​ 树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。

把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  1. 每个节点有零个或多个子节点
  2. 没有父节点的节点称为根节点
  3. 每一个非根节点有且仅有一个父节点
  4. 除了根节点之外,每个子节点可以分为多个不相交的子树

1.2树的基本术语

​ 若一个节点有子树,那么该节点称为子树根节点的“双亲“,子树的跟是该节点的“孩子”。有相同双亲的节点互为“兄弟节点”。一个节点的所有子树上的任何节点都是该节点的后裔。从根节点到某个节点的路径上的所有节点都是该节点的祖先。

在这里插入图片描述

  • 节点的度:节点拥有的子树的数目。

  • 叶子:度为零的节点

  • 分支节点:度不为零的节点

  • 树的度:树中节点最大的度

  • 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点

  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点

  • 兄弟节点:具有相同父节点的节点互称为兄弟节点

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

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

  • 层次:根节点的层次为1,其余节点的层次等于该节点的双亲节点加一

  • 树的高度:树中节点的最大层次

  • 无序树:如果树中节点的各子树的次序是不重要的,可以交换位置

  • 有序树:如果树中结点的各子树的次序是重要的,不可以交换位置

  • 森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林

1.3相关性质

  • 树的节点数 = 所有节点度数+1
  • 度为m的树第i层最多有m^(i-1)个节点
  • 高度为h的m叉树最多(m^h -1/(m-1)) 个节点(等比数列求和)
  • n个节点的m叉树最小高度 logm (n(m-1)+1)]

2.二叉树介绍

2.1定义

​ 二叉树是每个节点最多有两个子树的树结构。它有五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;活着左、右子树皆为空。【以go语言和Java为例】

/*------go------*/
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}
/*------Java------*/
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

2.2 性质

  • 二叉树第i层上的节点数目最多为 2{i-1} (i≥1)
  • 深度为k的二叉树至多有2{k}-1个节点(k>=1)
  • 包含n个节点的二叉树的高度至少为log2 (n+1)
  • 在任意一颗二叉树中,若终端节点的个数为n0,度为2的节点数为n2,则n0=n2+1

3.二叉树的种类

3.1 满二叉树

高度为h,并且由2{h} –1个结点的二叉树,被称为满二叉树。

3.2完全二叉树

​ 一棵二叉树中,只有最下面两层节点的度可以小于2,并且最下层的叶节点集中在靠左的若干位置上。

​ 叶子节点只能出现在最下层和次下层,且最下层的叶子节点集中在树的左部。显然,一颗满二叉树必定是一颗完全二叉树,而完全而二叉树不一定是满二叉树。

在这里插入图片描述

3.3 二叉查找树

​ 二叉查找树(Binary Search Tree),又被称为二叉搜索树。设x为二叉树中的一个节点,x节点包含关键字Key,节点x的Key值记为Key[x]。如果y是x的左子树中的一个节点,则Key[y]<=Key[x];如果y是x的有子树的一个节点,则Key[y]>=Key[x]。

在这里插入图片描述

特点:
  • 若任意节点的左子树不空,则左子树上所有的值均小于根节点的值
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于根节点的值(更大于左子树上的值)
  • 任意节点的左、右子树也分别为二叉查找树
  • 没有键值相等的节点
二叉查找树的节点包含的基本信息:
  • key——关键值,是用来对二叉查找树的节点进行排序的
  • left——指向当前节点的左孩子
  • right——指向当前孩子的右节点
  • parent——指向当前节点的父节点

3.4 平衡二叉树

​ 平衡二叉树搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一颗平衡二叉树。如图:
在这里插入图片描述

4.二叉树的遍历方式

二叉树主要有两种遍历方式,深度优先遍历和广度优先遍历

4.1深度优先遍历

深度优先遍历:先往深走,遇到叶子节点再往回走

  • 前序遍历(递归法,迭代法)
  • 中序遍历(递归法,迭代法)
  • 后序遍历(递归法,迭代法)

这里的前中后三种顺序的遍历其实讲的就是中间节点的遍历顺序,例如前序遍历就是先遍历中间节点,再遍历该中间节点的左右两个子节点,同样的中序遍历说的就是先遍历左孩子在遍历中间节点,最后是右孩子。我们可以尝试一下力扣的三道题以便更好地理解这三种遍历方式:

  • https://leetcode.cn/problems/binary-tree-preorder-traversal/
  • https://leetcode.cn/problems/binary-tree-inorder-traversal/
  • https://leetcode.cn/problems/binary-tree-postorder-traversal/

4.2广度优先遍历

  • 广度优先遍历:一层一层的去遍历
    • 层次遍历(迭代法)

相关文章:

  • 北京网站建设多少钱?
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • phpstudy框架,window平台,如何开端口给局域网访问?
  • AIGC专栏12——EasyAnimateV3发布详解 支持图文生视频 最大支持960x960x144帧视频生成
  • 【QT中实现摄像头播放、以及视频录制】
  • Consul与CoreDNS的对比
  • 架构设计(2)云原生架构与实例部署
  • 【WebGIS平台】传统聚落建筑科普数字化建模平台
  • MySQL之基本查询(上)-表的增删查改
  • 如何使用 Puppeteer 避免机器人检测?
  • oracle索引字段存储数据过长,导致索引失效
  • 突破传统,实时语音技术的革命。Livekit 开源代理框架来袭
  • for循环中list触发fast-fail或不触发的原理和方法
  • windows@windows设备之间远程命令行控制方案@windows设备间使用OpenSSH
  • C语言力扣刷题12——合并区间[排序]
  • 继承关系中的访问控制
  • 实战 | YOLOv8使用TensorRT加速推理教程(步骤 + 代码)
  • 【Amaple教程】5. 插件
  • ES6简单总结(搭配简单的讲解和小案例)
  • javascript从右向左截取指定位数字符的3种方法
  • java多线程
  • vue中实现单选
  • Zepto.js源码学习之二
  • 得到一个数组中任意X个元素的所有组合 即C(n,m)
  • 给Prometheus造假数据的方法
  • 机器学习 vs. 深度学习
  • 基于MaxCompute打造轻盈的人人车移动端数据平台
  • 计算机在识别图像时“看到”了什么?
  • 浅谈JavaScript的面向对象和它的封装、继承、多态
  • 深入体验bash on windows,在windows上搭建原生的linux开发环境,酷!
  • 使用 Xcode 的 Target 区分开发和生产环境
  • 一个完整Java Web项目背后的密码
  • 你对linux中grep命令知道多少?
  • 3月7日云栖精选夜读 | RSA 2019安全大会:企业资产管理成行业新风向标,云上安全占绝对优势 ...
  • ​Java基础复习笔记 第16章:网络编程
  • ​批处理文件中的errorlevel用法
  • # MySQL server 层和存储引擎层是怎么交互数据的?
  • ###项目技术发展史
  • #前后端分离# 头条发布系统
  • #我与Java虚拟机的故事#连载09:面试大厂逃不过的JVM
  • (1)(1.11) SiK Radio v2(一)
  • (C语言)输入一个序列,判断是否为奇偶交叉数
  • (附源码)ssm基于微信小程序的疫苗管理系统 毕业设计 092354
  • (一) storm的集群安装与配置
  • (原創) 系統分析和系統設計有什麼差別? (OO)
  • (转) Face-Resources
  • (转)JVM内存分配 -Xms128m -Xmx512m -XX:PermSize=128m -XX:MaxPermSize=512m
  • (最全解法)输入一个整数,输出该数二进制表示中1的个数。
  • .NET 使用 XPath 来读写 XML 文件
  • .Net 知识杂记
  • .NET基础篇——反射的奥妙
  • /*在DataTable中更新、删除数据*/
  • @EventListener注解使用说明
  • @JsonFormat与@DateTimeFormat注解的使用
  • [ C++ ] 继承
  • [ 蓝桥杯Web真题 ]-布局切换
  • []新浪博客如何插入代码(其他博客应该也可以)