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

【进阶】java基础之集合(2)数据结构<树>

文章目录

  • 二叉树的内部结构
  • 二叉查找树
  • 平衡二叉树
    • 平衡二叉树的旋转机制

二叉树的内部结构

在这里插入图片描述
在这里插入图片描述

二叉查找树

二叉查找树,又称二叉排序树或者二叉搜索树
在这里插入图片描述
特点:

  • 每一个节点上最多有两个子节点
  • 任意节点左子树上的值都小于当前节点
  • 任意节点右子树上的值都大于当前节点

二叉查找树添加节点 规则:

  • 小的存左边
  • 大的存右边
  • 一样的不存

二叉树的遍历方式

  • 前序遍历
    从根结点开始,然后按照当前结点,左子结点,右子结点的顺序遍历
  • 中序遍历
    从最左边的子节点开始,然后按照左子结点,当前结点,右子结点的顺序遍历
  • 后序遍历
    从最左边的子节点开始,然后按照左子结点,右子结点,当前结点的顺序遍历
  • 层序遍历
    从根节点开始一层一层的遍历

二叉树的遍历弊端

平衡二叉树

规则:任意节点左右子树高度差不超过1

平衡二叉树的旋转机制

规则1:左旋
规则2:右旋
触发时机:当添加一个节点之后,该树不再是一颗平衡二叉树

判断是左旋还是右旋

左旋

  1. 确定支点:从添加的节点开始,不断的往父节点找不平衡的节点
  2. 把支点左旋降级,变成左子节点
  3. 晋升原来的右子节点

右旋

  1. 以不平衡的点作为支点
  2. 把支点右旋降级,变成右子节点
  3. 晋升原来的左子节点

数据结构(平衡二叉树)需要旋转的四种情况

  • 左左:当根节点左子树的左子树有节点插入,导致二叉树不平衡
  • 左右:当根节点左子树的右子树有节点插入,导致二叉树不平衡
  • 右右:当根节点右子树的右子树有节点插入,导致二叉树不平衡
  • 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡

http://www.mrgr.cn/news/66941.html

相关文章:

  • C# WPF 打印机
  • 淘宝反爬虫机制的主要手段有哪些?
  • 拒绝事后背锅:测试项目中的风险管理一定要知道
  • java面试2.0
  • 配电线路的监控环境故障预警
  • LN2220 2A 高效率升压 DC/DC 电压调整器
  • 测试平台常见前端问题-建议收藏备忘
  • 开发的角度认识一下防止模拟执行和反调试函数(RC4算法)
  • mysql约束和高级sql
  • 【三维重建】Semantic Gaussians:开放词汇的3DGS场景理解
  • 【CAP理论:概念、解释与应用】
  • 画动态爱心(Python-matplotlib)
  • Django的manage.py命令用法
  • element-plus table tableRowClassName 无效
  • 最新三维视觉下的扩散模型综述——Diffusion Models in 3D Vision: A Survey
  • windows10显示计算机设置,我的电脑,此电脑设置
  • 软媒市场自助发稿平台的优势解析
  • 怎样用云手机进行FB矩阵运营而不被封号?
  • 【Ag-Grid】 使用笔记 Vue3 + Vite(一)
  • Kafka自动生产消息软件(自动化测试Kafka)