导图社区 数据结构 第五章 树
数据结构 第五章 树知识总结，包括空树与非空树、结点、路径、树与结点的横向比较、树的性质、树的种类等等。
第一章 计算机系统概述（操作系统）的内容包括操作系统的四个重要特征、操作系统的目标和功能、操作系统发展历程等等。
计算机体系结构第一章，讲述了计算机硬件的技术指标、计算机的基本组成、计算机系统简介等，赶快收藏下图了解吧！
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
第五章 树
1. 空树与非空树
空树
结点数为0
非空树
有且仅有一个根节点
没有后继结点的结点被称为“叶子结点”
有后继结点的结点被称为“分支节点”
除了根结点外，任何一个结点有且只有一个前驱
任何结点都可以有0个或多个后继
2. 结点
祖先结点
子孙结点
双亲结点：一个结点的直接前驱
孩子结点：一个结点的直接后继
兄弟结点：同一层的结点
堂兄弟结点：不是一个父亲结点的同一层结点
3. 路径
结点之间的路径：自上向下数，经过了几条边，则路径长度为几
树的路径：所有路径长度的总和
4. 树与结点的横向比较
结点
高度：自下而上计算
度：有几个孩子（分支），则度为几
深度：自上而下计算，默认深度为1，但有些题目会默认深度为0
树
树的高度（深度）：总共有多少层
度：所有结点中度的最大值为该树的度
路径：树的路径是所有路径长度的总和
所有结点高度（深度）的最大值为树的高度（深度）
需要特别注意的是：树的度为所有结点度的最大值，但是树的路径为所有长度的总和
5. 树的性质
树的结点数=所有结点的度数总和＋1
度为M的树
1. 任意结点的度＜＝M
2. 至少有一个度为M的结点
3. 一定是非空树，至少M+1个结点（只有根节点且根节点度为M的情况）
4. 高度为h，度为M的树至少有h+M-1个结点
M叉树（每一个结点最多M个孩子）
1. 可以为空树
2. 允许所有结点的度＜=M
3. 高度为h的M叉树最少有h个结点
4. 高度为h的M叉树最多有(M^h-1)/(M-1)个结点
5. n个结点的M叉树最小高度为
度为M的树和M叉树第i层（i<=1）最多有M的i-1次方个结点
6. 树的种类
有序树：树中各子树从左向右是有次序的，不可互换
无序树：树的子树无次序，可互换
二叉树
1. 特点：每个结点最多有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树有左右之分，其次序是不能颠倒的
2. 几种特殊的二叉树
满二叉树
定义：一棵高为h，且含有2^h-1个结点的二叉树被称为满二叉树（其实就是树的每一层都含有最多的结点，即除了叶子结点外每个结点的度数都为2）
特点
1. 满二叉树的所有叶子结点都在最下面一层
2. 对满二叉树开始编号，自上而下，从左向右。则对于编号为i的结点，它的左孩子结点为2i，右孩子结点为2i+1，父亲结点为i/2取整
3. 不存在度为1的结点
完全二叉树
定义：高度为h，有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点完全对应时，称为完全二叉树
1. 叶子结点只在层数最大的两层上出现
2. 若有度为1的结点，则只可能有1个
3. 对完全二叉树开始编号，自上而下，从左向右。则对于编号为i的结点，它的左孩子结点为2i，右孩子结点为2i+1，父亲结点为i/2取整
4. 一旦出现编号为i的某结点为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点
5. 若i<=n/2，则结点i为分支结点，其他为叶子结点（一完全二叉树有1001结点，1001/2=500，即500个分支节点，其他501个为叶子结点）
6. 具有n个结点的(满二叉树)完全二叉树的高度为log2(n+1)或
7. 对于完全二叉树，可以由结点数n推出度为0,1,2的结点个数
若有2k个结点，则必有n1=1，n0=k，n2=k-1
若有2k+1个结点，则必有n1=0，n0=k，n2=k-1
二叉排序树
平衡二叉树
3. 二叉树的性质
1. 非空二叉树的叶子结点数等于度为2的结点数+1，即n0=n2+1
2. 非空二叉树（包括满二叉树，完全二叉树）在第k层上，最多有 个结点
3. 高度为h的非空二叉树（包括满二叉树，完全二叉树）最多有（2^h)-1个结点
4. 结点数为n的二叉链表，含有n+1个空链域
4. 二叉树的存储结构
5. 二叉树的遍历
1. 先序遍历（根左右）
2. 中序遍历（左根右）
3. 后序遍历（左右根）
4. 层次遍历（二叉树一层一层的被遍历）
5. 由遍历序列推导二叉树结构
可以唯一确定一颗二叉树的序列组合
先中
后中
层中
不可唯一确定一颗二叉树的序列组合
没有中序遍历则无法推断出一颗唯一的二叉树
6. 线索二叉树
意义：线索二叉树存在的意义是为了加快找到结点前驱和后继的速度
结点结构：lchild* ltag data rtag rchild*
tag标志域
tag=0时，child指向左（右）孩子
tag=1时，child指向前驱（后继）
线索二叉树的前驱与后继取决于它是什么遍历
7. 树与森林
树的存储结构
双亲表示法
利用一块连续的空间来存储各个节点，同时在各个结点中增设一个伪指针，指示其双亲节点在数组中的位置
特点：找双亲容易，找孩子难。
孩子表示法
孩子表示法是将每个节点的孩子结点都用单链表链接起来行程一个线性结构，此时有n个结点则有n个孩子链表。（叶子结点的孩子链表为空表）
特点：找孩子易，找双亲难
带双亲的孩子链表
孩子兄弟表示法（重要）
此法又称二叉树表示法，其可以方便的实现树转换为二叉树的操作（左孩子右兄弟）
树、森林和二叉树的转换
1. 树转换成二叉树
1）加线：在兄弟之间加一连线 2）抹线：对每个结点,除了其左孩子外,去除其与其余孩子之间的关系 3）旋转：以树的根结点为轴心，将整数顺时针转45度。 记忆口诀：兄弟相连留长子 过程如下：加线->抹线->旋转
2. 二叉树转换成树
步骤： 1）加线：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来 2）抹线：删除原二叉树中所有双亲结点与右孩子结点之间的连线 3）调整：整理由前两步得到的树，即以该结点为轴心，逆时针转动45°，使之结构层次分明 记忆口诀：左孩右右连双线，去掉原来右孩线 过程如下：加线->抹线->调整（旋转）
3. 森林转换成二叉树
（1）先把每棵树转换为二叉树； （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
4. 二叉树转换成森林
二叉树转换为森林比较简单，其步骤如下： （1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树； （2）把分离后的每棵二叉树转换为树； （3）整理第（2）步得到的树，使之规范，这样得到森林
树、森林的遍历
树的遍历
先根遍历
先访问根节点，再访问根节点的每棵子树，遍历子树时依然遵循先根后子树的规则
其遍历序列与这棵树对应的二叉树先序序列相同
后根遍历
先访问每棵子树，再访问根节点，遍历子树时依然遵循先根后子树的规则
其遍历序列与这棵树对应的二叉树中序序列相同
层次遍历
与二叉树层次遍历思想基本相同
森林的遍历
先序遍历森林
访问森林中第一棵树的根结点，先序遍历第一棵树中根结点的子树森林，最后先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林
中序遍历森林中第一棵树的根结点的子树森林，然后访问第一棵树的根结点，最后中序遍历除去第一棵树之后的剩余树构成的森林。
8. 哈夫曼树
定义：n个带权结点的二叉树中，带权路径（WPL）最小的树为哈夫曼树
结点的带权路径
从树的根到任意结点所经过的边数与该结点上权值的乘积为该节点的带权路径长度
哈夫曼树的构造
哈夫曼树的特点
1. 每个初始节点都成为叶子结点，并且权值越小的结点到根结点的路径长度越大
2. 构造过程中共新建了N-1个结点（双分支结点），因此哈夫曼树中结点总数为2N-1。
3. 每次构造都选择2棵树作为新结点的孩子，因次哈夫曼树中不存在度为1的结点
9. 并查集
定义：并查集是一种树形模型，主要用于解决一些元素分组的问题。它管理一系列不相交的集合
存储结构（非常类似于双亲表示法）
可以用根节点S[]的绝对值代表其下有几个结点
Find与Union操作
Find：从目标结点依次向上查找S[]的值，直到找到S[]为-1的结点，该结点则为其根节点，时间复杂度O(n)
Union：将一棵树根节点的S[]改为另一颗树根节点下标即可，时间复杂度O(1)
Find操作的优化（压缩路径）
每次查找时，先找到根节点，再路径上的所有结点都挂在根节点之下
中心主题
主题
