离散数学第十一章树

第十一章树离散数学陈志奎主编人民邮电出版社前言1847年，德国学者柯希霍夫（Kirchhof）在研究物理问题时提出了树的概念。他用一类线性方程组来描述一个电路网络的每一条支路中和环绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点和线组成的相应的组合结构来代替原来的电路网络，而并不指明每条线所代表的电器元件的种类。事实上，他把每个电路网络用一个基本图来代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为图论中的标准方法。前言1857年，英国数学家凯莱（CaylayArthur）从事计数由给定的碳原子数n的饱和碳氢化合物的同分异构物时，独立地提出了树的概念。凯莱把这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现了树，他并不知道树与现代的化学学说有关。1889年凯莱给出了完全图Kn的概念。前言1956年Kruskal设计了求最优树的有效算法。树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领域也都有广泛的应用。本章将对树进行详细的讨论，主要包括树的基本性质和生成树，以及有向树中的m叉树、有序树和搜索树等。PART01PART02树与生成树有向树及其应用主要内容11.1树与生成树定义11.1连通且不含回路的图称为树。树中度为1的结点称为叶，度大于1的结点称为枝点或内点。根据这个定义，平凡图K1也是树。K1是一个既无叶又无内点的平凡树。定义11.2在定义11.1中去掉连通的条件，所定义的图称为森林。森林的每个支都是树。6树及其性质11.1树与生成树例11.1图11.1所示是森林，他的每个分支（a）、（b）都是一棵树。图11.17树及其性质11.1树与生成树定理11.1设T是无向（n，m）图，则下述命题相互等价。（1）T连通且无回路。（2）T无回路且m=n-1。（3）T连通且m=n-1。（4）T无回路但新增加任何一条边（端点属于T）后有且仅有一个回路。（5）T连通，但是删去任何一边后便不再连通。（6）T的每一对结点之间有且仅有一条道路可通。8树及其性质11.1树与生成树推论11.1任何非平凡树至少有二片叶。证明：设（n,m）树T有t片叶，则，由定理11.1中命题（2），可得，即例11.2设是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求的树叶数。解：设树有片树叶，则的节点数的边数又由得所以，即树有9片树叶。9树及其性质11.1树与生成树推论11.2阶大于2的树必有割点。证明：由知道T至少有一个度数大于1的内点v，再由定理11.1中命题（5），T-v不是连通的，故v必是割点。10树及其性质11.1树与生成树定义11.3若无向（连通图）G的生成子图是一棵树，则称该树是G的生成树或支撑树，记为。生成树中的边称为树枝。图G中其他边称为

的弦。所有这些弦的集合称为的补。例11.3图11.2中（b）、（c）所示的树、是图（a）的生成树，而（d）所示的树不是图（a）的生成树。图11.211生成树与最小生成树11.1树与生成树例11.4某地要兴建５个工厂，拟修筑道路连接这５处。经勘测其道路可依如图11.2（a）的无向边铺设。为使这５处都有道路相通，问至少要铺几条路？解：这实际上是求G的生成树的边数问题。一般情况下，设连通图G有n个节点，m条边。由树的性质知，T有n个节点，n-1条树枝，m-n+1条弦。在图11.2（a）中，n=5，则n-1=4，所以至少要修４条路才行。

由图11.2可见，要在一个连通图中找到一棵生成树，只要不断地从的回路上删去一条边，最后所得无回路的子图就是的一棵生成树。于是有以下定理。12生成树与最小生成树11.1树与生成树定理11.2无向图为连通当且仅当有生成树。证明：先采用反证法来证明必要性。若G不连通，则它的任何生成子图也不连通，因此不可能有生成树，与G有生成树矛盾，故G是连通图。再证充分性。设G连通，则G必有连通的生成子图，令T是G的含有边数最少的生成子图，于是T中必无回路（否则删去回路上的一条边不影响连通性，与T含边数最少矛盾），故T是一棵树，即生成树。13生成树与最小生成树11.1树与生成树定义11.4设<G，W>是加权无向图，

，中所有边的加权长度之和称为的加权长度。G的所有生成树中加权长度最小者称为<G，W>的最小生成树。最小生成树有很广泛的应用。例如要建造一个连接若干城市的通讯网络，已知城市和之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树。14生成树与最小生成树11.1树与生成树例11.5图11.3显示了利用Kruskal算法生成最小生成树的过程。通俗地讲，该算法就是想将图中的边按权重从小到大排列，再从小到大一次取出每条边做检查。一开始取最小的边，由该边导出一部分子图，然后依次每取一边加入得到的部分子图。若仍为无回路，将该边与原有部分子图的边导出一个新子图；若得到回路，将该边放弃。上述过程继续进行直到所有的边都检查完毕，这样得到的生成子图就是最小生成树。图11.315生成树与最小生成树11曲.1树与拳生成企树Kr释us蜡ka傻l算法（1）选少取G中权星最小拼的一聋条边鞋，设孩为塌。令（2）若农，剪输出G（S），糠算法逮结束去。（3）设非已选炕边构画成集凉合膏。从E-疼S中选名边饥，杆使其疮满足链条件厅：①罢不闹含圈香；②泽在E-尊S的所资有满剧足条善件①旬的边吨中，捕有聋最小竟的权回。（4）美转（2）。16生成耗树与跟最小肌生成厅树PART01PART02树与窄生成扩树有向纠树及渠其应胃用主要内容11遗.2有向胖树及制其应悲用定义11苗.5一个捎结点饭的入芦度为0，其肾余结必点的贩入度缘瑞均为1的弱挥连通结有向迁图，费称为有向菊树。在榆有向宋树中笔，入土度为0的结示点称薪为根建，出拜度为0的结熊点称朱为叶阳，出喇度大宜于0的结帜点称膜为分要支结每点，催从根辫至任寄意结秃点的幻玉距离磨称为哲该结糊点的买层或筒级，劣所有纺结点圆的级余的最怒大值统称为孟有向吊树的蚕高度域。例11拆.6图11树.4画出岩了一皱棵有印向树卡，届是根破，倒是叶蚊，壶是递分支摔结点穿，定背点悬的层逃数是1，树毕的高月度是3。图11垄.418有向支树11多.2有向租树及不其应眼用定理11品.3设雨是有连向图D的结省点。D是以震为回根的苗有向掀树，霜当且持仅当帐从伞至D的任鬼意结油点恰怖有一果条路塘径。19有向灯树11落.2有向熊树及柱其应井用定义11厦.6每个执弱分禽支都经是有票向树纵的有核向图键，称标为有向醉森林。定义11亩.7在有肿向树浇中，林若从厕到错可达伸，则兆称聋是匀的祖先，究是沫的后代；又四若<耳,剥>是根围树中铸的有纠向边选，则泡称拳是仆的父亲，趴是全的儿子；如吗果两政个节川点是灿同一点节点溪的儿佣子，扔则称昆这两袋个节辽点是兄弟。20有向卵树11写.2有向隆树及沈其应症用定义11串.8在有唱向树T中，榴若任瞎何结柏点的胃出度脑最多殃为m，则饺称T为m叉树笔；如型果每特个分律支结剂点的捡出度船都等体于m，则维称T为完份全m叉树景；进纤一步钱，若T的全贷部叶辅点位润于同睁一层售次，支则称T为正织则m叉树仍。例11解.7在图11船.5盯(a厉)是一弓棵二口叉树剥，而揭且是侄正则稠二叉舌树；饲图11们.5胀(b竞)是一隙棵完谨全二弊叉树大；图11熟.5乌(c懂)是一候棵三历叉树缘瑞，而胀且是龙正则筑三叉祖树；珠图11美.5裤(d橡)是一启棵完躁全三念叉树御。21m叉树图11银.511洽.2有向滥树及袍其应拖用定理11摆.4若T是完凭全m叉树围，其会叶数怠为t，分摩枝点抵数为i，则证明撇：在讽分枝瘦点中灾，除性根的仔度数楚为m外，煤其余是各分安枝结让点的蔬度皆捧为m+谁1。各妇叶点蹦的度盏为1，总借边数拐为mi，由野图论领基本说定理厚得到即这个摩定理扛实质缠上可鸡以用验每局祥有m个选统手参制加的祸单淘闭汰制担比赛眉来说粉明。t个叶惠表示t个参孩赛的顺选手叔，i则表译示必帜须按纯排的盾总的搅比赛沸局数店。每欣一局碧由m个参遗赛者族中产地生一版个优主胜者元，最冲后决拜出一每个冠六军。22m叉树11始.2有向首树及评其应贪用例11便.8设有28盏电辅灯，网拟公强用一很个电摸源插汇座，来问需程要多色少块织具有混四插磨座的莫接线隐板？这个泊公用弯插座件可以彻看成泳是正皱则四效叉树晃的根感，每漂个接阀线板解看成哥是其象它的络分枝肥点，鹊灯泡演看成疼是叶睬，则躁问题怎就是姓求总冲的分不枝点拢的数险目，曲由定湿理11钳.4可以棋算得列。棉因此巴，至判少需昌要9块接罚线板双才能俘达到句目的盟。23m叉树11拘.2有向狮树及俗其应燃用定义11脾.9设V是二壮叉树D的叶卧子的毫集合伯，R+是全阻体正猛实数甚的集墨合，W:丢V→院R+，则便称<R博,W省>为加权昌二叉筋树。对谈于D的任攀意叶v，称W(义v)为v的权，称则（剩其中,V是叶险子的哥集合糊）为<D威,W召>的叶岸加权纹路径墙长度叶，其严中W(胳v)是叶循子v的权，L(舟v)为v的级。我们虚用叶固子表蓝示字笛母或柳符号惕，用记分支亚结点杏表示绿判断爸，用歌权表唯示字抱母或赌符号引出现穗的机腿率，稍则叶批加权拖路径孟长度扑就表富示算孩法的鼠平均锤执行住时间梨。2411煌.2有向斜树及物其应薪用例11捐.9图11肝.6（a）和泳（b）表洞示了厉识别A,艰B,害C,莲D的两爱个算妇法，A,当B,肾C,两D出现柳的概石率分粮别是0.遣5，0.毕3，0.怒05，0.呢15。图11鲁.6（b）表左示的饶算法刮优于11赏.6（a）表择示的柄算法猜。25图11禽.611龟.2有向根树及株其应讲用定义11给.1赖0设<D回,W陡>是叶秆加权粮二叉博树。句如果逮对于巨一切溜叶加原权二滥叉树只要洲对于园任意任正实厦数r，D和误中事权等切于r的叶朝的数纲目相劳同，印就有<D慰,W津>的叶租加权亚路径计长度过不大碍于钞的鸦叶加市权路瓜径长邪度，给则称<D千,W茄>为最优诉的。这样树，我趁们把福求某嫌问题竭的最这佳算锹法就呀归结销为求洗最优扑二叉缎树的梢问题仓。2611叔.2有向男树及嗓其应扯用假定吵我们赤要找飞有m片叶董，并苍且它轮们的饱权分筑别为索的最刺优二裳叉树泊。不绢妨设姐是端按递社增顺颗序排斥列的忽。即句。设<D岔,W箱>是满捕足要津求的仙最优袍二叉蚀树，D中以为权驶的叶业分别辛为冬。显攀然，帖在所糟有的赠叶中安，虑和狭的级猴最大袭。不业妨设抓和亚与同假一个若分支繁结点压邻袭接，荣令，并笼且瓣，容易疲证明彩，<D傍,W拿>是最辈优的火，当联且仅尝当雕是森最优溪的。旬这样讲把求m片叶酱的最堆优二租叉树馒归结圾为求m-仆1片叶雄的最师优二鸡叉树叛。继顽续这裹个过剃程，皮直到原归结喂为求驻两片朝叶的床最优盆二叉乎树，盘问题绍就解斤决了蒸。2711绿.2有向颤树及挣其应婶用例11谦.1情0求叶哀的权室分别特为0.坡1、0.刑3、0.奴4、0.章5、0.烫5、0.逼6、0.优9的最正优二钱叉树盛。计算帖过程触如下桃：所得约出的督最优赞二叉朋树如撕图11肿.7所示赶，叶某中的任数表座示权伍，所暖有分绩支结嫌点中扔的数钟之和文就是歪叶加铸权路锹径长台度。28图11糊.711叨.2有向袜树及安其应庸用定义11左.1赔1如果坚在有须向树矮中规够定了触每一竹层次孩上节街点的拼次序穗，这嚷样的碌有向吉树称坑为有序蚁树。在醉有序湾树中况规定宴同一时层次兴节点横的次桃序是唤从左僚至右罩。29有序恭树11握.2有向污树及观其应遇用例11厘.1盼1我们策可以不用有惭向有盯序树释表达蓄算术婶表达津式，员其中进叶表蛾示参带加运汪算的棋数或木变量揭，分党支节夫点表瓜示运免算符陈。如男代数哥式达可表桶示为剧图11称.8的有惩向有刑序树巴。为方医便起复见，木我们哲借用喝家族的树的若名称脸来称句呼有蔑向有驴序树孩的结记点。泥如在陷图11涨.9中，箱称书是唇和咳的熔父亲豆，施是项的长被子，横是纽奉的哥促哥，纱是焰的识弟弟歼，驱是医的裕伯父点，毁是披的堂烈兄。30有序弯树11棒.2有向攻树及驴其应荣用定义11赶.1挥2一个续有向所图，补如果遥它的坚每个上连通币分支缴是有抓向树祖，则故称该慎有向古图为(有向)森林泉；在批森林惑中，久如果政所有访树都术是有恒序树求且给充树指袋定了纲次序咐，则脾称此否森林境是有堪序森蛛林。匀例如粗，图11宋.1超1是一渴个有裹序森菌林。在图11各.1晓0中，券（a）和势（b）是用相同做的有更向有参序树败，因志为同棍一级垫上结魄点的牌次序危相同康。但篮是如房诚果考轮虑结甘点之卖间的汉相对妈位置琴，他续们就政不同缓了。甘在（a）中斤，泉位于逗的沾左下砖方；挨而在浸（b）中朵，重位未于骆的右惯下方牲，它故们是株不同似的位毯置有卸向有乡丰序树大。31有序池树图11粗.1矛0图11督.1箩111恋.2有向津树及糖其应驶用定义11坚.1村3为每弟个分甩支结本点的进儿子习规定详了位愈置的贷有向柿有序产树，喂称为位置掌有序阁树。在位迟置二悦元有枪向有寻序树伍中，康可用属字母镜表{0嚼,1怒}上的奶字符悲串唯谁一地芦表示钱每个枯结点懂。用晌空串钓表示炼根。扔设用何表委示某大分支桐结点酒，则腊用太表示个它的酒左儿文子，飞用眉表示额它的展右儿阿子。汉这样插，每币个结焰点都额有了饲唯一是的编名码表静示，醉并且帝不同凭结点萍的编革码表吓示不段同。铁如在袖图11昏.1外2的（a）中箩，尽的编脆码表践示分泡别为β,熊0,砌1,络00俯,1杯0,联11。位有置二国元有韵向有躬序树颈全体即叶的恒编码酿表示歇的集葱合称跑为它具的前亡缀编决码。贯如图11绝.1泼2的（a）的偷前缀葵编码斯是{0此0,柳10洗,1贝1}。不医同的雷位置舌二元殖有向熟有序猜树有丹不同邪的前尸缀编沾码。隐这种凯表示惠方法阶便于剪用计锅算机赶存贮栋位置射二元皇有向悠有序妨树。32有序蝇树11乏.2有向丘树及俘其应侨用在二体叉树辉编码春中，蜡显然吼每两呜个叶薪点的余码都负不可棍能一集个是鉴另一丘个前那缀，条因为选要成球为前哨缀则距必然勺有祖娇先和期后裔趴的关凑系，朝这与邀叶的接定义雀不合斤。例社如集营合{0永00，00馆1，01蕉0，1}是前静缀码粱；集{0餐00，10脾01，01，00友}则不呈是前世缀码层，因迁为00是00益0的前鉴缀。显然卖，采播用前末缀码镜可以粱唯一魔确定危接收软的符压号串散内容冒。例原如{0拴00，00聪1，01的0，1}为前汤缀码糖，当宅接收伶的符卧号串取为10甜01邻01干00霜01脾00耕1，则赛可译垃为1，00厘1，01副0，00竟1，00莲1。33有序党树11滥.2有向恰树及芬其应死用例11渡.1傅2图11妥.1域2是由所前缀戏码{0模00，00女1，01，10，11讨}构造膊二叉渴树的宽例子岩，（a）中蔑黑点嚼表示绒前缀寺码中适每个估序列僚对应箩的叶宽，（b）是骗最后泡得到江的编拉码二岁叉树销。图11能.1就234有序船树11爬.2有向取树及蒸其应哀用可以印在有穴向有娃序森轿林和桨位置多二元圈有向呢有序先树之爪间建阳立一治一对改应关屋系。侵在有彻向有蚂序森载林中冲，我亩们称吗位于巧左边乘的有夜向有喝序树毅的根冬为位仁于右驶边的泳有向普有序板树的亭根的值哥哥水。设腿与有昼向有枣序森倚林F对应丈的位口置二育元有备向有诵序树蔬为T。我抬们规槽定，低它们阁有相昌同的嫌结点标。在F中，恋若画是惕的长山子，丝式则在T中呀是敲的左良儿子叠。在F中，酱若愈是云的大车弟，色则在T中，万是凉的肌右儿纺子。谊这中桂对应吊关系驻称为闯有向压有序列森林耽和位况置二片元有扇向有岸序树竞之间赤的自弹然对涛应关叶系。盯例如灶，图11遗.1嫩3中（a）是资有向膊有序摇森林行，（b）是陡对应验的位廉置二灾元有絮向有净序树悉。图11晨.1冈335有序林树11鞋.2有向图树及贱其应述用显然还当森盛林中赛只有奇一棵随树时众，上昨面的刃转化忆方法撞就是攀把任挠意m元树津转化峡成二服元有苦向有份序树纹的方微法了鸦。从上猾面的希讨论唱我们岛可以灭作出俯以下疾的结逃论：而如果阀一个馆实际冠问题裹可以个抽象招成一企个图没，则谦可宵以将叠这个遍图转面化成教树（此求这糖个图渡的生厕成树仁），到对任利何一驾棵树劲都可迈以转映化成析与其父对应产的二访元树扶，对时二元团树我此们可板以方械便地腿在计抗算机扰中存器贮与糠访问衬。下掉面我皂们就哀来介事绍二么元树罗的存恶贮与载访问良方式否。利床用连晒接分伍配技遣术可甩以方降便地法表示柱二元陷树，弃其中繁所包甩含的席结点详结构绵为：这里乌，LL戏IN宪K或RL仙IN猴K分别商包含台一个背指向巷所论茫结点栗的左捡子树方或右献子树泰的指冲针（恳或称液指示葵数、俯指示批字）惑、DA痕TA包含厕与这父个结推点有字关的绍信息魄。36有序改树LLINKDATARLINK11仇.2有向铲树及煌其应轧用数据六结构积中，耗在使凝用树港作数鄙据结促构时嫩，经维常需卫要遍里访二棋元有屿序树透的每霸一个损节点证，就插是检戴查存彼储于艳树中魄的每鬼一数层据项阳。对样于一姐棵根治树的泛每一爽个节迟点都洪访问情一次击且仅贱访问拆一次鹊称为珠遍历刷或周福游一攻棵树暴。二叉岩树的坛遍历顾算法棋主要冲有下要列3种。（1）前践序遍沾历算酬法前序奔遍历筒算法鲁的访己问次王序为直：①酿访问蛇根；②萝在根复的左语子树席上执蛛行前伟序遍径历；③甜在根奔的右谨子树词上执湿行前绿序遍现历。37二叉妥树的胁遍历11对.2有向抢树及炉其应触用（2）中悔序遍坦历算哄法中序岁遍历蜜算法夜的访粥问次泼序为诸：①励在根假的左俊子树再上执踢行中握序遍住历算辉法；②共访问迈根；③南在根躲的右斯子树索上执缓行中息序遍滚历算梅法。（3）后轻序遍属历算齿法后序锅遍历册算法症的访他问次仆序为射：①播在根呀的左功子树于上执酿行后焦序遍系历算璃法；②挤在根蹲的右虾子树袄上执鸟行后士序遍给历算蔬法；③尿访问排根。38二叉跃树的孕遍历11抽.2有向家树及料其应磨用如果愿某一步子树倾是空塑的（缩慧即该激结点队没有例左或骆右的浅子孙晒时）围则所哄谓周胞游就贼什么尽也不乐执行表。换颤句话凯说，双当遇灰到空火子树舱时，筹则它玩被认阶为已体完全执周游踩了。如图11绪.1惠4所示松的树婆，其驻前序违周游秤、中织序周傍游和勾后序怠周游届将按火下列率次序蛙处理艺结点稀。AB检CD兄EF拔GH（前祝序）CB惯DA光EG毙HF（中谊序）CD体BH宗GF叉EA（后忽序）39二叉犹树的赛遍历图11感.1沟411斑.2有向纵树及诸其应组用既然杯周游阶时，评要求杜向下命而后秆又要脚往上械追溯昆树的复一部酒分，锐所以洽允许都往上煤追溯益树时脾的指拐针信呼息必我须暂羽时保摇存起顶来（龙如图11顶.1释4（b））稻。注项意到恳已表材示在辜树中弓的结惩构信攀息，拾使得战从树套根往誉下运押动是汤可能旋的，掀但往模上运父动必尼须采蓄取与珍往下津运动逮相反线的手挖法，盖因此挽在周幼游树烟时，抵要求教有一节个栈袭保留印指针值的值卧。现烟在我原们给梳出前蓄序周闸游的硬算法征。40二叉叨树的孩遍历11筑.2有向粗树及航其应迹用PR酱EO叉RD梨ER算法铜：给定监一棵估二元树树,它的辜根结叹点地宪址是相变量T，它厘的结牵点结鞠构和墓上面火描述穗的相饭同，甲本算载法按绘前序复周游妙这棵增二元展树。茫利用你一个跌辅助得栈S，S的顶境点元台素的重下标拴是TO浸P，P是一绣个临嗓时变奶量,它表肯示我翠们处绍在这瓶棵树锻中的芝位置遥。1．[置初轿态]如果T=夺NU伞LL，则御退出(树无难根,因此犹不是启真的崇二元妄树)；否狮则P←堵T；TO匙P←映0。2．[访问竟结点川，右眼分枝慰地址窜进栈挖，并扫转左]处理屡结点P。如悠果PR环LI葬NK耐(P贴)≠徒NU仪LL，则辛置TO迟P←瞎TO在P+国1；S[忙TO订P]嘴←R谨LI揭NK颂(P复)；P←谨LL惹IN臂K(施P)。3．[链结颠束否?]如果P≠晓NU秋LL，则活转向赢第2步。4．[右分互枝地底址退怀栈]如果TO禽P=舅0则退贵出；幸否则爱令P←猫S[寨TO许P]；TO挣P←来TO荡P-喘1，并和转向弓第2步。41PR帽EO容RD撇ER算法11争.2有向绒树及屡其应吧用其中岗，算估法的孕第2步和掌第3步是停访问挎和处昼理结赏点。丸如果捏该结序点的傲右分桌枝地秃址存钱在的神话，荐则让押它进钱栈，策并跟咸踪左帅分枝匠链直翁到这串个链情结束谋。然网后进蹲入第4步，恒并将汉最近不遇到藏的右痰子树熟根结砌点的敞地址贸从栈炒中删渣除，陶再按坏第2步与渐第3步处敲理它猜。对然于图11傅.1捐4的二猜元树情，追猛踪上首述算捎法后令地址捞记为垒“NE绣”。在岂这里予，所关谓访蚕问结排点就认是输昆出它关的标籍号。42PR柱EO密RD度ER算法栈的内容P访问P输出串NAAANENBBABNENDNCCABCNENDNULLNENDDABCDNENULLNEEABCDENFNULLNFFABCDEFNGGABCDEFGNHNULLNHHABCDEFGHNULL11兔.2有向场树及嘴其应丢用例11疤.1桂3设有n根火墓柴，旱甲乙赵两人思依次泛从中网取走1或2根，浩但不哗能不世取，裕谁取且走最汉后一火根谁挨就是叉胜利教者。体为了会说明贯方法渐，不挡妨设n=呢6。在辽图11罪.1李5中6表示炼轮到电甲取牙时有6根火俘柴，4表示遥轮到脾乙取索时有4根火浅柴，毙以此抬类推鞭。显然扛，一惰当出屋现1或2状态匆，甲斑取胜拴，不直必再柳搜索堪下去是。同胸样，1或2是乙耐取胜屑的状贯态。图11凑.1均5搜索毫树43搜索铸树11垒.2有向忌树及酸其应严用若甲拍取胜匪时，赏设其职得分讯为1，乙蔑取胜慢时甲构的得这分为-1。无恩疑，产轮到伸甲作误出判惑决时第，他滩一定友选（-1，1）中皆的最委大者舌；而倡轮到依乙作竖出判猛决时扒，他隆将选壮取使烛甲失番败，剑选+1、-1中最银小者晋。这狂个道且理是样显而炭易见惑的。闯比如久甲遇听到图11妈.1普6（a）的色状态钟时，亚甲应挪选ma谜x(炼1,肢-1浩)=涨1，即浮甲应织取1根火扑柴使溉状态辽进入师③。用同理袍，乙虚遇到鄙图11箱.1辩6（b）的腔状态辜时，瞒乙应津选取ma迟x(摊-1头,1摊)=那-1，使帐甲进杜入必夫然失帆败的炕状态城为好啊。如膀图11拌.1虎5所示锐，开沸始时灾若有6根火破柴，科先下庙手者鸡败局破已定削，除嚼非对底手失小误。44搜索设树图11辜.1熄611谱.2有向半树及补其应狮用下面万我们低将举垒例介孔绍搜邮索树鲁的DF摊S算法迎（深度忍优先劲搜索(D参ee幼p－Fi谁rs壶t－Se删ar汽ch卸)）。DF寺S算法咳的基抄本思卡想如巧下：（1）当E(滴G)的所捆有边劝未经李完全锣搜索枕时，姓任取手一结甩点局，给奥以润标志托且入躁栈（包以先情入后狱出为聋原则睡叫做落栈，窄先入悲先出确者叫酿做队个）。（2）对挣与平点关抛联的承边依景次进零行搜誓索时诊，当含存在返另一旧端点另未给遇标志场的边冲时，