数据结构第八次课-树BVIP免费

调课通知下周（第5周）星期一1~2节的数据结构课调到：下周（第5周）星期四5~6节教室：L24122.2.二叉树的性质二叉树的性质(3+2)(3+2)性质1:在二叉树的第i层上至多有22i-1i-1个结点（i>0）。性质2:深度为k的二叉树至多有22kk-1-1个结点（k>0）。性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）上堂课内容回顾1.1.树的基本知识树的基本知识树的定义、若干术语、逻辑结构、存储结构、基本运算对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：性质4:具有n个结点的完全二叉树的深度必为log2n＋1性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1时为根,除外）。ABCDEGFHIKJMLNO152346789101112131415ACBEDFGHIJ12435768910上堂课例题讨论问:设一棵完全二叉树具有1000个结点，则它有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。法1：先求全部叶子数。n0＝489(末层)＋11(k-1层)=500个；法2：先求2度结点数。n2=255(k-2层)＋244(k-1层)=499个；这两种方法的缺点：都要先计算树的深度k=log2n＋1=10;法3：无需求树深k，便可快捷求出完全二叉树的叶子数：完全二叉树的叶子数：nn00==n/2n/2////取大于n/2的最小整数值可由二叉树性质5轻松证明！(编号为i的结点，其孩子编号必为2i和2i+1)①②④⑧⑤⑨③??⑦……nn已知最后一个结点编号为n，则其双亲n/2肯定是最后一个非叶子结点。其编号之后的全部结点都是叶子了！故，n0=n-n/2=n/2n/2问:设一棵完全二叉树具有n个结点,第一个叶子节点的编号是？第i个呢？4.二叉树的存储结构一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。AABBCCDDEEFFGGHHII[1][2][3][4][5][6][7][8][9]AABBCCGGEEIIDDHHFF问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。T[0]一般不用讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AABB^^CC^^^^^^DD^^……EE[1][2][3][4][5][6][7][8][9].[16]ABECD缺点：①浪费空间；②插入、删除不便二、链式存储结构(1)用二叉链表即可方便表示。datadataleft_childleft_childright_childright_childdatadataleft_childleft_childright_childright_child二叉树结点数据类型定义：P106代码6-1一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。例1：ABECD^^AABB^^DD^^CC^^^^EE^^ABECD有n个结点的树采用二叉链表存储有多少空指针域？指针域有2n个，有效的为n-1个，剩余都为空指针。A∧B∧∧∧∧∧∧∧CDEFG∧∧∧∧∧∧ADEFBC∧∧G例2：ABDCEFG(2)树的三叉链表表示lchilddatarchildparentA∧∧BD∧∧E∧C∧F∧∧G∧ABDCEFG第6章树和二叉树（Tree&BinaryTree）6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用（今日授课内容是本章及本课程的重点）（今日授课内容是本章及本课程的重点）6.3遍历二叉树和线索二叉树一、遍历二叉树（TraversingBinaryTree）遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。遍历方法——牢记一种约定，对每个结点的查看都是“先左后右”。遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、RD、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：DLRLDRLRD先(根)序遍历中(根)序遍历后(根)序遍历注：“先、中、后”的意思是指访问...