数据结构 软考

算法具有5个特性

可行性，有限性，确定性，输入, 输出

图:  有向图 Kruskal(克鲁斯卡尔)算法   和 prim(普鲁姆)算法  都是贪心算法

是一种用来在加权连通图中寻找最小生成树的算法,其操作对象是边.  找最小的不形成环

1.哈夫曼树(也叫最优树)

即叶子节点的带权路径长度最小 (树的第一层权就是0, 第二层就是1)
 

构造  19, 21, 2, 3，6, 7, 10, 32 的哈夫曼树，并计算WPL（带权路经长度）的值?

解题思路: 

带权路经长度计算公式 = 哈夫曼树每层的叶子节点 乘以 权, 然后相加即可

哈夫曼树特点: 从下往上,每一层从左到右递增, 取最小的2个向上构建，求和的结果放上去，把相加的2个数去掉,  不断的找最小的2个，直至所有的数都去掉，即构造完成

2.完全二叉树 / 满二叉树

完全二叉树（Complete Binary Tree）是一种特殊的二叉树，它的定义是：如果设二叉树的深度为h，除第h层外，其它各层（1~h-1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树

每层将节点尽量排满, 如果有空节点,则只在最后一层上,因此,树的高度相对其他二叉树一定是最小的

满二叉树:  每一层都达到最大个数

3. 平衡二叉树 

判断是否是平衡二叉树: 计算每个节点的平衡度(左子树高度减去右子树高度), 平衡度值是-1, 0, 1 , 说明是平衡二叉树, 否则是 非平衡二叉树

4.查找二叉树(也叫二叉排序树) 

左孩子节点 < 根  右孩子节点 > 根

5.线索二叉树

通过增设指针去保存节点的前驱后继关系