软考（中级）软件设计师核心笔记（8）数据结构——树与二叉树
三、树与二叉树1、树1.定义树的定义是递归它表明了树本身的固有特性也就是一棵树由若干子树构成而子树又由更小的子树构成2.概念根节点、叶子节点父子节点兄弟节点同一层次的节点节点度某一节点子树的个数树度对于整棵树而言各节点度的最大值分支节点非终端节点度不为0的节点层次根为第一层以此类推树的高度最大层次树2、二叉树1定义二叉树是nn 0个节点的有限集合空树n为0或是由一根节点及两颗不相交的切分别左右对称的二叉子树所构成具有递归性。树度与节点度都为2n个节点的二叉树高度最高为n最低为log2n1log2n表示n是2的多少次幂设二叉树的节点个数为7其树高度最高为7单支树高度最低为log2^71即(2^22存储)1.数组顺序存储补充成满二叉树后存储在数组中根据节点编号即可还原成树存储在数组当中编号1234567值123--4-)2.链式存储1.二叉链式存储结构左节点指针、值与编号、右节点指针当二叉树有k个节点时节点中必定有k1个空子节点指针2.三叉链式存储结构左节点指针、值与编号、右节点指针、父节点编号3特性)1.节点在二叉树的第i层上i1最少有1个节点最多有2^(i-1)个节点)2.高度高度为k的二叉树k1最多有2^k-1个节点)3.编号如果对一棵有n个节点的完全二叉树编号从第1层到log2n1层每层从左到右11.如果i1则i无父节点是二叉树的根2.如果i1则父节点是 i/2除不通则向下取整3.如果2in则其节点为叶子节点无左子节点4.如果2i5.如果2i1n则其节点为叶子节点无右子节点6.如果2i1)4.形态数递增公式A[n] ∑m0,m1.0个节点的二叉树形态只有一种空树2.1个节点的二叉树形态只有一种单节点树3.2个节点的二叉树形态套入公式 A[2] ∑m0,m快速计算4.3个节点的二叉树形态套入公式 A[3] ∑m0,m快速计算5.4个节点的二叉树形态套入公式 A[4] ∑m0,m快速计算A[0]有1种形态A[1]有1种形态A[2]有2种形态A[3]有5种形态)5.分支枝丫数对任何一颗二叉树如果其叶子节点数为n0度为0度为2的节点树为n2则n0n211.一棵树从根向叶子伸展根据度的定义节点不包含根节点数为k则伸展枝丫数为k枝丫数n0*0n1*1n2*2···nk*k2.一棵树从叶子向根回溯根据父子关系每个节点都会通过1根枝丫与其父节点连接除了根节点枝丫数节点总数-1(n0n1n2···nk)-13.二叉树度为2(n0n1n2)-1 n0*0n1*1n2*2 等同于 n0n21设已知树T的度为4度为4的节点数有7个度为3的节点数有5个度为2的节点数有8个度为1的节点数有10个n0?n110n28n35n47求节点总数套入伸展公式n0*0n1*1n2*2···nk*k 1*102*83*54*7 10161528 69求叶子节点数度为0套入叶子回溯公式节点总数-1(n0n1n2···nk)-1 69(n010857)-1 n069-(10857)1 n0404遍历)1.遍历方式1.前序遍历递归遍历遍历顺序 根 》左子树 》右子树遍历结果124578362.中序遍历递归遍历遍历顺序 左子树 》根 》右子树遍历结果427851363.后序遍历递归遍历遍历顺序 左子树 》右子树 》根遍历结果487526314.层次遍历逐层遍历遍历结果12345678)2.反向构造方法第一步先根据前序和中序将根区分出来并划分左右子树第二步再根据子树将新的根划分出来直至还原设前序序列ABHFDECG中序序列HBEDFAGC推算还原二叉树思路1.通过前序得出A为根2.已知A为根通过中序得出HBEDF为左子树GC为右子树AHBEDFGC3.已知HBEDF为左子树通过前序ABHFDECG得出B为左子树根节点ABGCHEDF4.已知B为左子树根节点通过中序HBEDFAGC得出H在B之前并且H是中序中第一个节点说明H在B左侧并且H下再没有子树ABGCHEDF5.已知H为B的左子树并且EDF非H下子树通过前序得出ABHFDECGF为B的右子树ABGCHFDE6.已知DE为F下的子树通过中序HBEDFAGC得出F为最后说明ED并非F的右子树E在D前表示E为D的左子树并通过前序ABHFDECG可验证左子树是否准确ABGCHFDE7.已知A为根节点BHFDE为左子树通过前序ABHFDECG得出C为根节点ABCHFGDE8.已知C为根节点通过中序HBEDFAGC得出G为C的左子树ABCHFGDE5排序左子树小于根右子树大于根第一个值为根从左到右排列同一个层次的节点其关键字呈现有序排列的特点最大高度值n最小高度值满二叉树[log2n]1设待排序序列{89, 48, 112, 20, 56, 51}8948112205651)1.查找节点查找关键字左子树小于根右子树大于根如查找关键字56小于根节点89得出在左侧 》小于左子树根节点48得出在右侧得出结果)2.插入节点1.若该键值节点已存在则不再插入2.若查找二叉树为空树则以新节点为查找二叉树单节点树3.将要插入节点键值与插入后父节点键值比较就能确定新节点是父节点的左子节点还是右子节点)3.删除节点1.若待删除节点是叶子节点则直接删除2.若待删除节点只有一个叶子节点则将这个子节点与待删除节点的父节点直接连接3.若待删除的节点右两个子节点则在其左子树上用中序遍历寻找关键值最大节点并用此节点代替待删除节点6最优二叉树哈夫曼树二叉树代价最小的形态可以存在多种只要代价最小即可权值越大离根节点越近哈夫曼树中不存在只有一个子树的节点哈夫曼树中的节点总数一定为奇数权值相同的节点到树根的路径长度不一定相同)1.概念1.树路径长度叶子节点到根的枝丫树2.权权值节点当中的数值3.带权路径长度权值*树路径长度4.树带权路径的长度代价所有叶子节点带权路径的长度5.最优二叉树代价最小其中设叶子节点‘3’树路径长度为3节点当中数值为权值权值为3的带权路径长度3*3为9树带权路径长度代价为4*23*36*229其中设叶子节点‘3’树路径长度为2节点当中数值为权值权值为3的带权路径长度3*2为6树带权路径长度代价为4*26*33*235综上两图相比图1比图2代价更小所以图1为最优二叉树)2降低二叉树代价权值最大的节点放置根节点权值最小的节点放置离根最远的节点设叶子节点序列{1248}最优二叉树表现为例题叶子节点序列为529781423311求最优二叉树解思路1.先将叶子节点序列排序为3578111423292.先取最小两节点开始拼接完成后得出子节点序列为357811142329 》788111423293.78811142329 》811141523294.1415192329 》192329295.19232929 》2929426.292942 》42587.得出根节点5842 》1008.拼接所有子树到根节点下得出)3哈夫曼编码变长、压缩编码设某文档5个字符每个字符出现的频率为下表并在哈夫曼树中右侧节点表示1左侧节点表示0字符abcde频率%4010201614则求得最优二叉树结果为根据表格进行转换替换当中的数字为字母得出已知此哈夫曼树右侧节点表示1左侧节点表示0则可以得出根据上述分析得出结论a0b100c111d110e101定长a的长度为1位b/c/d/e的长度均为3位则平均定长为3变长a的长度为40%使用频率*1定长 0.4b~e定长都为360%b~e的使用频率总和为*3定长1.8平均变长为 0.41.8 2.2压缩比例3-2.2/3 ≈ 0.27 27%7特殊的二叉树)1平衡二叉树平衡因子右侧高度 - 左侧高度任意节点左右子树的深度相差不超过1每个节点的平衡因子只能是10-1)2线索二叉树遍历利用填补空节点指向遍历的前驱和后继
