11个数之和,问至少需要执行几次这个加法指令。 解:将11个数作为树叶,每个分支点对其儿子执行加法指令所得之数,则执行过程可用一 l1-1 棵3叉正则树来表示。因有11个叶子,且叉数r=3,由推论86.1,分支点有m= 个,故至少需执行这个加法指令5次 2-叉树可用于描述淘汰赛。在淘汰赛中,一旦一支球队输了一场比赛,就被淘汰出局。 有n个选手参加的淘汰赛可用一棵有n片叶子的2叉树来表示。树叶表示选手,树高表示最 长赛程。一个选手所在的层数表示他要取得冠军需要赢的比赛次数。如果各选手平等比赛 则相应的淘汰赛模型是一棵完全正则2叉树。如果某些选手需要经过附加赛才能进入正式赛 或上届种子选手可以少参加前若干场比赛,则相应的淘汰赛模型是一棵不完全正则2-叉树。 在淘汰赛中,最后获胜的球队未必是最好的球队,最好的球队可能在早些某场比赛中被 淘汰了。 三、2叉树与二元前缀码 定义866设ax2a2…an是长为n的符号串,其子串a1,a1a2,…,a1a2…an-分别称为该 符号串的长度为1,2,…n-1的前缀。设A={B1,B2…,Bn}为一个符号串集合。若对 vB,B,∈A,(i≠j),B与月都互不为前缀,则称A为前缀码。若A中每个符号串中 都只出现0,1两个符号,则称A为二元前缀码。 例如,{1,000110101,01001,01000}是二元前缀码,而{1,00,011,0101,0100,01001}不 是前缀码。 利用2叉树可产生二元前缀码。 定理86.4由一棵给定的2叉正则树可以产生一个二元前缀码。 证设T是具有t片树叶的2叉树。T的任何分支点v必有1个或2个儿子。若v有两个儿 子,在由v引出的两条边上,左边的标上0,右边的标上1。若v只有一个儿子,由它引出 的边可以标0也可以标1。设u是T的任一片树叶,从树根到u的通路上各边的标号按通 路上边的顺序组成的符号串放在u处,因u处的符号串的前缀均在u所在的通路上取得 故t片树叶对应的t个符号串组成的集合构成一个二元前缀码 例如,由下列2叉树所产生的一个二元前缀码为{01,11,000,0010,0011}。 0010 bou 如果将其中只有一个儿子的点发出的边标上0,则得另一个二元前缀码:12 11 个数之和，问至少需要执行几次这个加法指令。 解：将 11 个数作为树叶，每个分支点对其儿子执行加法指令所得之数，则执行过程可用一 棵 3 叉正则树来表示。因有 11 个叶子，且叉数 t=3，由推论 8.6.1，分支点有 11 1 5 3 1 m − = = − 个，故至少需执行这个加法指令 5 次。 2-叉树可用于描述淘汰赛。在淘汰赛中，一旦一支球队输了一场比赛，就被淘汰出局。 有 n 个选手参加的淘汰赛可用一棵有 n 片叶子的 2 叉树来表示。树叶表示选手，树高表示最 长赛程。一个选手所在的层数表示他要取得冠军需要赢的比赛次数。如果各选手平等比赛， 则相应的淘汰赛模型是一棵完全正则 2 叉树。如果某些选手需要经过附加赛才能进入正式赛 或上届种子选手可以少参加前若干场比赛，则相应的淘汰赛模型是一棵不完全正则 2-叉树。 在淘汰赛中，最后获胜的球队未必是最好的球队，最好的球队可能在早些某场比赛中被 淘汰了。 三、2 叉树与二元前缀码 定义 8.6.6 设α1 α 2 "α n 是长为 n 的符号串，其子串 1 1 2 1 2 1 , , , α α α " α α "α n− 分别称为该 符号串的长度为1,2,", n −1的前缀。设 A＝{ β β β m , , , 1 2 " }为一个符号串集合。若对 ∀β i , β j ∈ A，（i ≠ j ）， βi 与 β j 都互不为前缀，则称 A 为前缀码。若 A 中每个符号串中 都只出现 0, 1 两个符号，则称 A 为二元前缀码。 例如，{1, 00,011,0101,01001,01000}是二元前缀码，而{1, 00, 011, 0101, 0100, 01001}不 是前缀码。 利用 2 叉树可产生二元前缀码。 定理 8.6.4 由一棵给定的 2 叉正则树可以产生一个二元前缀码。 证 设 T 是具有 t 片树叶的 2 叉树。T 的任何分支点 v 必有 1 个或 2 个儿子。若 v 有两个儿 子，在由 v 引出的两条边上，左边的标上 0，右边的标上 1。若 v 只有一个儿子，由它引出 的边可以标 0 也可以标 1。设 u 是 T 的任一片树叶，从树根到 u 的通路上各边的标号按通 路上边的顺序组成的符号串放在 u 处，因 u 处的符号串的前缀均在 u 所在的通路上取得， 故 t 片树叶对应的 t 个符号串组成的集合构成一个二元前缀码。 例如，由下列 2 叉树所产生的一个二元前缀码为{01, 11, 000, 0010, 0011}。 如果将其中只有一个儿子的点发出的边标上 0，则得另一个二元前缀码： 0 0 1 1 0 1 1 0 1 01 11 000 0010 0011