一.数组的存储地址1.一维数组arr[i]的地址 首地址 i x 元素大小2.二维数组行优先arr[ i ][ j ]的地址 首地址 i x 列数 jx 元素大小3.二维数组列优先arr[ i ][ j ]的地址 首地址 i x 行数 jx 元素大小二.树是n个节点的有限集。在任意一颗非空树1.有且只有一个根节点。2.当n1时其余节点可分为m(m0)个互不交互的有限集其中每一个集合本身又是一棵树并称为根的子树。三.二叉树1.二叉树每个节点最多有两个子节点的树结构。二叉树的子树顺序不能颠倒1.二叉树第i层最多有 2^(i-1)个节点i1。2.深度为k的二叉树最多有2^k - 1个节点。k1.3.对任何一棵二叉树T如果其终端结点数为n0度为2的结点数为n2则n0n21。完全二叉树最后一层可以不满一棵二叉树除了最后一层外其他层都是满的且最后一层的节点从左到右连续排列。2.遍历方式1. 先序遍历步骤1.访问当前根节点。2.递归遍历左子树。3.递归遍历右子树。2. 中序遍历步骤1.递归遍历左子树。2.访问当前根节点。3.递归遍历右子树。3. 后序遍历步骤1.递归遍历左子树2.递归遍历右子树。3.访问当前根节点。4.层序遍历按照从上到下、从左到右的顺序一层一层地访问二叉树的节点。类型定义节点数特点满二叉树所有层都满2^h - 1最严格完全二叉树除最后一层外全满最后一层从左到右连续2^(h-1) ~ 2^h - 1较严格平衡二叉树左右子树高度差 ≤ 1任意高度平衡二叉搜索树左 根 右任意有序普通二叉树无限制任意最宽松满二叉树是指每个非叶节点都有两个子节点且叶子节点没有子节点。四.赫夫曼树给定N个权值作为N个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优 二叉树也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。1.赫夫曼编码一种变长编码根据字符出现的频率来构造最优前缀码频率高的字符用短编码频率低的字符用长编码。2.赫夫曼编码优点WPLWeighted Path Length所有叶子节点的权值乘以路径长度之和。WPL Σ(叶子节点权值 × 叶子节点路径长度) 路径长度 从根到该叶子节点的边数或节点数 - 1压缩效率高频率高的字符编码短WPL 最小无歧义解码前缀码特性不会产生歧义自适应性强根据数据频率自动调整编码理论最优在变长编码中是最优前缀码广泛应用文件压缩、图像压缩等前缀码任何一个字符的编码都不是另一个字符编码的前缀。赫夫曼树的叶子节点权值 字符频率内部节点权值 左右孩子权值之和。贪心算法每次选权值最小的两个节点合并新节点权值为两者之和。1. 将每个字符看作一个叶子节点权值为频率 2. 从森林中选出权值最小的两个树 3. 合并这两棵树新树根权值为两者之和 4. 将新树放回森林 5. 重复步骤 2-4直到森林中只剩一棵树