数据结构——二叉树
2023-02-18 16:27:08 时间
文章目录
前言
经过前几天的学习,我们对树这个基本数据结构也有了初步的了解,今天让我们一起来看树中比较难的二叉树,有句玩笑话叫”大学有俩棵树,上面挂了好多人,一棵二叉树,一棵高数“,也可以看出二叉树的难度,但是遇难我们更强,开始今天的学习!
二叉树定义
特点:
- 每个结点'最多'有俩棵子树
- 左右子树都是有顺序的,不能任意颠倒
- 即使只有一棵子树,也要区分它是左子树还是右子树
一般情况下,有以下几种基本形态
- 空二叉树,没有办法画图了
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
再思考一下,如果有三个结点的二叉树,又有几种形态呢? 5种,怎么来的?先看图
由于他必须是有序的所以要单个计算,左右分开,加起来就是5种 下面来说几个特殊的二叉树:
- 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。
- 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
- 斜树:有点像线性表,这个斜可以不分左右,所以更像线性表了
如何判断完全二叉树,下面是它的特征:
- 叶子结点只能出现在最下俩层、
- 最下层的叶子一定集中在左部的连续位置
- 倒数俩层,若有叶子结点,一定都在右部连续位置
- 如果结点度为一,则该结点只有左孩子
- 同样结点数的二叉树,完全二叉树的深度最小
树的几种遍历方式
- 前序遍历
- 中序遍历
- 后序遍历
数据结构——二叉树先序、中序、后序及层次四种遍历(C语言版)
刷题巩固
相关文章
- Docker学习11-Docker常规方式安装软件
- 【图文教程】Windows11下安装Docker Desktop
- 若依前后端分离版本-添加定时任务提示目标字符串不在白名单解决办法:
- idea导入eclipse项目的时候,Java图标变成黄色小J了,怎么解决?
- Windos11下通过WSL安装centos7系统
- 【填坑】在windows系统下安装Docker Desktop后迁移镜像位置
- 【已经解决】./ 运行bash脚本文件出现 报错信息 /usr/bin/env: “bash\r“: 没有那个文件或目录
- Docker学习6-Docker镜像commit操作案例
- Acrobat 8安装步骤 PDF编辑器全版本软件下载
- CSS 中的变量
- 网站经典功能之返回顶部
- CSS overflow 内容溢出时的显示方式
- CSS font-family 属性设置字体
- Acrobat XI Pro软件安装教程,PDF编辑器全版本软件下载
- HTML5 语义化标签
- Laravel Valet - macOS 极简主义者的开发环境
- CSS 控制内容显示行数
- PDF作品集如何插入视频?Acrobat Pro 中完成只需3步!
- 异步编程解决方案 Promise
- uniapp 中的交互反馈 API【提示框】