五章节二叉树及应用

《五章节二叉树及应用》由会员分享，可在线阅读，更多相关《五章节二叉树及应用（82页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 二叉树及应用二叉树及应用一种重要的非线性结构一种重要的非线性结构藉胶谩刮讽兴厚潮赚澎甭寞掘链倡询取骚家薛午慑露廷爆瓢蜗箭覆咱皮扩五章节二叉树及应用五章节二叉树及应用学习要点：学习要点：二叉树的递归概念，这与二叉树各种基本运算具有密切关联。二叉树的递归概念，这与二叉树各种基本运算具有密切关联。满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。二叉树的顺序存储与二叉链表存储结构。二叉树的顺序存储与二叉链表存储结构。二叉树遍历的基本思想和基于递归与非递归实现算法。二叉树遍历的基本思想和基于递归与非递归实现算法。线索二叉树概念，二

2、叉树的线索化和遍历。线索二叉树概念，二叉树的线索化和遍历。Huffman树概念与基本算法；树概念与基本算法；Huffman编码和实现算法。编码和实现算法。2诌押浮宜惶被屉汰等氟裴楷诉椰鹊娩接坞客校韩泳立喝描卯宜萍讳圃垫学五章节二叉树及应用五章节二叉树及应用5.1 二叉树及其基本性质二叉树及其基本性质5.1.1 二叉树基本概念二叉树基本概念“二叉树二叉树”是一个满足下述条件的由结点组成的有限集合是一个满足下述条件的由结点组成的有限集合E： 当当E为空集时，定义其为空二叉树；为空集时，定义其为空二叉树； 当当E非空时，分为两种情形。非空时，分为两种情形。 如果如果E为单元素集合，定义其为一棵为单元

3、素集合，定义其为一棵根二叉树根二叉树； 如果如果E为多于一个结点的集合，则为多于一个结点的集合，则E中应当具有唯一一个结点中应当具有唯一一个结点r称称其为根结点，而集合其为根结点，而集合E=E r也是一棵二叉树，称为也是一棵二叉树，称为r的子二叉的子二叉树。此时，结点树。此时，结点r至多只能有两棵不相交的子二叉树，并且相应至多只能有两棵不相交的子二叉树，并且相应子二叉树有左右之分，分别称为子二叉树有左右之分，分别称为r的的左子树左子树和和右子树右子树。3掷詹宾娃券巳效枢浪神土阴姿尼怨友豁将敞恐帮陪维玫濒滇滁桔盲吩捆吐五章节二叉树及应用五章节二叉树及应用其它一些相关概念：其它一些相关概念：结点的

4、结点的度：度：结点拥有的子树棵数结点拥有的子树棵数 结点的结点的深度深度（层次层次）：）：根结点看做第根结点看做第0层，其余结点的层次值为其层，其余结点的层次值为其父结点所在层值加父结点所在层值加1 树的度：树的度：树中所有结点度的最大值树中所有结点度的最大值树的深度：树的深度：树中最大层次数树中最大层次数 4根结点、叶结点、内部结点根结点、叶结点、内部结点子结点、父结点、兄弟结点、堂兄弟结点、子结点、父结点、兄弟结点、堂兄弟结点、子孙结点、祖先结点；子孙结点、祖先结点；罕叠驼抢波阳挟凋缀散闯两落嗓语尔潮磷滋梦混散邓侠岳片梨龚宛拧栽恋五章节二叉树及应用五章节二叉树及应用5.1.1 二叉树基本概

5、念二叉树基本概念21、二叉树的特征、二叉树的特征二叉树可以没有任何结点，即是一个空二叉树。二叉树可以没有任何结点，即是一个空二叉树。二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点集合互不相交；集合互不相交；二叉树中结点的两棵子树有左、右之分，次序不能颠倒。二叉树中结点的两棵子树有左、右之分，次序不能颠倒。2、二叉树基本类型、二叉树基本类型5则修陶有携叹魄叮占嫡唬怕章循滞奇厩澈僧衫隶己镑睦诵耻栗蒸剿搪顽爬五章节二叉树及应用五章节二叉树及应用5.1.2 满二叉树和完全二叉树满二叉树和完全二叉树1、满二叉树、满二叉树 如果一棵二叉树满足下

6、述条件，就称其为满二叉树（如果一棵二叉树满足下述条件，就称其为满二叉树（full binary tree）：）： 每个结点或是度数为每个结点或是度数为2（具有两个非空子树）的结点，或是度（具有两个非空子树）的结点，或是度数为数为0的（叶）结点；的（叶）结点； 所有叶结点都在同一层。所有叶结点都在同一层。6屈织剪筷熟炊毯舰盐滤盔教鲁粘梁茹凝衰致半到众箱乏粹母哗辙尚爽詹酒五章节二叉树及应用五章节二叉树及应用5.1.2 满二叉树和完全二叉树满二叉树和完全二叉树22、完全二叉树、完全二叉树若一棵二叉树满足下述条件，就称其为完全二叉树（若一棵二叉树满足下述条件，就称其为完全二叉树（complete bi

7、nary tree）：）： 至多只有最下两层中结点的度数小于至多只有最下两层中结点的度数小于2； 最下一层的叶结点都依次排列在该层最左边位置。最下一层的叶结点都依次排列在该层最左边位置。7钙体羌参罗建揍淑棒虫温狼保浪术淫终琅兹骂桑陷悟索养肠蹿绅捉讨淤兄五章节二叉树及应用五章节二叉树及应用5.1.2 满二叉树和完全二叉树满二叉树和完全二叉树22、完全二叉树、完全二叉树2重点理解：重点理解：满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。空二叉树和根二叉树既是满二叉树，也是完全二叉树。空二叉树和根二叉树既是满二叉树，也是完全二叉树。完全二

8、叉树可以看作是在满二叉树的最下一层，从右向左连续去掉若完全二叉树可以看作是在满二叉树的最下一层，从右向左连续去掉若干个结点后得到二叉树。干个结点后得到二叉树。完全二叉树中的一个结点如果没有左子结点，就一定没有右子结点。完全二叉树中的一个结点如果没有左子结点，就一定没有右子结点。8心登蓟巫栏冲情砂轿孺须牙哉苦王栅复雅凸窃堆神啮憾擞钙爪微烹描萤蜒五章节二叉树及应用五章节二叉树及应用练习：练习：1、完全二叉树某结点若无右子树则定无左子树。、完全二叉树某结点若无右子树则定无左子树。2、完全二叉树某结点若无左子树则定无右子树。、完全二叉树某结点若无左子树则定无右子树。9姬拿展哩缨平谍孝槐壮嗽帛马养物狮虱

9、扑况蝗钞啮锰诱姿娩耻宴奥袁佬姬五章节二叉树及应用五章节二叉树及应用5.1.3 二叉树基本性质二叉树基本性质性质性质5-1 一棵二叉树第一棵二叉树第i（i0）层上至多只能有）层上至多只能有 个结点。个结点。102i证明：应用数学归纳法。证明：应用数学归纳法。二叉树第二叉树第0层有一个结点，即当层有一个结点，即当i=0时，时，2i=20=1成立。成立。假设结论对第假设结论对第i层成立，即第层成立，即第i层至多只能有层至多只能有2i个结点。注意到个结点。注意到二叉树每个结点的度最多为二叉树每个结点的度最多为2，第，第i+1层结点个数至多只能层结点个数至多只能是第是第i层结点个数的层结点个数的2倍，即

10、倍，即2*2i = 2i+1，归纳完成，命题得，归纳完成，命题得证。证。老取撩饶幼从伯漱栈纸晋驻混沥庄柏咽摸羊蒂要研募蓑索翻拧趟淖疼兆夸五章节二叉树及应用五章节二叉树及应用5.1.3 二叉树基本性质二叉树基本性质211性质性质5-2 树高为树高为k（k0）的二叉树，最多有）的二叉树，最多有 个结点。个结点。2k+1-1证明：证明： 由性质由性质5-1可知在树高为可知在树高为k的二叉树当中，第的二叉树当中，第0层有层有20个结点，第个结点，第1层有层有21个结点，第个结点，第2层有层有22个结点，个结点，第，第k层有层有2k个结点。由个结点。由此可知，树高为此可知，树高为k的二叉树结点个数总数为

11、的二叉树结点个数总数为20 + 21 + 22 + 2k。这是一个公比为这是一个公比为p=2的等比数列，前的等比数列，前k+1项和项和Sk+1为：为： Sk+1 =（a0 ak p）/（1p）= (202k 2)/(12) = (12k+1)/(12) = 2k+11蒲腾蛇定堵粮次拧粗涧罪差胎酶缎屎太铡签袱为植铺舰层穆箍题卖淤鄂蛰五章节二叉树及应用五章节二叉树及应用5.1.3 二叉树基本性质二叉树基本性质3性质性质5-3 如果二叉树中度为如果二叉树中度为0结点数为结点数为n0，度为，度为2结点数为结点数为n2， 则则 成立。成立。12n0=n2+1证明：设结点总数证明：设结点总数 n = n0

12、+ n1+ n2 又因为：结点数又因为：结点数n = 边数边数+1 边数边数 = n1+ 2*n2 即即n0 + n1 + n2 = n1 + 2n2 + 1 所以：所以：n0 = n2 + 1结点数结点数n = 边数边数+1吮拧乓愧揪霍择汗掏甘准迸扛赔汾因犊哪绽靡幌镑憋腺溶葬宋拭诞燃揍宴五章节二叉树及应用五章节二叉树及应用练习：练习：一棵树的度为一棵树的度为4，n4=2， n3=3， n2=4，求，求n0？13解：解： 结点数结点数 = 边数边数 + 1 n0+ n1+n2 +n3+n4 = n1+ 2*n2 + 3*n3 + 4*n4 + 1 n0 + 2 + 3 + 4 = 8 + 9

13、+ 8 + 1 n0=17寥套紧济纵段棘菊馒痴滩垛十闺筒耪使沦创哄加耍急并膝薛屎惫海源梢身五章节二叉树及应用五章节二叉树及应用练习：练习： 设完全二叉树有设完全二叉树有1000个结点，求叶子结点个数？有多少个个结点，求叶子结点个数？有多少个度为度为1的结点？度为的结点？度为2的结点呢？的结点呢？14解：设二叉树中叶子结点、度为解：设二叉树中叶子结点、度为1、度为、度为2的结点数目的结点数目 分别分别n0、 n1、n2 ， 其中完全二叉树中其中完全二叉树中n1只能为只能为1或或0，则：，则：n0+ n1+ n2 = 1000n0 = n2+ 1n1= 0 或或 n1=1n0 = 500n1 =

14、1n2 =499蒂啸设粮肆拱卯鞠撤班就云傅僵互酬则愉劲荆茸烤彬潍嗜灯您逻糖焉缆周五章节二叉树及应用五章节二叉树及应用复习两个概念：复习两个概念：（1）满二叉树满二叉树：深度为：深度为k的满二叉树有的满二叉树有 个结点。个结点。152k+1-1 对满二叉树按层次从上到下，从左到右，不留一个空对满二叉树按层次从上到下，从左到右，不留一个空位进行编号，号码位进行编号，号码1n。（2）完全二叉树完全二叉树：结点数为：结点数为n的完全二叉树上各个结点与同深的完全二叉树上各个结点与同深度的满二叉树前度的满二叉树前n个相应位置结点编号一一对应。个相应位置结点编号一一对应。固很恨郸引查池柯路馏遭胡赖谤辐雀社仓

15、拳选户乓逾谦蓖装渊陶肪弗沙淫五章节二叉树及应用五章节二叉树及应用5.1.3 二叉树基本性质二叉树基本性质416性质性质5-4 设设BT为具为具n个结点的完全二叉树，将个结点的完全二叉树，将BT所有结点按照所有结点按照从上到下、从左到右的顺序（二叉树的层序）进行编号。则从上到下、从左到右的顺序（二叉树的层序）进行编号。则BT中任意结点中任意结点N的序号的序号i（1in）具有下述性质。）具有下述性质。（1）若）若i=1，则，则N为为BT根结点，根结点，N无父结点；无父结点；（2）若）若i1，则，则N父结点序号为父结点序号为 （即（即i除以除以2后向下取整）；后向下取整）；（3）若）若2in，则，则

16、N无左子树，否则其左子结点（即左子树的根无左子树，否则其左子结点（即左子树的根结点）序号为结点）序号为2i；（4）若）若2i+1n，则，则N无右子树，否则其右子结点（即右子树的无右子树，否则其右子结点（即右子树的根结点）序号为根结点）序号为2i+1。宽道彭慰可丘跺蹭甚凿帐皆毙净造京缸锭欧堑踢衔皿刻剐犁划佐觅迹撂镭五章节二叉树及应用五章节二叉树及应用练习：练习：1、1000个结点的完全二叉树最大的分支结点编号为个结点的完全二叉树最大的分支结点编号为 。2、n个结点的完全二叉树深度为个结点的完全二叉树深度为 。17500int（log2n）承勺啤镀坚盎蜀舶歹逼口笑堑曲照喂撼例轨痈健霖点痕女栽痢吠套

17、桌来络五章节二叉树及应用五章节二叉树及应用5.2 二叉树存储二叉树存储5.2.1 二叉树顺序存储二叉树顺序存储 预留最大空间预留最大空间 深度为深度为k的二叉树预留的二叉树预留2k+1-1个存储单元，按编号顺序存个存储单元，按编号顺序存储，遇空结点留空位。储，遇空结点留空位。 18早碧哩跃半财洞泽怔漓识迅谤贿杏协裴似隧匪肛跑针幌尸捞线翅噪滦泄耐五章节二叉树及应用五章节二叉树及应用5.2.1 二叉树顺序存储二叉树顺序存储2适合满（完全）二叉树，求双亲、孩子方便适合满（完全）二叉树，求双亲、孩子方便不适合深度较大、结点不多的二叉树不适合深度较大、结点不多的二叉树19著椅叛翻晰千顺嫉申搬德襟驱敏距竖

18、厂盛枕之院损常颁枚尧侯节驱釉本溪五章节二叉树及应用五章节二叉树及应用5.2.2 二叉树链式存储二叉树链式存储1、二叉链表存储、二叉链表存储 让一个存储结点只包含与其子树的邻接关系，那么就是让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。二叉树的二叉链表存储结构。20架棕呕活旭悟氏现卒垃熊斯挺历匀蹿秘潘蹦烦榨钙蔡斋房坪赞歼斟犹依云五章节二叉树及应用五章节二叉树及应用5.2.2 二叉树链式存储二叉树链式存储1、二叉链表存储、二叉链表存储221用用C语言定义二叉链表的结构类型如下：语言定义二叉链表的结构类型如下： struct node DataType data; /*

19、定义数据域，定义数据域，DataType代表实际需要的类型代表实际需要的类型 */ struct node *lch; /* 定义左孩子域，指向左孩子地址定义左孩子域，指向左孩子地址 */ struct node *rch; /* 定义右孩子域，指向右孩子地址定义右孩子域，指向右孩子地址 */ ; typedef struct node bitree; /* 定义二叉树结点类型为定义二叉树结点类型为bitree */彤咯至刨瞥疯良饭淳呜茵甜或慕缅节奠树仇娥销蹄略管袍皆凭捧劣楔卸达五章节二叉树及应用五章节二叉树及应用1、二叉链表存储、二叉链表存储3算法算法5-1 创建一棵只有根结点的二叉树算法。

20、创建一棵只有根结点的二叉树算法。 创建只有以创建只有以x为根结点的二叉树为根结点的二叉树Bt，x的数据类型为的数据类型为DataType，相，相应结点的应结点的Lchild和和Rchild域均取值域均取值NULL，返回指向根结点的指针。，返回指向根结点的指针。2200Create_Bt(DataType x)01 02 bitree *Bt,*ptr;03 ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点申请存储结点 */04 Bt=ptr;05 ptr-data = x;06 ptr-lch = NULL;07 ptr-rch = NULL

21、;08 return (Bt);09 易溶苫泛恩婿叠挎婶悟筷鳖鸿抡抱罢洋阳遮追璃枯嫩嗡锭蛮赂哩烹倔雄辅五章节二叉树及应用五章节二叉树及应用1、二叉链表存储、二叉链表存储4算法算法5-2 在指定左子结点处插入一个新结点。在指定左子结点处插入一个新结点。 已知二叉链表已知二叉链表Bt，在指针，在指针Parent所指结点左子结点处插入一个数所指结点左子结点处插入一个数据元素值为据元素值为x的新结点，使之成为的新结点，使之成为Parnet所指结点新的左子树根结点。所指结点新的左子树根结点。23 bitree *Inl_Bt(bitree *Bt, bitree *Parent, DataType x)

22、 if (Parent = NULL) printf (位置错！位置错！); return (NULL); ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点空间申请存储结点空间 */ ptr-data = x; ptr-lch = NULL; ptr-rch = NULL; if (Parent-lch = NULL) /* Parent所指结点左子树为空所指结点左子树为空 */ Parent-lch = ptr; else /* Parent所指结点左子树非空所指结点左子树非空 */ ptr-lch = Parent-lch; Parent

23、-lch = ptr; return(Bt) 苑补滴校友谰颗驾祝魁权簇灵江宫令丫凸葡歼荷缠熏睡娩雨狗骂低涯掂翔五章节二叉树及应用五章节二叉树及应用5.2.2 二叉树链式存储二叉树链式存储22、三叉链表存储、三叉链表存储 同时反映当前结点与其左子树的根结点、右子树的根同时反映当前结点与其左子树的根结点、右子树的根结点和与其父结点关联。结点和与其父结点关联。24藏篓丧承体统鞍谓巢室惯荣仰胆束咆杉曳寿纳赡蚕暮悬逃机案钠最瑰铡央五章节二叉树及应用五章节二叉树及应用5.2.2 二叉树链式存储二叉树链式存储22、三叉链表存储、三叉链表存储225府佩家晌硕域泉匙疮粳勺破翁龟娟密殴荒台什屿宏巨萧限砷射帝飘逐或

24、歹五章节二叉树及应用五章节二叉树及应用5.3 二叉树的遍历二叉树的遍历按照某种确定方式对二叉树进行访问，但要求二叉树中每按照某种确定方式对二叉树进行访问，但要求二叉树中每个结点被访问一次且只被访问一次。个结点被访问一次且只被访问一次。1、先序、中序和后序遍历、先序、中序和后序遍历对左、右子树，限定对左、右子树，限定“先访左后访右先访左后访右”，那么访问结点的，那么访问结点的顺序有三种不同的组合形式：顺序有三种不同的组合形式：TLR、LTR、LRT。通常，称通常，称TLR为二叉树的先序（先根）遍历，为二叉树的先序（先根）遍历， LTR为中序为中序（中根）遍历，（中根）遍历， LRT为后序（后根）

25、遍历。为后序（后根）遍历。26凸铰秀遥貌桂茧鲍事走跺钻脆凶错寓四暴缴敞腺凰媒奸绸而胰汀盒弓踊脏五章节二叉树及应用五章节二叉树及应用例子：例子：以三种遍历方式访问如图所示的二叉树。以三种遍历方式访问如图所示的二叉树。27解：先序遍历序列解：先序遍历序列 A-B-D-H-E-C-F-I-G-J-K中序遍历序列中序遍历序列 D-H-B-E-A-I-F-C-J-G-K后序遍历序列后序遍历序列 H-D-E-B-I-F-J-K-G-C-A坏而望戏瑚哉略巾饯霉牲倒丧杨氟费速豆灯碍厨竖某其渡像休敖出汇爹部五章节二叉树及应用五章节二叉树及应用例子：例子：已知二叉树先序遍历序列是已知二叉树先序遍历序列是A-B-C

26、-D-E-F-G，中序遍历序，中序遍历序列是列是C-B-D-A-E-G-F。由这两个序列可唯一确定一棵二叉树。由这两个序列可唯一确定一棵二叉树。28解：从先序遍历序列第一个结点可知二叉树根结点是解：从先序遍历序列第一个结点可知二叉树根结点是A。由结点。由结点A在在中序遍历序列里位置可知该根结点左子树包含结点中序遍历序列里位置可知该根结点左子树包含结点C-B-D，右子树包，右子树包含结点含结点E-G-F，如图，如图5-22所示。由中序序列片段所示。由中序序列片段C-B-D可知，可知，B是是A左子树根结点，再结合先序序列片段左子树根结点，再结合先序序列片段B-C-D可知，可知，C和和D分别是分别是

27、B的的左右子结点。由先序序列片段左右子结点。由先序序列片段E-F-G可知，可知，E是是A的右子结点，再由的右子结点，再由先序序列片段先序序列片段F-G和中序序列片段和中序序列片段G-F可知，可知，F不能是不能是E的左子结点，的左子结点，故只能是故只能是E的右子结点，并且的右子结点，并且G是是F的左子结点。的左子结点。推茵咯塌傲蜂疾紊毛疏毒踏球返晨赚永斧解涧惋烟陆罪厄涪换度祟盒酝意五章节二叉树及应用五章节二叉树及应用29溅瑶宗措腺笨酶呛蛹捕待邑蛾老令逗桩辞慢匝稳灌猴帐哈融累敲父胁岗菌五章节二叉树及应用五章节二叉树及应用练习：练习：1、已知二叉树先序遍历序列为、已知二叉树先序遍历序列为ABCDEF

28、GH，中序遍历序列为，中序遍历序列为CDBAFEHG，试画出此二叉树。，试画出此二叉树。2、已知二叉树后序遍历序列为、已知二叉树后序遍历序列为DCBFHGEA，中序遍历序列为，中序遍历序列为CDBAFEHG，求先序遍历序列。，求先序遍历序列。30凌娇当婿坑免捅嚼妖荷刚衙奇复朵划布合蜜绩枫隔掉桑晕痉绝万渣纹众瓦五章节二叉树及应用五章节二叉树及应用5.3 二叉树的遍历二叉树的遍历22、基于递归遍历算法、基于递归遍历算法递归步骤递归步骤（先序遍历）：（先序遍历）： 访问根结点；访问根结点； 先序遍历访问左子二叉树；先序遍历访问左子二叉树； 先序遍历访问右子二叉树。先序遍历访问右子二叉树。31估墒燥训

29、吮盒禁膏幢烩睛犀婆茄姻粗衷薯翰川僧撇识您惟混激急叛佑箍鹃五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法2算法算法5-4 二叉树先序遍历递归算法。二叉树先序遍历递归算法。 已知二叉树已知二叉树Bt，对其进行先序遍历，若二叉树为空，则为空操作；否则进，对其进行先序遍历，若二叉树为空，则为空操作；否则进行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树的右子树。的右子树。3200 Pret_Bt(bitree *Bt)01 02 if (Bt != NULL)03 04 printf (

30、%c, Bt-data); /* 访问根结点访问根结点 */05 Pret_Bt(Bt-lch); /* 先序遍历左子树先序遍历左子树 */06 Pret_Bt(Bt-rch); /* 先序遍历右子树先序遍历右子树 */07 08 测烹记励泊捕觅晾臆伍冉锅雇烘恢呀想待隋陕事同专所舱授谱佃纶蓬滇上五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法2基于递归调用先序遍历基于递归调用先序遍历:33剧菱猛僧着春片瞻峡舒缘痛陕浓奉庚头头升沦砸砂皿房誓膘棒钳岸箔罩职五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法2先序递归算法应用实例先序递归算法应用实例:

31、先序建立二叉树先序建立二叉树bitree *creat() bitree *t; int x; scanf(“%d”,&x); if (x=0) t=NULL; else t=(bitree *) malloc (sizeof(bitree); t-data=x; t-lch=creat(); t-rch=creat(); return t; 番爬裤捻缨心侵涕冻漓锨诛韶骨站柿铺致今整业怔驳剖募宙动筷垛岁毛诱五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法2先序递归算法应用实例先序递归算法应用实例:先序建立二叉树先序建立二叉树(续续)主程序调用主程序调用:main()

32、bitree *root; root=creat(); 例：例：建立如图二叉树应该如何输入？建立如图二叉树应该如何输入？练习：练习： 测试用例：测试用例：1 2 3 0 0 4 0 5 0 0 6 0 0 问：画出建立的二叉树？问：画出建立的二叉树？劳鞋让两核罩垄紊彪榆谨啡巢杠栋面侥咆朗旬疫免疙籍展吾父赶慌比峨旦五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法3算法算法5-5 二叉树中序遍历递归算法。二叉树中序遍历递归算法。 已知二叉树已知二叉树Bt，对其进行中序遍历，若二叉树为空，则为空操作；否则进，对其进行中序遍历，若二叉树为空，则为空操作；否则进行如下操作：中序

33、遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树的右子树。的右子树。3600 Indt_Bt(bitree *Bt)01 02 if (Bt != NULL)03 04 Indt_Bt(Bt-lch);/* 中序遍历左子树中序遍历左子树 */05 printf (%c, Bt-data);/* 访问根结点访问根结点 */06 Indt_Bt(Bt-rch);/* 中序遍历右子树中序遍历右子树 */07 08 壮躬貌白昼相列富姚迢狸抹钉迹廊爪排烃频淑贡吞掠碴风奴扯顺睡丈引队五章节二叉树及应用五章节二叉树及应用2、基于递归遍历

34、算法、基于递归遍历算法3基于递归调用中序遍历基于递归调用中序遍历:37武丹洗剔葵识宝溶仔堰殷谆桃既环庸俺髓浚做濒态铺帝沤吕迪属宛焦曰警五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法4算法算法5-6 二叉树后序遍历递归算法。二叉树后序遍历递归算法。 已知二叉树已知二叉树Bt，对其进行后序遍历，若二叉树为空，则为空操作；否则进，对其进行后序遍历，若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉树根结点。树根结点。3800 Postv_Bt(bitree

35、 *Bt)01 02 if (Bt != NULL)03 04 Postv_Bt(Bt-lch); /* 后序遍历左子树后序遍历左子树 */05 Postv_Bt(Bt-rch); /* 后序遍历右子树后序遍历右子树 */06 printf (%c, Bt-data); /* 访问根结点访问根结点 */07 08 称葛抉国朋升恶谭酷尹嫌囱澎坝随茬闹北杭衡残瞎亦汪椽拥榔驹烩颊砚红五章节二叉树及应用五章节二叉树及应用2、基于递归遍历算法、基于递归遍历算法4基于递归调用后序遍历基于递归调用后序遍历:39畜伦性专啦院婉神箔雷茵将废釉走颐过窿腐仓措隙锚先菜免会整怕靠适翠五章节二叉树及应用五章节二叉树及应

36、用5.3 二叉树的遍历二叉树的遍历33、基于非递归遍历算法、基于非递归遍历算法非递归遍历算法中，需要做出三条假设：非递归遍历算法中，需要做出三条假设： 设置一个一维数组设置一个一维数组Ss作为顺序栈以临时保存遍历时遇到的结点信作为顺序栈以临时保存遍历时遇到的结点信息，其栈顶指针为息，其栈顶指针为Ss-top，初始时为，初始时为0。 采用二叉链表结构保存需要遍历的二叉树，起始指针为采用二叉链表结构保存需要遍历的二叉树，起始指针为Bt，每个结，每个结点包含点包含Data、Lchild和和Rchild等三个域。等三个域。 对结点进行的对结点进行的“访问访问”理解为将该结点的理解为将该结点的Data域

37、的值打印出来。域的值打印出来。40皆辫擂述拆搂搏瑟送靡腐吃蓖嘛乡脏栓赠菠扒县缮蛤匀突缺肇陌孪贴奉稻五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法2算法算法5-7 先序遍历二叉树的非递归算法。先序遍历二叉树的非递归算法。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的先序遍历序列。，要求打印出该二叉树的先序遍历序列。4100 Pre_Bt(bitree *Bt)01 02 bitree *p;03 bitree *stack10; /* 定义栈数组定义栈数组 */04 int top=-1; /* 定义栈顶下标定义栈顶下标top并赋初值并赋初值-

38、1 */05 printf(nOutput preorder:);06 p= Bt;07 while(p!=NULL | top!=-1)08 if (p!=NULL)09 10 printf(%d ,p-data); /* 访问该结点访问该结点 */11 top=top+1;stacktop=p; /* 访问后入栈访问后入栈 */12 p=p-lch; /* 继续深入左孩子继续深入左孩子 */13 14 else15 16 p=stacktop;top=top-1; /* 遇空出栈，栈顶给遇空出栈，栈顶给p */17 p=p-rch; /* 转向右孩子转向右孩子 */18 19 针奎羔鞭茅哇

39、霓奖皮聪电桐擎弥鸡更驴纳鸣弗果笋殷熟队刊誊繁步刻竿角五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法2基于非递归二叉树先序遍历：基于非递归二叉树先序遍历：42诣冻鄂僳效喊掺广赤筷帅喉悼景畦验苫砖趟珊谚睫浚蛋翅恳吃挽寐差囊拨五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法3中序非递归遍历算法流程中序非递归遍历算法流程:v bitree *p; 定义及初始化栈定义及初始化栈;v p=root;v while(p!=NULL | 栈不空栈不空)v if (p!=NULL) v p进栈；进栈；p=p-lch;v elsev 栈顶给栈顶给p并出

40、栈；并出栈；输出输出p；p=p-rch;刮砰原败爆征挖联复绸拷栓疟攘款途嘶栗穆葫绥铭软掺怔染链索鲜稿呸勾五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法3算法算法5-8 中序遍历二叉树的非递归算法。中序遍历二叉树的非递归算法。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的中序遍历序列。，要求打印出该二叉树的中序遍历序列。4400 In_Bt(bitree *Bt)01 02 bitree *stack10; /* 定义栈数组定义栈数组 */03 int top=-1; /* 定义栈顶下标定义栈顶下标top并赋初值并赋初值-1 */04 bitr

41、ee *ptr;05 ptr = Bt;/* ptr是工作指针是工作指针 */06 do07 08 while (ptr != NULL) /* 一直朝左子树深入下去一直朝左子树深入下去 */09 10 top+; /* 调整栈顶指针调整栈顶指针 */11 stacktop = ptr; /* ptr所指结点进栈所指结点进栈 */ 12 ptr = ptr-lch;1314 if (Ss_top !=-1 )15 16 ptr = stacktop ; /* 栈顶元素赋值给栈顶元素赋值给ptr */17 top - ; /* 出栈出栈 */18 printf (%d , ptr-data);

42、/* 访问该结点访问该结点 */19 ptr = ptr-rch; /* 进入右子树访问进入右子树访问 */20 21 while(ptr !=NULL)|(top!=-1);22 扣杆芬瑞债钝绣洛翠郎干酉切处狄坤募渠芹唐鹃炯饱揣滋身轨佐湾裔涝糖五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法3基于非递归二叉树中序遍历（基于非递归二叉树中序遍历（1-4趟）：趟）：45铜囱锻滴埃成沧略骏侈再秀卉跪微阻产契肇韵井写讨影唤荒楼沫狡秆购獭五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法3基于非递归二叉树中序遍历（基于非递归二叉树中序遍历（1-

43、4趟）：趟）：46被精罢褥底艰腺租唯翘藤剑辽朴酒憨漓妒搁典讼刽玩藉牢萎使凰湛首拽厘五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法4算法算法5-9 后序遍历二叉树的非递归算法（略）。后序遍历二叉树的非递归算法（略）。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的后序遍历序列。，要求打印出该二叉树的后序遍历序列。47算法要点：算法要点：由于后序遍历是由于后序遍历是“左、右、根左、右、根”，因此在后序遍历过程中搜索到某，因此在后序遍历过程中搜索到某个结点时，不是马上访问它，而是将其作为相应子树根结点保存在个结点时，不是马上访问它，而是将其作为相应子

44、树根结点保存在工作栈中，然后沿着其左子树继续深入直到工作栈中，然后沿着其左子树继续深入直到“最左下最左下”结点。完成结点。完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，但仍对其左子树访问后，从工作栈顶元素中获得相应根结点信息，但仍然不能马上进行访问，而是在工作栈中对其进行然不能马上进行访问，而是在工作栈中对其进行第二次保存第二次保存，同时，同时对其右子树进行遍历。在访问完右子树后，从工作栈中得到根结点对其右子树进行遍历。在访问完右子树后，从工作栈中得到根结点信息，由此实现对相应根结点访问。信息，由此实现对相应根结点访问。即浸琳凝阵蔚舅汇达掉涩蜡你皿粗蛙惭怯坷获珠胳摩诚产茂沼巢喜缅草

45、颐五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第1-3趟运算变化：趟运算变化：48淡碉益艰藕则在侍取询持擞僚痛艺峡责誓院冉输冗鹊徊泞处秀蛔邻牢癌札五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第4趟运算变化：趟运算变化：49秘枝只帕恳拿症源丛损伶某僻占噎徽熊罚憾父麻嘶各壬坛刻捆沛查敏靖酶五章节二叉树及应用五章节二叉树及应用3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第5-7趟运

46、算变化：趟运算变化：50根趴阳阵缴距捕踪滦沁宛惰乘窒屠拥簧补考软寡迭蓑孙向榴薯哪详鼓账叠五章节二叉树及应用五章节二叉树及应用上机：上机：1、用先序、用先序递归方法递归方法建立一棵二叉树；建立一棵二叉树；2、用中序、用中序非递归非递归方法遍历该二叉树。方法遍历该二叉树。51暖寇跺函雨蓝瘫扯潍舔鹰莆锗沦捕与井劣忙师然煮亢售獭阮突诚酋滔恨赤五章节二叉树及应用五章节二叉树及应用5.4 线索二叉树线索二叉树5.4.1 线索与线索二叉树线索与线索二叉树 结合遍历方式特点使用这些空链域来存放相应前驱或后继信结合遍历方式特点使用这些空链域来存放相应前驱或后继信息即前驱或后继的地址。息即前驱或后继的地址。 当前

47、结点左孩子域非空时，保留原指针不变；当左孩子域为空时，当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，添加该结点在相应历序列中前驱结点地址。添加该结点在相应历序列中前驱结点地址。 当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，添加该结点在相应遍历序列中后继结点地址。添加该结点在相应遍历序列中后继结点地址。52榆抑驮豌吝黑翅侈榜应圈波冰肇奖喧坊卒开影忽鲸蔽丽啸闷韦诧请烹券竞五章节二叉树及应用五章节二叉树及应用5.4.1 线索与线索二叉树线索与线索二叉树2一个中序线索二叉树的例子：一个中序线索二叉树的例子：53医另炭忽

48、皱香它舱扭辖似樊府汾譬偏弄稿必肝献沥孤顿望褐睛翘醇钦递紧五章节二叉树及应用五章节二叉树及应用5.4.2 创建线索二叉树创建线索二叉树1、创建线索二叉树结点、创建线索二叉树结点54算法算法5-10（线索二叉树结点结构）（线索二叉树结点结构） 01 struct ThreadNode /* 线索二叉树结点的定义线索二叉树结点的定义 */02 03 DataType info;04struct ThreadNode llink, rlink;05 int ltag, rtag;06 ;07 typedef struct ThreadNode ThreadTree; /* 线索二叉树类型的定义线索二叉

49、树类型的定义 */多蹲慰涅鸭墨织玉渍于瑶臀盆辱宗疆乖抑钢仪两艇盘名挎普五卑者猖惕直五章节二叉树及应用五章节二叉树及应用5.4.2 创建线索二叉树创建线索二叉树22、二叉树的线索化、二叉树的线索化55在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱前驱”和和“后继后继”信息。遍历过程中，附设指针信息。遍历过程中，附设指针pre，并始终保持指针，并始终保持指针pre指向当前访问的、指针指向当前访问的、指针p所指结点的前驱。将给定二叉树扩充为线索二所指结点的前驱。将给定二叉树扩充为线索二叉树的过程称为二叉树的线索化，也就是

50、线索二叉树的创建。叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。线索化实际上就是在遍历过程中线索化实际上就是在遍历过程中在当前结点的空链域中添加前驱或后在当前结点的空链域中添加前驱或后继指针继指针。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个工作指针工作指针pre始终指向刚访问过的结点，也就是说，当指针始终指向刚访问过的结点，也就是说，当指针p指向当前访问指向当前访问结点时，结点时，pre就指向就指向p的前驱结点。的前驱结点。置尤豢扇屯兑亨乍恨靖酬垦免捎鸟蒜菊床千帅朝屑蒲愿妄苔库窗琢宰双泽五章节二叉树及应用五章节二叉

51、树及应用5.4.2 创建线索二叉树创建线索二叉树33、线索二叉树遍历、线索二叉树遍历56以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算法。此时，算法关键点有二：法。此时，算法关键点有二： 怎样获取中序遍历的首结点？怎样获取中序遍历的首结点？从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的处于处于“最左下最左下”的结点，结点是的结点，结点是“最左下最左下”的含义是该结点再无左子的含义是该结点再无左子结点，亦即该结点的左指针域为空。结点，亦即该结点的左指针域为空。 怎样

52、获取在中序线索化链表中当前结点的后继结点？怎样获取在中序线索化链表中当前结点的后继结点？如果当前结点没有无右子树，则其后继结点即为其右指针域中后如果当前结点没有无右子树，则其后继结点即为其右指针域中后继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开始沿左指针行进，直到右子树始沿左指针行进，直到右子树“最左下最左下”结点，此即为当前结点的后结点，此即为当前结点的后继。继。咸垛歧么准而吱正掀幸帝嫁满傅旦魁胡墨降它难敞疟铬砾匣济童堆冠殴搀五章节二叉树及应用五章节二叉树及应用5.4.2 创建线索二叉树创建线索二叉树33、线索二叉树

53、遍历、线索二叉树遍历257算法算法5-12基于中序线索二叉树中序遍历算法基于中序线索二叉树中序遍历算法00 void thrInOrder(ThreadTree *root ) 01 02 ThreadTree *p;03 p = root-llink;04 if (p=NULL)05 return ;06 while ( p-llink!=NULL & p-ltag=0 )07 p = p-llink; /* 一直到一直到“最左下最左下” */08 while (p!=root) 09 10 printf(%d ,p-info);11 if ( p-rlink!=NULL & p-rtag=

54、0 ) /* 右子树不是线索时右子树不是线索时 */12 13 p = p-rlink;14 while (p-llink!=NULL&p-ltag=0)15 p = p-llink; /* 顺右子树的左子树一直向下顺右子树的左子树一直向下 */16 17 else18 p = p-rlink;19 20 员盛骑烧填败诺椿徒铣华梭该疹专粮链睹牟截挤峭姜萨窥腋买琼秒写禹期五章节二叉树及应用五章节二叉树及应用5.5 Huffman编码编码5.5.1 等长与非等长编码等长与非等长编码 所谓编码（所谓编码（code），就是用一组不同的代码表示一个数据对），就是用一组不同的代码表示一个数据对象集合中的每

55、个元素的过程。象集合中的每个元素的过程。1、两种基本编码类型、两种基本编码类型编码三要素：编码三要素： 唯一性：唯一性：发送方传输编码字段，接收方解码后必须具有唯一性，发送方传输编码字段，接收方解码后必须具有唯一性，解码结果与发送原文保持相同；解码结果与发送原文保持相同； 简洁性：简洁性：发送的编码应该尽可能做到简洁短小，减少存储代价和发送的编码应该尽可能做到简洁短小，减少存储代价和提高传输效率。提高传输效率。 前缀性：前缀性：两个编码字节不使用特殊标记如标点符号进行分隔，一两个编码字节不使用特殊标记如标点符号进行分隔，一个编码字节不能是另一个编码字节的前缀，应具有个编码字节不能是另一个编码字

56、节的前缀，应具有“前缀性前缀性”（Prefix Property）；）；58篱防茬险执应某奴廷沥贡献嚷毅凯滔墅持曰虞督桓忠患衡麦恳康字题缨奉五章节二叉树及应用五章节二叉树及应用5.5.1 等长与非等长编码等长与非等长编码22、最优二叉树与、最优二叉树与Huffman树树二叉树路径长度二叉树路径长度：一棵二叉树的所有从根结点到每个叶结点路径长：一棵二叉树的所有从根结点到每个叶结点路径长度之和称为该二叉树的度之和称为该二叉树的“路径长度路径长度”。叶结点的权叶结点的权：赋给二叉树叶结点一个具有某种意义的实数，则称此：赋给二叉树叶结点一个具有某种意义的实数，则称此数为该叶结点的数为该叶结点的“权权”

57、。二叉树带权路径长度二叉树带权路径长度：设二叉树具有：设二叉树具有n个带权的叶结点，则从根结点个带权的叶结点，则从根结点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的“带权路径长度带权路径长度”，记为：，记为：59WPL= wklk （wk是第是第k个叶结点权值，个叶结点权值， lk是第是第k个叶结点路径长度）个叶结点路径长度）“Huffman树树”：由带有权值的一组相同叶结点所构成二叉树当中，由带有权值的一组相同叶结点所构成二叉树当中，称其中带权路径长度最小的二叉树为是称其中带权路径长度最小的二叉树为是“最优二叉树最优二叉树”

58、。钠空贷吠店银佑泉仓箩孙喘邱强撇惟此椭村痘凝拓侍绞鬃山认颠缓赘框扎五章节二叉树及应用五章节二叉树及应用5.5.2 Huffman树构建思想树构建思想设有设有n个权值个权值w1、w2、w3、wn，则可按照下述步骤，则可按照下述步骤构造构造Huffman树：树：Step 1. 构造构造n棵只有一个根结点的二叉树森林棵只有一个根结点的二叉树森林 HT = T1，T2，T3，Tn，它们分别以，它们分别以w1、w2、w3、wn作为权值。作为权值。Step 2. 在在HT集合中，选取权值最小和次小的两个根结点作为一集合中，选取权值最小和次小的两个根结点作为一棵新二叉树的左子树和右子树。新二叉树根结点权值是

59、其左、右子棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子树根结点权值之和；树根结点权值之和；Step 3. 在在HT集合中，删除已经取为左、右子树的原两棵二叉集合中，删除已经取为左、右子树的原两棵二叉（根）树，并将新构成二叉树添加到（根）树，并将新构成二叉树添加到HT中；中；Step 4. 重复重复Step 2和和Step 2至至HT只剩下一棵二叉树，此即是所只剩下一棵二叉树，此即是所求求Huffman树。树。60瓣猩悉卓堪垛骋卢女晋铺蜜绩获析赞畴企属甥苫运妓氰像投批空急典同窍五章节二叉树及应用五章节二叉树及应用5.5.2 Huffman树构建思想树构建思想2构造具有四个分别带有权

60、值构造具有四个分别带有权值1、3、5、7的的Huffman树如下图所示：树如下图所示：61阂冉重萝拿己疲捡囊蝉多喘竣仆硒感巳缝押谐开桶涩昂雍傅测钾牢赠褒抑五章节二叉树及应用五章节二叉树及应用练习：练习： 已知有已知有6个叶子，值分别为个叶子，值分别为A、B、C、D、E、F，它们的权值分别为，它们的权值分别为4，9，1，3，2，1，试构造哈夫，试构造哈夫曼树（左权曼树（左权右权）。右权）。62俄黔研岸婉魔怔幕敖任烃窿迟柯掘非汞绊膨聊糊玫犯伤棕珍磕野控备崔荫五章节二叉树及应用五章节二叉树及应用5.5.3基于顺序存储基于顺序存储Huffman树构造树构造1、Huffman树结点结构树结点结构问题：若

61、哈夫曼树有问题：若哈夫曼树有n0个叶子结点，则所有结点个叶子结点，则所有结点 个。个。632n0-1解：因为树中无度为解：因为树中无度为1的结点，的结点， 由二叉树的性质由二叉树的性质3知：知：n0=n2+1 所以：所以：n=n0+n2=n0+n0-1 =2n0-1u由于最终结果中结点个数已经确定，因此可采用顺序结由于最终结果中结点个数已经确定，因此可采用顺序结构存储存放所建构存储存放所建Huffman树树湿央蔗铜叶告牡叙柱挎仗榜拣六巡黑弟弄鲤募与野冬石铣话韩沾滁锚轨监五章节二叉树及应用五章节二叉树及应用5.5.3基于顺序存储基于顺序存储Huffman树构造树构造1、Huffman树结点结构树

62、结点结构2问题：结点结构如何构造？问题：结点结构如何构造？6400 struct node01 02 int weight;03 int parent,lch,rch;04 ;05 struct node HtreeMAX;众润算莲俩噎锐瞬坊盾元舰汤笆救报帽冈拈猫伪筒弘鹊唤喳舍橡毁读她巍五章节二叉树及应用五章节二叉树及应用5.5.3基于顺序存储基于顺序存储Huffman树构造树构造22、Huffman树构造算法树构造算法问题：算法如何构造问题：算法如何构造Huffman树？树？65原理：原理：找两找两无双亲无双亲且且权值最小权值最小结点合并，生成新结点，填写相关结点合并，生成新结点，填写相关信

63、息（信息（两结点双亲，新结点权值，新结点左、右孩子两结点双亲，新结点权值，新结点左、右孩子）。）。标噬石巳效义警西挽鼎抹领缆忽黔筷厘低当片任蹲啸铆压若砚命攫奔娱朽五章节二叉树及应用五章节二叉树及应用算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法 00 creat_huff(struct node Htree)01 02 int i,j,min1,min11,min2,min22;03 printf(nInput the count of leaves(10):);04 scanf(%d,&n); /* 读取叶子结点个数读取叶子结点个数n */05 for (i=0

64、;i2*n-1;i+) /* 数组数组Htree初始化初始化 */06 07 Htreei.parent=-1;08 Htreei.lch=-1;09 Htreei.rch=-1;10 11 printf(nInput the leavess weight:);12 for (i=0;in;i+) /* 读取各个叶子的权值并赋值到读取各个叶子的权值并赋值到Htree数组数组 */13 scanf(%d,&Htreei.weight);66狮架凹显工沥责桌噎怖难皱贡椿逗柜氏早婉丛莽孰禾残亦羚宋动醋匡断葵五章节二叉树及应用五章节二叉树及应用算法算法5-13 基于顺序存储基于顺序存储Huffman树

65、构造算法树构造算法2 14 for (i=n;i2*n-1;i+) /* 控制控制n-1次二叉树的合并次二叉树的合并 */15 16 min2=min1=MAX; /* min1、min2记录当前最小、次小权值记录当前最小、次小权值 */17 min11=min22=0; /* min11、min22记录当前最小、次小权值记录当前最小、次小权值结点位置结点位置 */18 for (j=0;ji;j+) /* 在在j的范围内，找最小、次小结点的范围内，找最小、次小结点 */19 20 if (Htreej.parent=-1)21 if (Htreej.weightmin1) /* 如当前权值比

66、最小结点还小如当前权值比最小结点还小 */22 23 min22=min11;24 min2=min1; /* 最小结点信息赋给次小最小结点信息赋给次小 */25 min11=j;26 min1=Htreej.weight; /* 当前权值信息赋给最小当前权值信息赋给最小 */27 28 else67现咳辗娶耙沂野玛蹿劳盐侗借杀禄魁殊邹耻栖睬桶茹机蹿陶橱淳莱潮壬奇五章节二叉树及应用五章节二叉树及应用算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法3 29 if (Htreej.weightmin2) /* 如当前权值比次小结点小如当前权值比次小结点小 */30 31

67、 min22=j;32 min2=Htreej.weight; /* 当前权值信息赋给次小当前权值信息赋给次小 */33 34 35 Htreemin11.parent=i; /* 设置最小权值结点的设置最小权值结点的parent域域 */36 Htreemin22.parent=i; /* 设置次小权值结点的设置次小权值结点的parent域域 */37 Htreei.weight=Htreemin11.weight+Htreemin22.weight; /* 设置新结点的权值域设置新结点的权值域 */38 Htreei.lch=min11; /* 设置新结点的设置新结点的lch域为最小结点域

68、为最小结点 */39 Htreei.rch=min22; /* 设置新结点的设置新结点的rch域为次小结点域为次小结点 */40 41 Htree2*n-2.parent=-1; /* 最后一个结点为根结点，最后一个结点为根结点，parent域为域为-1 */42 ;68刁伪惰宋标朗牺欺锣拆祁澡青霍排陛隐扮宅下苑募泥迫商跳裤犊症窍庙辙五章节二叉树及应用五章节二叉树及应用5.5.3基于顺序存储基于顺序存储Huffman树构造树构造33、Huffman树算法分析树算法分析69设有叶结点相应权值分别为设有叶结点相应权值分别为1，3，5，7。按照算法构建。按照算法构建Huffman树树过程如下图所示：

69、过程如下图所示：舞晴朱寺遭湛稼滚打龚霜函锈削呕荧获喷稠琉瘟班橡傲吾口岂洲蒙栈伴眼五章节二叉树及应用五章节二叉树及应用5.5.3基于顺序存储基于顺序存储Huffman树构造树构造33、Huffman树算法分析树算法分析70设有设有叶结点相应权值分别为叶结点相应权值分别为1，3，5，7。按照算法构建按照算法构建Huffman树过树过程如下图所示（续）：程如下图所示（续）：蓄碧诚薪榔祭匙军适讹怨攀芋惯影玄钠饮姓汉缨繁跑砌产茸叁陶回浅巩粮五章节二叉树及应用五章节二叉树及应用5.5.4 Huffman编码编码1、Huffman编码概念编码概念基于具体基于具体Huffman树的不等长编码就称为树的不等长编

70、码就称为Huffman编码。编码。首先得到需要编码的字符首先得到需要编码的字符c1、c2、cn在相应数据信息中出现的频在相应数据信息中出现的频率为率为p1、p2、pn；再以；再以c1、c2、cn作为叶结点，作为叶结点，p1、p2、pn作为相应权值，按照作为相应权值，按照Huffman算法构造一棵算法构造一棵Huffman树。树。其次，由构造的其次，由构造的Huffman树的根结点开始，在每个左分支上标注树的根结点开始，在每个左分支上标注0，右分支上标注右分支上标注1。这样，从根结点到每个叶结点的路径上由。这样，从根结点到每个叶结点的路径上由0、1组成组成的序列，就是该结点对应字符的编码。的序列

71、，就是该结点对应字符的编码。71凭嗅糖东扼诛猜痈祭洒聘恳私说拽板生鹊恤忿衔梨濒明死遇判丝栈叭往氮五章节二叉树及应用五章节二叉树及应用5.5.4 Huffman编码编码1、Huffman编码概念编码概念2编码步骤编码步骤1：先建先建Huffman树树72叶帆梧寥碟胆演碾戌呸帆翻汉挥予振窘屿伺盯酝呜抠眉系赛牢早抱盐眶拍五章节二叉树及应用五章节二叉树及应用5.5.4 Huffman编码编码1、Huffman编码概念编码概念2编码步骤编码步骤1：先建先建Huffman树（续）树（续）73昂陀吴辞切豌劫芜淆梧碟硫凯污凄取漳偏寅浓创旷偷朗及糖雕恭序盾胀姻五章节二叉树及应用五章节二叉树及应用5.5.4 Hu

72、ffman编码编码1、Huffman编码概念编码概念2编码步骤编码步骤2：再编码再编码74渔嘻陛巷锣迄圃蛋涂寄壮药迪弧硝弟轿剥律类掘痔唤幕妄于段锗疫幸倦痹五章节二叉树及应用五章节二叉树及应用5.5.4 Huffman编码编码22、Huffman编码算法编码算法问题：如何编码？问题：如何编码？原理：原理：从叶子结点到根结点顺着路径分支为其编码。从叶子结点到根结点顺着路径分支为其编码。75砒千努探攒蔼呵橡住喉耙买评惦润甲亚悦淌挖毁桃骂浪引帕牡拧骆某昨耍五章节二叉树及应用五章节二叉树及应用算法算法5-14 Huffman编码算法编码算法00 code_huff(struct node Htree)0

73、1 02 int i,j,k,pr,start;03 for (i=0;in;i+)04 05 j=n-2; 06 k=i; /* k记录当前编码结点，初始为叶结点位置记录当前编码结点，初始为叶结点位置 */07 while(Htreek.parent!=-1)08 09 pr=Htreek.parent; /* 记录记录k的父结点的父结点 */10 if(k=Htreepr.lch)11 codeij=0; /* 左分支编码为左分支编码为0 */12 else13 codeij=1; /* 右分支编码为右分支编码为1 */14 j=j-1;15 k=pr; /* 进到路径的上一个结点，直至根

74、结点进到路径的上一个结点，直至根结点 */16 17 codein-1=j+1; /* 存放编码的起始位置是存放编码的起始位置是j+1 */18 76忌吼蒙涤恨牌续垮脏攒近糙姻欲栽让脏袱浦稚选瞅水酚诫痪爪肆哭子疟茹五章节二叉树及应用五章节二叉树及应用算法算法5-14 Huffman编码算法编码算法219 printf(n The code are:n);20 for (i=0;in;i+)21 22 start=codein-1; /* 取出编码的起始位置取出编码的起始位置 */23 for (j=start;jn-1;j+) /* 逐个输出编码逐个输出编码 */24 printf( %-3d

75、,codeij);25 printf(n);26 27 77卑茂搪读涛峡硬糟吐涩航抉醉述瞧舆颗岩胜旋渗刃好虏突巡畔伶宪恶谈尉五章节二叉树及应用五章节二叉树及应用5.5.4 Huffman编码编码33、Huffman编码算法分析编码算法分析Huffman编码过程如下图所示：编码过程如下图所示：78黔瘴九测泡美笋勤客方沏歹蜘停饮荒都原笼牙汞甚蔼兵敝露蔡误挨藕剩沿五章节二叉树及应用五章节二叉树及应用练习：练习： 设有设有7个带权结点个带权结点A，B，C，D，E，F，G，其权值分别为，其权值分别为3，7，8，2，5，8，4，试以这，试以这7带权结点为叶子结点，构造一带权结点为叶子结点，构造一棵哈夫曼树

76、（左权棵哈夫曼树（左权右权）。右权）。79精镀仗镀绅财驳玉膘旨氓笺扭雌林顺讥捧辙渍咖嵌棵徐滇柜灿晨纤姻疥支五章节二叉树及应用五章节二叉树及应用练习：练习： 在一份报文中有五种字符，在一份报文中有五种字符，A，B，C，D，E，它们在报文，它们在报文中出现的频率比例为中出现的频率比例为4，7，5，2，9，试通过构造最优二叉树，试通过构造最优二叉树来确定每种字符的哈夫曼编码（左权来确定每种字符的哈夫曼编码（左权右权）。右权）。80扼常塔耘信匀哩及菇硅筋店殖赐熄冠匆残魂疮物编舌鱼碘衰挪土图参邮清五章节二叉树及应用五章节二叉树及应用上上 机：机：81理解建立理解建立huffman树的过程及编码过程。树的

77、过程及编码过程。 v1. 结点定义（需要至少结点定义（需要至少4个域：个域：weight，parent，lch，rch）v2. 定义数组定义数组v3. 输入叶子的个数输入叶子的个数nv4. 数组初始化数组初始化v5. 输入叶子的权值输入叶子的权值v6. 循环循环n1次做：次做：v （1）找两个最小权值及其下标）找两个最小权值及其下标v （2）合并，填写相关信息）合并，填写相关信息v7. 输出数组输出数组v8. 编码并输出编码并输出祷槛办铀珐淄翁祷寂姜莱橱箱牺誊嚎箍帕钧死卸宜范坪惦断葱贱钙稻濒驮五章节二叉树及应用五章节二叉树及应用本章小结本章小结本章基本内容本章基本内容朽核侦月獭徊杰驼迪痒麻告白蝶心击每裳脂搅翼烯腑戎首队表偿烈谅墅趴五章节二叉树及应用五章节二叉树及应用