数据结构之树形结构2_堆讲述.ppt

二叉树（Binary tree） 二叉树 堆 数据结构之树形结构 1.什么是树？ 复习 树 树是由n(n=0)个节点构成集合。特点是任何两个节点间有且仅有一条路径。 A B C D E G H F L J K 根节点：没有父亲的节点。 一棵树只有一个根节点。 E K J A 每个节点可有0个或多个儿子节点 除根节点外，每个结点有且只有一个父亲节点 J和K是E的儿子节点E是J和K的父亲节点 A是E的父节点 没有儿子的节点称为叶节点，比如 F G H L J K 都是叶节点 父亲相同的节点称为兄弟节点，比如 F G H 是兄弟 节点的儿子的个数称为节点的度，比如 A 的度数为4 祖先、子孙 包含一个节点的所有子孙和该节点本身的集合，称为子树 复习 1.什么是树？2.什么是二叉树？ 复习 1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多少个节点？ 复习 1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多少个节点？4.高度为h的二叉树最多有多少个节点？ 复习 1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多少个节点？4.高度为h的二叉树最多有多少个节点？5.二叉树叶节点和度为2的节点的关系是？ 复习 二叉树就是每个节点最多只有两个子节点的树。 二叉树的特点： 1.第i层上最多有 个节点 2.高度为h的二叉树最多有 个节点 2i-1 2h-1 3.在非空二叉树中， 叶节点的个数等于度为2的节点个数加1 A B C G F J K L M 复习 6.什么是完全二叉树？什么是满二叉树？ 复习 每层节点数都达到最大的二叉树树叫满二叉树 A B C G F J K 满二叉树 除最底层外，其余各层节点都达到最大值，且最底层的节点集中在左侧的连续位置上的二叉树叫完全二叉树。 A B C G F K 完全二叉树 复习 1 8 3 5 6 2 7 写出前序，中序，后续遍历序列 前顺：1,8,5,3,6,7,2 中序：8,5,1,7,6,2,3 后续：5,8,7,2,6,3,1 复习 二叉堆(heap) 二叉堆是完全二叉树 任何一个节点都大于他的儿子节点的值(大根堆) 或者 任何一个节点都小于他的儿子节点的值(小根堆) 父子，则堆顶元素值一定最大 父子，则堆顶元素值一定最小 9 8 7 1 6 2 5 3 #define Maxn 堆的最大元素个数 //#define maxn 11 int heap[Maxn] ,n; //整型数组heap来存储堆，n表示堆的结点总数 规定这种存储结构中： heap[1]是堆的根； 结点heap[i]的父亲是heap[i/2]（i1）//比如5号节点的父亲是2号节点 结点heap[i]左孩子是heap[2*i]，右孩子是heap[2*i+1] i=n/2 根据堆的定义可以知道： 对于大根堆：heap[1]最大 heap[i]≥h[2*i]且heap[i]≥heap[2*i＋１]（1≤i≤n / 2） 大根堆 heap 数组下标 堆用一维数组来存储， 父子关系可通过数组下标快速计算出来 99 49 66 72 45 27 38 12 已知下列数组表示一个堆，请画出这个堆！ 12 38 27 72 66 49 45 下标 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 99 8 定理：堆的高度最大为log2(n+1) 因为高度为h的二叉树最多有2h-1个节点。 2h-1=n 那么h=log2(n+1) 怎样建堆？(小根) 3 建堆开始…… 6 5 7 4 2 3 1 3 8 7 7 1 5 2 1 6 3 6 1 3 建堆完毕…… 3 6 5 7 4 2 3 1 3 8 7 数组heap 初始时 1 2 3 4 5 6 7 8 9 10 11 n=11 数组下标 从第下标为n/2的节点开始， 依次讨论下标为n/2+1,n/2+2,...,2,1 建堆的时间复杂度为O(n) 详细证明见《算法导论》第77页，或者《算法分析与设计》第74页 1 3 2 3 5 5 3 7 6 8 7 数组heap 建堆完毕后 1 2 3 4 5 6 7 8 9 10 11 堆的向下调整(小根) void shift(int i,int n){ int k,t; t=heap[i]; k=2*i; while(k=n) { if((kn)(heap[k]heap[k+1]))k++; if(theap[k]){ heap[i]=heap[k]; i=k; k=