国二计算机考试树与二叉树与森林知识点思维导图
简单介绍国二计算机考试树与二叉树与森林知识点内容
树图思维导图提供 国二计算机考试树与二叉树与森林知识点思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 国二计算机考试树与二叉树与森林知识点思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：285fc20d639872361dcf3fbb00bfe2b2
思维导图大纲
树与二叉树与森林思维导图模板大纲
二叉树
特殊的二叉树
完全二叉树
完全二叉树总结点数为偶，有一个度为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
沪公网安备 31011502019485号
上海工商