离散数学课件(英文版)----Trees.ppt

《离散数学课件(英文版)----Trees.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TreesLecture8DiscreteMathematicalStructuresRootedTreeLetAbeaset,andletTbearelationonA.Tisarootedtreeifthereisavertexv0inAwiththepropertythatthereexistsauniquepathinTfromv0toeveryothervertexinA,butnopathfromv0tov0.v0PropertiesofRootedTreeLet(T,v0)bearootedtree.Then(a)TherearenocyclesinT.

2、(b)v0istheonlyrootofT.(c)Eachvertexotherthantheroothasin-degreeone,andtheroothasin-degree0v0vpcMorethanonepathfromv0tov.(a)v0v0’Acyclefromv0tov0(b)v0vkw1?Morepathtow1?(c)DrawingaRootedTreebyLevelsRootInnernodeBranchingnodeLeafLevel0Level1Level2Level3Height=3RootedTreeandFamilyRelationsI

3、tiseasytodescribethefamilyrelations，andontheotherhand,termsaboutfamilyrelationsareusedinrootedtrees.JohnJohn'schildJohn'sparentJohn'sancestorsJohn'sdescendantsJohn’ssiblingsSomeTermsaboutRootedTreeOrderedtree:theorderingisassumedonverticesineachlevel;n-tree:everyvertexhasatmostnoffsprin

4、g;Completen-tree:everyvertes,otherthanleaves,hasexactlynoffspringBinarytree:2-treeSubtreeofaRootedTreeIf(T,v0)isarootedtreeandvT.LetT(v)bethesetofvandallitsdescendants,thenT(v)andalledgeswiththeirtwoendsinT(v)isatree,withvasitsroot.(Itiscalledasubtreeof(T,v0))Proof:Thereisapathfromvtoa

5、nyothervertexinT(v)sincetheyareallthedescendantsofv;TherecannotbemorethanonepathfromvtoanyothervertexwinT(v),otherwise,in(T,v0),therearemorethanonepathfromv0tow,boththroughvTherecannotbeanycycleinT(v),sinceanycycleinT(v)isalsoin(T,v0)SubtreesofBinaryTreeInaorderedbinarytree,asubtreeisal

6、eftsubtreeorarightsubtree.Evenifavertexhasonlyoneoffspring,itssubtreecanbeidentifiedasleftorrightbyitslocationinthedigraph.LeftsubtreeRightsubtreeLabeledTree:anExampleUsingrootedtreetorepresentaarithmeticexpressions:branchingverticescorrespondingoperatorsleavescorrespondingoperandsjiagb

7、cdefh/++***+-Example:(a*(b+c)+d*(e*f))/(g+(h-i)*j)PositionalTrees222233333111LLLLLLLLRRRRRRRRPositionalBinaryTreeOrderedBinaryTreeAnyorderedtreecanbeconvertedintoaorderedbinarytree.123456789101112123456789101112ComputerRepresentationS+-32x--2+xx3(3-(2x))+((x-2)-(3+x))asadoubl