数据结构;;;5.1问题引入：商品分类树;5.1问题引入：商品分类树;5.1问题引入：商品分类树;5.2树的定义与结构;5.2树的定义与结构;树的基本术语;树的基本术语;树的基本术语;树的基本操作;5.3.1二叉树的定义;5.3.1二叉树的定义;二叉树的基本操作;5.3.2满二叉树、完全二叉树、完美二叉树;5.3.2满二叉树、完全二叉树、完美二叉树;5.3.2满二叉树、完全二叉树、完美二叉树;5.3.2满二叉树、完全二叉树、完美二叉树;5.3.2满二叉树、完全二叉树、完美二叉树;5.3.2满二叉树、完全二叉树、完美二叉树;5.3.3二叉树基本性质;5.3.3二叉树基本性质;5.3.3二叉树基本性质;完全二叉树的分层编号;5.3.3二叉树基本性质;5.3.4二叉树的顺序存储实现;5.3.4二叉树的顺序存储实现;5.3.4二叉树的顺序存储实现;5.3.5二叉树的链接存储实现;5.3.5二叉树的链接存储实现;构造二叉树的算法;5.4.1二叉树遍历的基本概念;5.4.2二叉树遍历的递归算法;5.4.2二叉树遍历的递归算法;递归算法;后序遍历递归算法的应用;表达式树;表达式树;表达式树;将表达式树转换成中缀表达式的算法;表达式树;5.4.3二叉树遍历的非递归算法;算法5-7：非递归前序遍历PreOrder(tree);算法5-8：非递归中序遍历InOrder(tree);5.4.3二叉树遍历的非递归算法;算法5-9：非递归后序遍历PostOrder(tree);5-4二叉树的遍历;5.4.3二叉树遍历的非递归算法;层序遍历;算法5-10：层序遍历二叉树LevelOrder(tree);层序遍历;5.4.4二叉树的序列化与反序列化;5.4.4二叉树的序列化与反序列化;5.4.4二叉树的序列化与反序列化;前序序列;算法5-11：二叉树前序序列化PreOrderSerialize(tree);前序序列;算法5-12：二叉树前序序列的反序列化PreOrderDeSerialize(preorder,n);二叉树的序列化：按某种遍历方案访问所有结点并依次输出结点数据，由此形成结点的线性序列
二叉树的反序列化：根据线性序列重构原始的二叉树
思考：
（1）与前序序列类似，在二叉树的层序遍历过程中，输出表示空结点的标记，可生成二叉树的层序序列，并根据层序序列重构二叉树（过程及算法参考教材）
（2）（经典问题）用前序遍历与中序遍历结果重构二叉树，分析重构条件及算法的时间复杂度
;5.5.1最优二叉树;5.5.1最优二叉树;最优二叉树基本性质;命题5-5：最优二叉树中，如果两个叶结点的权重值不同，则权重值小的叶结点在树中的层数大于等于权重值大的叶结点
;命题5-6：给定一组叶结点权重，存在最优二叉树，权重最小和次小的叶结点在树的最下层并且互为兄弟结点。
;中间结点的权重：除了叶结点带有权重，带权二叉树各中间结点也可定义权重，等于它的左子结点和右子结点的权重之和
哈夫曼算法：一种至下而上构建最优二叉树的方法，通过不断合并两个带权二叉树，最终生成最优二叉树，具体过程如下：
;哈夫曼算法：一种至下而上构建最优二叉树的方法，通过不断合并两个带权二叉树，最终生成最优二叉树
;算法5-15：创建哈夫曼树CreateHuffmanTree(w);算法5-15：创建哈夫曼树CreateHuffmanTree(w);哈夫曼算法：一种至下而上构建最优二叉树的方法，通过不断合并两个带权二叉树，最终生成最优二叉树
算法分析：
;问题：如何传输由字母a、b、c、w、z组成的字符串“baaacabwbzc”？
关键：需要将文字符串转换成计算机能够识别处理的二进制字符串（编码）
定长码：把每个字母转换成固定长度的二进制字符串
不定长码：使用频率高的字母采用短编码，频率小的采用长编码
;前缀码：一种常用的不定长码，每个字母的编码都不是其它字母编码的前缀
;前缀码：常用的不定长码，每个字母的编码都不是其它字母编码的前缀
;前缀码：常用的不定长码，每个字母的编码都不是其它字母编码的前缀
问题：给定一个字符串，求最优前缀码，使编码出的二进制字符串长度最短
;算法5-16：使用哈夫曼树对二进制字符串解码Decoding(tree,binary_code);5.6.1树的存储结构;父亲表示法;算法5-17：查找父亲表示法的树的根结点FindRoot(tree,x);孩子表示法;孩子表示法;孩子兄弟表示法;5.6.2树、森林与二叉树的转换;算法5-18：查找树中带有指定数据的结点Search(tree,x);森林与二叉树的转换;5.6.3树与森林的遍历