资源描述:
《基于多级标记编码理论的树形结构表示方法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cnAnImplementationMethodofTreeStructureBasedonMultilevelMarkingCodingTheoryWuShengyuanSchoolofComputerScienceandTechnologyShandongUniversityJinan,P.R.China250061Email:wsy@sdu.edu.cnAbstractBasedonmultilevelmarkingcodingtheory,thispaperpresentsanewtreeimple
2、mentationmethod,calledasmatrix-basedimplementationmethod,whichcanbeusedtoimplementbinarytree,generaltree,andanykindsoftrees.Comparingtotheexistentimplementationmethods,matrix-basedimplementationmethodissimpler,theoperationsoftreearesimplifiedandmoreefficient,andstoragespacecan
3、besavedKeywords:Treeimplementation;multilevelmarkingcodingtheory;matrix;multilevelmark.1IntroductionTreestructureisusuallyimplementedbypointers,calledaspointer-basedimplementation;sometreecanbeimplementedbyarray,suchascompletebinarytree.Sequentialtreeimplementationisanothertre
4、eimplementationmethod.Generaltreeimplementationcanbeasfollowing:parentpointerimplementation,implementationoflistofchildren,Left-Child/Right-Siblingimplementation;Dynamicnodeimplementation,andsoon.[1]Thispaperpresentsanewtreeimplementationmethod,calledasmatrix-basedimplementati
5、onmethod,whichcanbeusedtoimplementbinarytree,generaltree,andanykingsoftrees.Matrix-basedimplementationmethodismoreefficientandspacesavedcomparingtheimplementationmethodsused.Matrix-basedimplementationmethodisbasedonmultilevelmarktheory.[2-5]First,wediscussthederivationofthemet
6、hod;thendiscussmatrix-basedimplementationmethods;thelastpartisconclusion.2Derivationofmatrix-basedimplementationmethodTheideaofmatrix-basedimplementationmethodisgeneratedintheprocedureofmarkingasequencebymultilevelmark.Therefore,weshoulddiscusswhatmultilevelmarkis.[3]Theproced
7、uretodistinguishtheobjectsintoobjectgroupsinanobjectsequenceaccordingtosomeruleriscalledobjectgrouping.Binary0and1arecalledas0markand1markrespectively.Nextisoneofmultilevelmarkrules.Right1multilevelmarkrule:therightmostobjectinanobjectgroupmarkedwith1mark;theotherNobjectsinthe
8、objectgroupmarkedwith0mark;1Markiscalledasgrouprepresentative