《数据结构》(C语言版)第六章_树和二叉树.ppt

第六章 树和二叉树 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结 点。 (i≥1) 两种特殊形式的二叉树 满二叉树 定义：指的是深度为k且含有2k-1个结点的二叉树。 特点：每一层上的结点数都是最大结点数。 二、孩子表示法 6.4.2 树、森林与二叉树转换 第六章 作业 data child1 child2 ………. childD data degree child1 child2 ………. childd 多重链表：每个结点有多个指针域，分别指向其子树的根。 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d n个结点度为k的树中有n(k-1)+1个空链域 孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。 typedef struct CTNode { int child; struct CTNode *next; } *ChildPtr; 孩子结点结构: child next typedef struct { Elem data; ChildPtr firstchild; // 孩子链的头指针 } CTBox; 双亲结点结构: data firstchild 树结构: typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree; a b c d e f h g i 1 2 ^ 3 4 ^ ^ 8 6 7 ^ 5 ^ ^ ^ ^ ^ 如何找双亲结点 6 0 1 2 3 4 5 7 8 a c d e f g h i b data fc R=0，N=9 带双亲的孩子链表 5 0 1 2 3 4 6 7 8 a c d e f g h i b data fc 1 2 3 4 8 6 7 5 ^ ^ ^ ^ ^ ^ ^ ^ ^ -1 0 1 1 2 4 4 4 0 parent a b c d e f h g i firstchild data nextsibling 三、孩子兄弟表示法（二叉树表示法） typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; 结点结构: a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ A C B E D 树 A B C D E 二叉树 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 对应 存储 存储 解释 解释 §6.6 赫夫曼树及其应用 6.6.1 最优二叉树 6.6.2 赫夫曼编码 6.6.1 最优二叉树（赫夫曼树） 结点的路径长度：从根结点到该结点的路径上分支的数目。 树的路径长度：从树根到每一个结点的路径长度之和。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作 赫夫曼树（最优二叉树）：带权路径长度之和最小的二叉树。 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 例如： a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 d c a b 2 4 7 5 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 （1）根据给定的 n 个权值 {w1, w2, …, wn}， 构造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树； 如何构造最优树？ （赫夫曼算法）以二叉树为例： （2）在 F 中选取其根结点