导图社区 数据结构树的思维导图
总结了数据结构树的知识点，主要内容包括定义和基本术语、树的性质、二叉树的定义和基本术语、二叉树的性质、二叉树的存储结构。
社区模板帮助中心，点此进入>>
论语孔子简单思维导图
《傅雷家书》思维导图
《童年》读书笔记
《茶馆》思维导图
《朝花夕拾》篇目思维导图
《昆虫记》思维导图
《安徒生童话》思维导图
《鲁滨逊漂流记》读书笔记
《这样读书就够了》读书笔记
妈妈必读：一张0-1岁孩子认知发展的精确时间表
树
第一部分
定义和基本术语
根结点，叶子结点，边，分支结点，空树：结点数为0的数，子树，结点之间的路径：从上至下。路径长度：经过的边数。
特点：有且仅有一个称为根的结点，除根结点外每个结点只有一个前驱，所有结点都可以有很多后继。
有序树无序，从左往右依次是有序的还是无序的
树和森林
结点，树的属性描述
树的度：一个树拥有最多孩子结点的孩子数
结点的高度：从下往上数
结点的层次，深度：从上往下数
结点的度：一个结点有几个孩子
树的性质
结点数=总度数+1
度为m的树和m叉树
度为m的树：每个结点的度<=m，至少有一个结点的度为m，一定是非空树，至少有m+1个结点
m叉树：任意结点的度<=m,允许所有结点的度<m,可以是空树
度为m的树第i层至多有m^i-1个结点，m叉树相同
高度为h的m叉树至多有m^h-1/m-1个结点
高度为h的m叉树至少有h个结点，高度为h，度为m的树至少有h+m-1个结点
具有n个结点的m叉树的最小高度为(log)[m](n(m-1)+1 向上取整
第二部分
二叉树的定义和基本术语
基本概念
特点：每个结点至多只有俩颗子树，左右子树不能颠倒
几种特殊的二叉树
满二叉树
高度为h，结点数为2^h-1
按层序从1开始编号，结点i的父结点为下取整i/2
完全二叉树
与满二叉树一一对应，只能从后往前删，队列相似。
i<=n/2下取整为分支结点，大于为叶子结点
二叉排序树
右子树的所有结点的关键字均大于根结点的关键字，左子树均小于
用于元素的排序，搜索
平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1
更胖，层数尽量少
更高的搜索效率
二叉树的性质
n0=n2+1
其余同上
完全二叉树的性质
具有n个结点的完全二叉树的高度为向上取整log2（n+1），向下取整（log2n）+1
根据结点数为n，可以推出度为0,1，2的结点的个数
二叉树的存储结构
顺序存储
创建一个静态数组用从上之下，从左至右的顺序存放树，树的结构包含俩个变量一个为数据的值，一个为判断结点是否为空的bool值。初始化时需要一个循环设置每个结点为空（bool值为true）
操作
i结点的左孩子2i
i结点的右孩子2i+1
i的父结点向下取整i/2
向上取整log2（n+1）
判断i是否有左孩子2i<=n
判断i是否有右孩子2i+1<=n
判断i结点为叶子还是分支i>下取整n/2
二叉树的顺序存储中，一定要把二叉树的结点编号和完全二叉树对应起来，这样才能用顺序存储的编号来反映各结点之间的逻辑关系。只有完全二叉树用顺序存储才有意义。
最坏情况，只有右孩子的单只树至少需要2^h-1个顺序存储单元
链式存储
结构体为三个变量一个为值，俩个分别为左右孩子指针变量。
n个结点的二叉树链表共有n+1个空链域
优点找结点的左右孩子很方便，缺点是找父结点需要从头遍历。方法是可以在结构中多设置一个父结点指针。
第三部分
二叉树的先/中/后序遍历
先序遍历
根左右
前缀表达式
步骤
若为空什么都不做
访问根结点
先序遍历左子树
先序遍历右子树
中序遍历
左根右
中序表达式，需要家界限符
若空什么都不做
中序遍历左子树
中序遍历右子树
后序遍历
左右根
后缀表达式
后序遍历左子树
后序遍历右子树
每种遍历中每个结点都会被路过三次，三种遍历依次在第一次，第二次，第三次路过时访问结点。
二叉树的层序遍历
算法思想
初始化一个辅助队列
让根结点入队
若队列非空 让根结点出队 让根节点的左，右孩子入队（左右孩子存在）的话
重复第三步至队列为空
由遍历序列构造二叉树
若只给前中后层序遍历序列中的一种，不能唯一确定一课二叉树
必须要俩个结合，而且其中一个必须为中序序列才可以
原理是根据前后层次可判断根结点，然后再根据中序划分左右子树
线索二叉树的概念
线索化
思路：n个结点存在n+1个空链域，我们用这个结点的空链域来存放这个结点在各序遍历中的前驱后继。设置rtag，ltag在表示是指向孩子rag=1还是线索rag=0。
前驱线索：由左孩子的指针充当
后继线索：由右孩子的指针充当
中序前驱：指向的是在中序遍历中结点的前驱
原因是如果不线索化用土办法我们需要重头从头结点一次遍历，效率低小。土办法是用俩个指针依次遍历然后进行记录，然后用俩个指针用要找结点进行等价判断。俩种前后判断对应前驱和后继
二叉树的线索化
三种遍历的代码实现
三种遍历算法的改造，当访问一个结点是，连接该结点与前驱结点的线索信息
用一个指针pre记录当前访问结点的前驱结点
易错点
最后一个结点的rchild，rtag的处理
先序线索化注意爱的魔力转圈圈问题。当ltag=0时才能对左子树先序线索化
在线索二叉树中找前驱和后继
找中序线索二叉树p结点的前驱和后继
找后继
判断rtag的值
若为0
循坏找右子树的左节点，直到是叶节点，则此结点为后继
若为1
则p的右孩子为后继
找前驱
判断ltag的值
循坏找左子树的右孩子，直到是叶结点，则此结点为前驱
则p的左孩子为前驱
先序
判断ltag=1
则为左指针
ltag=0
先序遍历中左右孩子只能是后继不可能是前驱
代替办法土办法从头遍历
改用三叉链表，添加父结点的指针
若存在父结点且p为左孩子
则p的父结点就是前驱
若存在父结点且p为右孩子
左兄弟非空
p的前驱为左兄弟子树先序遍历最后一个结点
左兄弟为空
父结点则为前驱
若p为根节点
没有前驱
假设有左孩子
则左孩子为后继
没有左孩子
则为右孩子
后序
必有左孩子
假设没有右孩子
则左孩子就为前驱
有右孩子
则右孩子就为前驱
判断rtag=1
则为右指针
rtag=0
p必有右孩子
后序遍历中左右子树只能是根的前驱，不可能是后继
用土办法从头遍历
改用三叉链表添加父指针
能找到父结点
p是右孩子
p的父结点为后继
p是左孩子
右兄弟为空
右兄弟非空
p的后继为右兄弟子树中第一个被后序遍历的结点
P是根结点
p没有后继
第四部分
树的存储结构
双亲表示法（顺序存储）
怎样定义
定义俩个结构一个为每个结点的结构，一个树结构
按从上之下从左至右的顺序将树存入数组
根节点的父结点指针为-1，其他结点的父结点指针的值为其父结点的数组下标
新增元素无需在物理上按次序存储
删除元素
方案1将删除元素的父结点指针值改为-1
方案2将尾结点覆盖要删除的结点
如果是叶子结点删除很方便如果不是叶子结点呢
需要从头遍历，将其子树也全部删除
优缺：好处是查找父结点容易，查找孩子结点需要从头遍历
孩子表示法（顺序+链式存储）
定义三个结构
链表结构
一个树结构
一个结点的结构
顺序存储每个结点，每个结点中保存孩子的链表头指针
孩子兄弟表示法（链式存储）
结构体内俩个指针，一个指左孩子一个指向左孩子的右兄弟
优点：可以用二叉树的操作来直接处理树
在物理逻辑上呈现二叉树的结构
实现树和二叉树的转化
实现二叉树和森林的转化
各个树的根节点视为兄弟关系
树和森林的遍历
树的遍历
树的先根遍历
若树非空，先访问根结点，再依次对每棵子树进行先根遍历
深度优先遍历
树的先根遍历序列与这棵树相应二叉树的先序序列相同
树的后根遍历
若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点
树的后跟遍历与这棵树相对应的二叉树中序序列相同
树的层次遍历
用队列实现
若树非空根结点入队
若队列非空，队头元素出队并访问，同时将该元素的孩子入队
重复上一步直到队列为空
广度优先遍历
森林的遍历
森林的先序遍历
效果等同于依次对每个树进行先根遍历
等同于依次对二叉树的先序遍历
等同于依次对每个树进行后根遍历
等同于对二叉树的中序遍历
先先先，树森二。后中中，树森二。
第五部分
哈夫曼树
带权路及长度
结点的权：有某种现实含义的数值（如结点的重要性）
结点的带全路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带全路径长度
树种所有叶结点的带权路径长度之和
哈夫曼树的定义
在含有n个带权叶结点的二叉树中，其中带全路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。
哈夫曼树的构造
每次将俩个权值最小的结点结合成一棵树，生成的新结点的权值为这俩颗之和，依次进行以上步骤，直到所有的结点都结合完毕
性质
每个初始结点最终都成为叶结点，且权值最小的结点到根结点的路径长度最大
哈夫曼树的结点总数为2n-1
哈夫曼树中不存在度为1的结点
哈夫曼树并不唯一，但wpl必然相同且为最优
哈夫曼编码
固定长度编码：每个字符用相等长度的二进制位表示
可变长度编码：允许对不同字符用不等长的二进制位表示
前缀编码：若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码
前缀编码解码无歧义
有哈夫曼树得到哈夫曼编码，字符集中的每个字符作为一个叶子结点，每个字符出现的频度作为结点的权值，构造哈夫曼树。
哈夫曼树不唯一，哈夫曼编码不唯一。
应用：传电报和压缩数据
并查集
并查集是逻辑结构，集合的一种具体实现，只进行并和查，俩种操作,用森林来表示集合,每一棵树是互不相交的子集。
查：从指定元素出发，一路向北，找到根结点。
判断俩个元素是否是同一个集合。分别查找俩个元素的根，判断根结点是否是相同的
并：让另一课树成为另一棵树的子树即可
存储结构：树的双亲表示法。
代码实现
初始化：让每个结点的父指针都指向-1
查找
并
并的优化：用根结点的绝对值表示树的结点总数，让小树合并到大树
优化和查找操作最坏时间复杂度从on变为olog2n
该方法构造的树高不超过（向下取整log2n）+1
并查集的进一步优化
find操作的优化：压缩路径，先找到根结点，再将查找路径上所有结点都挂到根结点下
