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

数据结构之树2

news 来源：原创 2024/5/14 9:26:38

二叉树储存结构

顺序结构

当你的树是完全二叉树时
在这里插入图片描述
几个基本操作
在这里插入图片描述
当你的二叉树不是完全二叉树时
因为要完成树的基本操作，你只能在对应空间储存
而且此时对应是否有自子节点
还要根据isEmpty来判断对应
节点
这样的空间利用率还低
在这里插入图片描述
所以树的顺序一般来说是不太实用的
只适用于完全二叉树
所以我们重点看书的链式储存

树的链式储存

n个节点
n-1个节点上面有指针指向
一共是2n个指针域
所以有n+1个空指针域
在这里插入图片描述
简单看下二叉树的初始化和插入新节点
在这里插入图片描述
其他定义方法
看情况
考研一般考不加父节点的
在这里插入图片描述

二叉树的先后中序遍历法

先序，中序和后序
对应的是节点的先中后
左一定在右后面
先序：根左右
中序：左根右
后序：左右根
在这里插入图片描述

先中后序
遍历一些例子
在这里插入图片描述

先序遍历的伪代码

在这里插入图片描述

可以推一下奥
中序
和后序都差不多

在这里插入图片描述

在这里插入图片描述

演示递归过程
在这里插入图片描述

现在栈顶的T=NULL
弹出栈
到前一个栈
前一个栈运行到126行
现在运行127行
就是D->G
访问G
124然后G！=NULL
到125访问G
然后到126没左NULL返回
G的栈
然后127也是NULL
返回G的栈
然后G的栈运行完了
弹出
其他都差不多是这样的过程

在这里插入图片描述

应用
访问树的深度
也是递归哦
在这里插入图片描述

二叉树的层次遍历

算法思想
1.借助一个辅助队列实现
2.入根节点，然后先入队其左节点后入队其右节点
3.后面的都相同循环出一个节点的同时入队其左节点和右节点
直至队列没有元素
在这里插入图片描述
在这里插入图片描述
代码实现
在这里插入图片描述

遍历序列构造二叉树

三序遍历的缺点
就是一个树对应一种遍历序列
但是
一个中序（或者前序或者后序）遍历不能确定唯一的二叉树
如图他们的三种二叉树的中序遍历法都相同
但是树不同

在这里插入图片描述
所以我们确定唯一的一棵树
需要前序，中序，后序
中的至少二个
才能确定

在这里插入图片描述

相关文章：

  • 微信小程序开发实战9_1 生成小程序码
  • Informer时序模型(代码解析)
  • CAN协议解析
  • 转置卷积详解（原理+实验）
  • ES字符串从任意位置模糊查询（支持只匹配含连续字符串内容）
  • (附源码)计算机毕业设计ssm基于B_S的汽车售后服务管理系统
  • STM32F103移植FreeRTOS必须搞明白的系列知识---4（FreeRTOSConfig.h配置文件）
  • Java基础2（二维数组、数组的赋值判定）
  • Redis 强化之一
  • 打印设备电磁泄露信息提取和还原技术的matlab仿真实现
  • 【C++】类和对象（中）—— 日期类的实现 | const成员函数
  • 树莓派视频监控项目总结
  • datax与多种数据库间数据类型映射
  • Redis哨兵模式与Redis缓存穿透、击穿和雪崩
  • Ubuntu Budgie 22.04 设置中文语言并安装拼音输入法
  • 【399天】跃迁之路——程序员高效学习方法论探索系列（实验阶段156-2018.03.11）...
  • 78. Subsets
  • echarts的各种常用效果展示
  • idea + plantuml 画流程图
  • Linux gpio口使用方法
  • MySQL QA
  • React 快速上手 - 06 容器组件、展示组件、操作组件
  • Swoft 源码剖析 - 代码自动更新机制
  • TypeScript迭代器
  • vue 个人积累(使用工具，组件)
  • 发布国内首个无服务器容器服务，运维效率从未如此高效
  • 买一台 iPhone X，还是创建一家未来的独角兽？
  • 猫头鹰的深夜翻译：JDK9 NotNullOrElse方法
  • 前端学习笔记之原型——一张图说明`prototype`和`__proto__`的区别
  • 适配iPhoneX、iPhoneXs、iPhoneXs Max、iPhoneXr 屏幕尺寸及安全区域
  • 微信端页面使用-webkit-box和绝对定位时，元素上移的问题
  • 用Python写一份独特的元宵节祝福
  • 06-01 点餐小程序前台界面搭建
  • 白色的风信子
  • 测评：对于写作的人来说，Markdown是你最好的朋友 ...
  • #pragma multi_compile #pragma shader_feature
  • #WEB前端（HTML属性）
  • (04)Hive的相关概念——order by 、sort by、distribute by 、cluster by
  • (13)Latex：基于ΤΕΧ的自动排版系统——写论文必备
  • （4）STL算法之比较
  • （C语言）共用体union的用法举例
  • （MATLAB）第五章-矩阵运算
  • (windows2012共享文件夹和防火墙设置
  • (附源码)ssm教师工作量核算统计系统 毕业设计 162307
  • （附源码）ssm捐赠救助系统 毕业设计 060945
  • （附源码）ssm智慧社区管理系统 毕业设计 101635
  • （七）MySQL是如何将LRU链表的使用性能优化到极致的？
  • （转载）跟我一起学习VIM - The Life Changing Editor
  • ＊Django中的Ajax 纯js的书写样式1
  • .describe() python_Python-Win32com-Excel
  • .net mvc部分视图
  • .net 打包工具_pyinstaller打包的exe太大？你需要站在巨人的肩膀上-VC++才是王道
  • .NET3.5下用Lambda简化跨线程访问窗体控件,避免繁复的delegate,Invoke(转)
  • .NET的微型Web框架 Nancy
  • .net之微信企业号开发(一) 所使用的环境与工具以及准备工作