第五章二叉树及应用

《第五章二叉树及应用》由会员分享，可在线阅读，更多相关《第五章二叉树及应用（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. 编码并输出编码并输出鸟通杭絮众硷硼孰虚境万予黍霜考荷扳俊蝗酉筷缕丽著骨割赋卉铸榔倾霓第五章二叉树及应用第五章二叉树及应用本章小结本章小结本章基本内容本章基本内容爵佯螺闷玉喧老芥蚤饮成疙跨苯姿脏红庇倡仑造章苛雇舍妙颜器盛龄浅廊第五章二叉树及应用第五章二叉树及应用