数据结构C++PPT5.ppt

2 5.1 定义及主要特性3 基本形态空二叉树A只有根结点的二叉树AB右子树为空AB左子树为空ABC左、右子树均非空4 二叉树的相关术语5 二叉树的相关术语6 二叉树的相关术语7 二叉树的相关术语8 完全二叉树12311458912136710141512345671231145891267101234569 二叉树性质10 二叉树的性质11 二叉树的性质12 二叉树的性质13 二叉树的性质14 二叉树的抽象数据类型15 5.2 周游二叉树16 先序遍历ADBCD L RAD L RD L RBDCD L R17 中序遍历ADBCL D RBL D RL D RADCL D R18 后序遍历ADBC L R DL R DL R DADCL R DB19 举例-+/a*b-efcd中序遍历：后序遍历：层次遍历：-+a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f先序遍历：20 前序遍历算法21 遍历算法应用22 5.3 二叉树的实现23 二叉树的存储24 二叉树存储（区别叶和分支）25 表达式树：联合实现方法26 用不同的类实现分支和叶27 不同类实现的分支结点28 5.3.2 结构性空间开销分析29 结构性空间开销分析(2 )2(2 )2nppnpdpdn30 5.3.3 使用数组实现完全二叉树31 顺序存储32 完全二叉树的下标对应关系00000000000033 完全二叉树的下标公式34 5.4 二叉查找树35 BST图示36 检索37 二叉检索树类的定义38 二叉检索树类的定义39 检索40 插入41 BST插入图示42 删除43 删除子树中最小值图示44 删除右子树中最小值结点45 BST Remove（1）46 BST Remove（2）47 5.5 堆与优先队列48 最小值堆49 最大值堆的实现50 建堆图示51 堆的形成52 Shiftdown操作53 举例4965382713769750496538271376509749133827657650974913382765765097132738496576509754 Shiftdown55 Remove Max Value56 建堆操作的效率57 5.6 Huffman编码树58 数据压缩和不等长编码59 5.6.1 建立Huffman编码树10niiilw这个扩充二叉树的叶结点带权外部路径长度总和这个扩充二叉树的叶结点带权外部路径长度总和最小（注意不管内部结点，也不用有序）。权越大的叶结最小（注意不管内部结点，也不用有序）。权越大的叶结点离根越近；如果某个叶的权较小，可能就会离根较远。点离根越近；如果某个叶的权较小，可能就会离根较远。60 建立Huffman树的过程61 Huffman建树图示62 Huffman建树图示63 Huffman建树图示64 Huffman树结点的实现65 Huffman树叶节点的实现66 Huffman树分支结点的实现67 元素/频率对的类声明68 Huffman树的类声明69 Huffman树的类声明70 Huffman树构建函数/ Build a Huffman tree from list fltemplate HuffTree*buildHuff(SLListHuffTree*, HHCompare * fl) HuffTree *temp1, *temp2, *temp3; for (fl-setStart(); fl-leftLength()+fl-rightLength()1; fl-setStart() / While at least two items left fl-remove(temp1); / Pull first two trees fl-remove(temp2); / off the list temp3 = new HuffTree(temp1, temp2); fl-insert(temp3); / Put the new tree back on list delete temp1; / Must delete the remnants delete temp2; / of the trees we created return temp3;71 编码结果平均代码长度是平均代码长度是2.565362.56536。72 5.6.2 Huffman编码及其用法73 Huffman编码及其用法74 Huffman树编码效率)(2211nnpcpcpc75 Huffman树编码效率