【学习笔记】数据结构-树

数据结构中关于树的一些知识，内容有哈夫曼树、树表的查找、线索二叉树、二叉树遍历方式、最小生成树，欢迎大家学习。

树

哈夫曼树

带权路径长度WPL

设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积的和，叫做二叉树的带权路径长度WPL (weighted Path Length)。

相同的叶结点构造出不同的二叉树

权值越大的叶子结点，越靠近根，wpl的值越小

定义

具有最小带权路径长度的二叉树称为哈夫曼树(也称最优树)。

如何构造？

原则

权值越大的叶结点越靠近根结点。

权值越小的叶结点越远离根结点。

找小值（合成的节点也要一起比较）

过程

有n0个带权值的叶子结点的

应用

哈弗曼编码（前缀编码）

哈夫曼编码特点:权值越大的字符编码越短，反之越长。

在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。

应用

字符编码

机器指令

树表的查找

二叉排序树

左<根<右

平衡二叉树AVL

二叉排序树的改进版（特殊的二叉排序树），尽量保证树越矮越好！

如何判断树是否在正常的长高？

平衡因子=左子树高度-右子树高度

平衡因子<=1的二叉排序树

平衡二叉树的最大深度和最小节点数

B树（平衡二叉树的拓展）

插入

创建B树就是不断进行插入操作的过程

线索二叉树

左空链域的条件:处于序列最左端，且原来左指针就是空的。

右空链域的条件:处于序列最右端，且原来右指针就是空的。

二叉树遍历方式

针对根节点

前序

根-左-右

中序

左-根-右

后序

左-右-根

层次

一行一行遍历

最小生成树

Prim算法

要求

权值最小，不能成环

针对节点少的题

Prime算法的核心步骤是：在带权连通图中V是包含所有顶点的集合， U已经在最小生成树中的节点，从图中任意某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树。

Kruskal算法

先把节点都确定，依次选择路径最短的

不能成环

针对边数少的题

基本思想：以边为主导。在带权连通图中，U是所有边构成的集合，N是顶点数量，设SU是已经在最小生成树上的边构成的集合。重复执行下述操作:每次选择一条权值最小的边e∈U-SU,且与SU中边不构成环的边，加入到SU中。当SU中边数量等于N-1时，就找到了最小生成树。

题

如果一个节点不是叶节点，那么就会有孩子,这些孩子就是一组亲兄弟

没有右侧指针的节点的数量是:根节点+非叶节点数量

排除对称的，数数目，要保证一直是左少右多或左多右少

树

ASL平均查找长度

与树的高度有关

第五章树与二叉树

二叉树的遍历和哈夫曼树

难点：二叉树与树和森林的转换

多以选择题形式考查，也会涉及树的遍历和哈夫曼树的算法

树

n个结点的有限集

根节点唯一

子树个数无限制，但互不相交

度数：节点所拥有的子树的个数

二叉树：度数都<=2

性质

在二叉树的第i层上最多有2^i-1个节点。

二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1)

n0=n2+1 ,n0表示度数为0的节点数,n2表示度数为2的节点数。

在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整

[二叉树]节点计算公式N = n0+n1+n2

节点总数=总度数+1=Oxn0+1xn1+2xn2+..

满二叉树

所有节点都存在左右子树，且所有叶子节点都在同一层

完全二叉树

叶子结点只能出现在最下层和次下层，

并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

树、森林、二叉树的遍历对应关系

堆

定义

必须是完全二叉树

完全二叉树只允许最后一行不为满。且最后一行必须从左往右排序。最后一行元素之间不可以有间隔

堆序性

大根堆

小根堆

基本操作

堆的存储

1、按照层序遍历编号，用一维数组表示

父节点为i，左子结点下标2i+1，右子节点2i+2（此规律在算法中经常使用）

上滤

只有树的最后一个元素破坏了堆序性

主要用于插入新元素到堆中

复杂度：O(logN)

下滤

只有根节点破坏堆序性

根节点向下调整

复杂度：O(logN)

建堆

乱序数组如何转化成堆？

自顶向下

插入堆，上滤

复杂度：O(NlogN)

自下而上

先把元素调整成堆，下滤，从倒数第二行开始，对父节点进行下滤操作

复杂度：O(N)

应用：优先队列

两个操作

插入队列

弹出最小元素

可以用小根堆实现

因为小根堆的根节点是min，弹出后将剩余元素调整成堆（将最后一个元素置于根节点，下滤）

复杂度：O(logN)

堆排序：将优先队列的元素依次弹出

复杂度：O(NlogN)