TreeMind树图在线AI思维导图
当前位置:树图思维导图模板资格考试计算机计算机理论知识树与二叉树与森林思维导图

计算机理论知识树与二叉树与森林思维导图

  收藏
  分享
免费下载
免费使用文件
U517027942 浏览量:12022-11-07 13:59:27
已被使用0次
查看详情计算机理论知识树与二叉树与森林思维导图

简单介绍树与二叉树与森林内容

树图思维导图提供 计算机理论知识树与二叉树与森林思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机理论知识树与二叉树与森林思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:36d977f8f8247aae4579e44151536e67

思维导图大纲

树与二叉树与森林思维导图模板大纲

二叉树

特殊的二叉树

完全二叉树

完全二叉树总结点数为偶,有一个度为1的结点;为奇,没有度为1的结点,这是快速解题之法

二叉排序树

平衡二叉树

满二叉树

编号为i的结点,若有左右孩子,左为2i,右为2i+1(前提是要有)

二叉树的性质

叶子结点数等于度为2的节点数+1

二叉树的存储结构

链式存储结构

二叉链表

含有n个结点的二叉链表中,有n+1个空链域

顺序存储结构(2020)

自上到下,自左到右存储,缺的位置要空出来

二叉树的遍历

基本遍历方法

中序遍历

左--中--右

2

后序遍历

左--右--中

3

层次遍历

需要借助队列实现

先序遍历

中--左--右

1

线索二叉树

构造原则:左前驱右后继

数据结构:线索链表(左孩子+标志+数据+标志+右孩子)

标志位:0代表左右孩子;1代表前驱后继

二叉树线索化后仍不能有效解决后序线索二叉树求后继问题

树、森林

树的存储结构

孩子表示法

把每个结点的孩子都用单链表链接起来

寻找孩子容易寻找双亲难

孩子兄弟表示法

使用二叉链表

双亲表示法

数组存储,伪指针指向双亲结点的数字下标

寻找双亲容易寻找孩子难

森林--树--二叉树的转换

树--森林

把树接到另一个二叉树的右孩子处

树--二叉树

给定一棵树,有唯一的二叉树与之对应

过程

树和森林的遍历

后跟/后序/中序

对应二叉树的中序

先根/先序

对应二叉树的先序

树与二叉树的应用

二叉排序树(BST)

左<根<右,进行中序遍历,可以得到递增的序列

删除操作

非叶结点

有一个左孩子或右孩子,直接挂上

左右俩孩子,用直接前驱或后继(叶子结点)补上去

叶子结点

直接删除

查找时间:平均理想情况log2(n);最坏情况:n

新加入的结点一定是个叶子结点

树里没有相同值的结点

平衡二叉树

定义:任意结点的左右子树高度差的绝对值不超过1

插入

左右

先对不平衡结点左孩子左旋,再对不平衡结点右旋

右左

先对不平衡结点右孩子右旋,再对不平衡结点左旋

右右

对第一个不平衡结点左旋

左左

对第一个不平衡结点右旋

查找时间:log2(n)

平衡因子:左高度-右高度

哈夫曼树

结点的带权路径长度=结点权值*经过的边数

哈夫曼编码

前缀编码:没有一个编码是另一个编码的前缀

树的带权路径长度=结点之和

树种没有度为1的结点

叶子结点=非叶结点+1(不含度为1的结点)

红黑树

题型

二叉树遍历

先--后序判断形态

11、12

特殊形态

先中相同

2017

感想:题型一直在创新

线索二叉树线索指向哪里

10、13、14

二叉树应用

哈夫曼编码

15、17、18、19

平衡二叉树的构造与插入

09、10、12、13

树、森林

树、森林的遍历顺序

19、20

森林与树转换过程中结点与边的关系

09、11、14

相关思维导图模板

计算机理论知识传输系统思维导图思维导图

树图思维导图提供 计算机理论知识传输系统思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机理论知识传输系统思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:4454067a46ed5333931759de55378bb4

计算机理论知识接口特性与设备思维导图思维导图

树图思维导图提供 计算机理论知识接口特性与设备思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机理论知识接口特性与设备思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:dc9af4e01906e9fc20672ad772a50c1e