数据结构各种算法实现(c 模板)

目录1、顺序表1SEQLISTH1TESTCPP62、单链表8LISTNODEH8SINGLELISTH10TESTCPP203、双向链表22NODELISTH22DOUBLELISTH24TESTCPP344、循环链表36LISTNODEH36CIRCULARLISTH37TESTCPP475、顺序栈49SEQSTACKH49TESTCPP546、链式栈55STACKNODEH55LINKSTACKH56TESTCPP607、顺序队列62SEQQUEUEH63TESTCPP688、链式队列70QUEUENODEH70LINKQUEUEH71TESTCPP759、优先级队列77QUEUENODEH77COMPAREH78PRIORITYQUEUEH80TESTCPP8510、串88MYSTRINGH88MYSTRINGCPP90TESTCPP10111、二叉树104BINTREENODEH104BINARYTREEH112TESTCPP12412、线索二叉树126THREADNODEH126THREADTREEH128THREADINORDERITERATORH128TESTCPP13913、堆140MINHEAPH140TESTCPP14714、哈夫曼树149BINTREENODEH149BINARYTREEH151MINHEAPH156HUFFMANH161TESTCPP16315、树164QUEUENODEH164LINKQUEUEH165TREENODEH169TREEH170TESTCPP18716、B树189BTREENODEH189BTREEH192TESTCPP21517、图217MINHEAPH217EDGEH222VERTEXH223GRAPHH224TESTCPP24618、排序249DATAH249QUEUENODEH255LINKQUEUEH259SORTH263TESTCPP2781、顺序表SEQLISTHCONSTINTDEFAULTSIZE100TEMPLATECLASSSEQLISTPUBLICSEQLISTINTSZDEFAULTSIZEM_NMAXSIZESZ,M_NCURRENTSIZE1IFSZ0M_ELEMENTSNEWTYPEM_NMAXSIZESEQLISTDELETEM_ELEMENTSINTLENGTHCONST/GETTHELENGTHRETURNM_NCURRENTSIZE1INTFINDTYPEXCONST/FINDTHEPOSITIONOFXINTISELEMENTTYPEXCONST/ISITINTHELISTINTINSERTTYPEX,INTI/INSERTDATAINTREMOVETYPEX/DELETEDATAINTISEMPTYRETURNM_NCURRENTSIZE1INTISFULLRETURNM_NCURRENTSIZEM_NMAXSIZE1TYPEGETINTI/GETTHEITHDATARETURNIM_NCURRENTSIZECOUTINTSEQLISTFINDTYPEXCONSTFORINTI0IINTSEQLISTISELEMENTTYPEXCONSTIFFINDX1RETURN0RETURN1TEMPLATEINTSEQLISTINSERTTYPEX,INTIIFIM_NCURRENTSIZE1|M_NCURRENTSIZEM_NMAXSIZE1COUTIJM_ELEMENTSJM_ELEMENTSJ1M_ELEMENTSIXRETURN1TEMPLATEINTSEQLISTREMOVETYPEXINTSIZEM_NCURRENTSIZEFORINTI0IVOIDSEQLISTPRINTFORINTI0IINCLUDE“SEQLISTH“USINGNAMESPACESTDINTMAINSEQLISTTEST15INTARRAY152,5,8,1,9,9,7,6,4,3,2,9,7,7,9FORINTI0ICLASSSINGLELISTTEMPLATECLASSLISTNODEPRIVATEFRIENDTYPENAMESINGLELISTLISTNODEM_PNEXTNULLLISTNODECONSTTYPEITEM,LISTNODENEXTNULLM_DATAITEM,M_PNEXTNEXTLISTNODEM_PNEXTNULLPUBLICTYPEGETDATAFRIENDOSTREAMPRIVATETYPEM_DATALISTNODEM_PNEXTTEMPLATETYPELISTNODEGETDATARETURNTHISM_DATATEMPLATEOSTREAMDELETEHEADPUBLICVOIDMAKEEMPTY/MAKETHELISTEMPTYINTLENGTH/GETTHELENGTHLISTNODEFINDTYPEVALUE,INTN/FINDTHDNTHDATAWHICHISEQUALTOVALUELISTNODEFINDINTN/FINDTHENTHDATABOOLINSERTTYPEITEM,INTN0/INSERTTHEDATAINTHENTHPOSITIONTYPEREMOVEINTN0/REMOVETHENTHDATABOOLREMOVEALLTYPEITEM/REMOVEALLTHEDATAWHICHISEQUALTOITEMTYPEGETINTN/GETTHENTHDATAVOIDPRINT/PRINTTHELISTPRIVATELISTNODEHEADTEMPLATEVOIDSINGLELISTMAKEEMPTYLISTNODEPDELWHILEHEADM_PNEXTNULLPDELHEADM_PNEXTHEADM_PNEXTPDELM_PNEXTDELETEPDELTEMPLATEINTSINGLELISTLENGTHLISTNODEPMOVEHEADM_PNEXTINTCOUNT0WHILEPMOVENULLPMOVEPMOVEM_PNEXTCOUNTRETURNCOUNTTEMPLATELISTNODESINGLELISTFINDINTNIFNPMOVEHEADM_PNEXTFORINTI0IM_PNEXTIFPMOVENULLCOUTLISTNODESINGLELISTFINDTYPEVALUE,INTNIFNPMOVEHEADINTCOUNT0WHILECOUNTNIFPMOVEM_DATAVALUECOUNTIFPMOVENULLCOUTBOOLSINGLELISTINSERTTYPEITEM,INTNIFNPMOVEHEADLISTNODEPNODENEWLISTNODEITEMIFPNODENULLCOUTM_PNEXTIFPMOVENULLCOUTM_PNEXTPMOVEM_PNEXTPMOVEM_PNEXTPNODERETURN1TEMPLATEBOOLSINGLELISTREMOVEALLTYPEITEMLISTNODEPMOVEHEADLISTNODEPDELHEADM_PNEXTWHILEPDELNULLIFPDELM_DATAITEMPMOVEM_PNEXTPDELM_PNEXTDELETEPDELPDELPMOVEM_PNEXTCONTINUEPMOVEPMOVEM_PNEXTPDELPDELM_PNEXTRETURN1TEMPLATETYPESINGLELISTREMOVEINTNIFNPMOVEHEAD,PDELFORINTI0IM_PNEXTIPMOVEPMOVEM_PNEXTIFPMOVEM_PNEXTNULLCOUTM_PNEXTPMOVEM_PNEXTPDELM_PNEXTTYPETEMPPDELM_DATADELETEPDELRETURNTEMPTEMPLATETYPESINGLELISTGETINTNIFNPMOVEHEADM_PNEXTFORINTI0IM_PNEXTIFNULLPMOVECOUTM_DATATEMPLATEVOIDSINGLELISTPRINTLISTNODEPMOVEHEADM_PNEXTCOUT“M_DATAPMOVEPMOVEM_PNEXTCOUTOVER“USINGNAMESPACESTDINCLUDE“SINGLELISTH“INTMAINSINGLELISTLISTFORINTI0ICLASSDOUBLYLISTTEMPLATECLASSLISTNODEPRIVATEFRIENDCLASSDOUBLYLISTLISTNODEM_PPRIORNULL,M_PNEXTNULLLISTNODECONSTTYPEITEM,LISTNODEPRIORNULL,LISTNODENEXTNULLM_DATAITEM,M_PPRIORPRIOR,M_PNEXTNEXTLISTNODEM_PPRIORNULLM_PNEXTNULLPUBLICTYPEGETDATAPRIVATETYPEM_DATALISTNODEM_PPRIORLISTNODEM_PNEXTTEMPLATETYPELISTNODEGETDATARETURNTHISM_DATADOUBLELISTHINCLUDE“LISTNODEH“TEMPLATECLASSDOUBLYLISTPUBLICDOUBLYLISTHEADNEWLISTNODE/THEHEADNODEPOINTTOITSELFHEADM_PPRIORHEADHEADM_PNEXTHEADDOUBLYLISTMAKEEMPTYDELETEHEADPUBLICVOIDMAKEEMPTY/MAKETHELISTEMPTYINTLENGTH/GETTHELENGTHOFTHELISTLISTNODEFINDINTN0/FINDTHENTHDATALISTNODEFINDDATATYPEITEM/FINDTHEDATAWHICHISEQUALTOITEMBOOLINSERTTYPEITEM,INTN0/INSERTITEMINTHENTHDATATYPEREMOVEINTN0/DELETETHENTHDATATYPEGETINTN0/GETTHENTHDATAVOIDPRINT/PRINTTHELISTPRIVATELISTNODEHEADTEMPLATEVOIDDOUBLYLISTMAKEEMPTYLISTNODEPMOVEHEADM_PNEXT,PDELWHILEPMOVEHEADPDELPMOVEPMOVEPDELM_PNEXTDELETEPDELHEADM_PNEXTHEADHEADM_PPRIORHEADTEMPLATEINTDOUBLYLISTLENGTHLISTNODEPPRIORHEADM_PPRIOR,PNEXTHEADM_PNEXTINTCOUNT0WHILE1IFPPRIORM_PNEXTPNEXTBREAKIFPPRIORPNEXTBREAKCOUNT2PPRIORPPRIORM_PPRIORPNEXTPNEXTM_PNEXTRETURNCOUNTTEMPLATELISTNODEDOUBLYLISTFINDINTN0IFNPMOVEHEADM_PNEXTFORINTI0IM_PNEXTIFPMOVEHEADCOUTBOOLDOUBLYLISTINSERTTYPEITEM,INTNIFNNEWNODENEWLISTNODEITEM,PMOVEHEADIFNEWNODENULLCOUTM_PNEXTIFPMOVEHEADCOUTM_PNEXTPMOVEM_PNEXTNEWNODEM_PPRIORPMOVEPMOVEM_PNEXTNEWNODENEWNODEM_PNEXTM_PPRIORNEWNODERETURN1TEMPLATETYPEDOUBLYLISTREMOVEINTN0IFNPMOVEHEAD,PDELFORINTI0IM_PNEXTIFPMOVEHEADCOUTM_PPRIORM_PNEXTPDELM_PNEXTPMOVEM_PNEXTM_PPRIORPDELM_PPRIORTYPETEMPPDELM_DATADELETEPDELRETURNTEMPTEMPLATETYPEDOUBLYLISTGETINTN0IFNPMOVEHEADFORINTI0IM_PNEXTIFPMOVEHEADCOUTM_DATATEMPLATEVOIDDOUBLYLISTPRINTLISTNODEPMOVEHEADM_PNEXTCOUT“M_DATAPMOVEPMOVEM_PNEXTCOUTOVER“LISTNODEDOUBLYLISTFINDDATATYPEITEMLISTNODEPPRIORHEADM_PPRIOR,PNEXTHEADM_PNEXTWHILEPPRIORM_PNEXTPNEXTIFPNEXTM_DATAITEMRETURNPNEXTPPRIORPPRIORM_PPRIORPNEXTPNEXTM_PNEXTCOUTINCLUDE“DOUBLYLISTH“USINGNAMESPACESTDINTMAINDOUBLYLISTLISTFORINTI0IGETDATACLASSCIRCULARLISTTEMPLATECLASSLISTNODEPRIVATEFRIENDCLASSCIRCULARLISTLISTNODEM_PNEXTNULLLISTNODECONSTTYPEITEM,LISTNODENEXTNULLM_DATAITEM,M_PNEXTNEXTLISTNODEM_PNEXTNULLPRIVATETYPEM_DATALISTNODEM_PNEXTCIRCULARLISTHINCLUDE“LISTNODEH“TEMPLATECLASSCIRCULARLISTPUBLICCIRCULARLISTHEADNEWLISTNODEHEADM_PNEXTHEADCIRCULARLISTMAKEEMPTYDELETEHEADPUBLICVOIDMAKEEMPTY/CLEARTHELISTINTLENGTH/GETTHELENGTHLISTNODEFINDTYPEVALUE,INTN/FINDTHENTHDATAWHICHISEQUALTOVALUELISTNODEFINDINTN/FINDTHENTHDATABOOLINSERTTYPEITEM,INTN0/INSERTTHEDATAINTOTHENTHDATAOFTHELISTTYPEREMOVEINTN0/DELETETHENTHDATABOOLREMOVEALLTYPEITEM/DELETEALLTHEDATASWHICHAREEQUALTOVALUETYPEGETINTN/GETTHENTHDATAVOIDPRINT/PRINTTHELISTPRIVATELISTNODEHEADTEMPLATEVOIDCIRCULARLISTMAKEEMPTYLISTNODEPDEL,PMOVEHEADWHILEPMOVEM_PNEXTHEADPDELPMOVEM_PNEXTPMOVEM_PNEXTPDELM_PNEXTDELETEPDELTEMPLATEINTCIRCULARLISTLENGTHLISTNODEPMOVEHEADINTCOUNT0WHILEPMOVEM_PNEXTHEADPMOVEPMOVEM_PNEXTCOUNTRETURNCOUNTTEMPLATELISTNODECIRCULARLISTFINDINTNIFNPMOVEHEADM_PNEXTFORINTI0IM_PNEXTIFPMOVEHEADCOUTLISTNODECIRCULARLISTFINDTYPEVALUE,INTNIFNPMOVEHEADINTCOUNT0WHILECOUNTNPMOVEPMOVEM_PNEXTIFPMOVEM_DATAVALUECOUNTIFPMOVEHEADCOUTBOOLCIRCULARLISTINSERTTYPEITEM,INTNIFNPMOVEHEADLISTNODEPNODENEWLISTNODEITEMIFPNODENULLCOUTM_PNEXTIFPMOVEHEADCOUTM_PNEXTPMOVEM_PNEXTPMOVEM_PNEXTPNODERETURN1TEMPLATEBOOLCIRCULARLISTREMOVEALLTYPEITEMLISTNODEPMOVEHEADLISTNODEPDELHEADM_PNEXTWHILEPDELHEADIFPDELM_DATAITEMPMOVEM_PNEXTPDELM_PNEXTDELETEPDELPDELPMOVEM_PNEXTCONTINUEPMOVEPMOVEM_PNEXTPDELPDELM_PNEXTRETURN1TEMPLATETYPECIRCULARLISTREMOVEINTNIFNPMOVEHEAD,PDELFORINTI0IM_PNEXTHEADIPMOVEPMOVEM_PNEXTIFPMOVEM_PNEXTHEADCOUTM_PNEXTPMOVEM_PNEXTPDELM_PNEXTTYPETEMPPDELM_DATADELETEPDELRETURNTEMPTEMPLATETYPECIRCULARLISTGETINTNIFNPMOVEHEADM_PNEXTFORINTI0IM_PNEXTIFPMOVEHEADCOUTM_DATATEMPLATEVOIDCIRCULARLISTPRINTLISTNODEPMOVEHEADM_PNEXTCOUT“M_DATAPMOVEPMOVEM_PNEXTCOUTOVER“INCLUDE“CIRCULARLISTH“USINGNAMESPACESTDINTMAINCIRCULARLISTLISTFORINTI0ICLASSSEQSTACKPUBLICSEQSTACKINTSZM_NTOP1,M_NMAXSIZESZM_PELEMENTSNEWTYPESZIFM_PELEMENTSNULLCOUTVOIDSEQSTACKPUSHCONSTTYPEITEMIFISFULLCOUTTYPESEQSTACKPOPIFISEMPTYCOUTTYPESEQSTACKGETTOPCONSTIFISEMPTYCOUTVOIDSEQSTACKPRINTCOUT“TOP“USINGNAMESPACESTDINCLUDE“SEQSTACKH“INTMAINSEQSTACKSTACK10INTINIT101,2,6,9,0,3,8,7,5,4FORINTI0ICLASSLINKSTACKTEMPLATECLASSSTACKNODEPRIVATEFRIENDCLASSLINKSTACKSTACKNODETYPEDT,STACKNODENEXTNULLM_DATADT,M_PNEXTNEXTPRIVATETYPEM_DATASTACKNODEM_PNEXTLINKSTACKHINCLUDE“STACKNODEH“TEMPLATECLASSLINKSTACKPUBLICLINKSTACKM_PTOPNULLLINKSTACKMAKEEMPTYPUBLICVOIDMAKEEMPTY/MAKETHESTACKEMPTYVOIDPUSHCONSTTYPEITEM/PUSHTHEDATATYPEPOP/POPTHEDATATYPEGETTOPCONST/GETTHEDATAVOIDPRINT/PRINTTHESTACKBOOLISEMPTYCONSTRETURNM_PTOPNULLPRIVATESTACKNODEM_PTOPTEMPLATEVOIDLINKSTACKMAKEEMPTYSTACKNODEPMOVEWHILEM_PTOPNULLPMOVEM_PTOPM_PTOPM_PTOPM_PNEXTDELETEPMOVETEMPLATEVOIDLINKSTACKPUSHCONSTTYPEITEMM_PTOPNEWSTACKNODEITEM,M_PTOPTEMPLATETYPELINKSTACKGETTOPCONSTIFISEMPTYCOUTM_DATATEMPLATETYPELINKSTACKPOPIFISEMPTYCOUTPDELM_PTOPM_PTOPM_PTOPM_PNEXTTYPETEMPPDELM_DATADELETEPDELRETURNTEMPTEMPLATEVOIDLINKSTACKPRINTSTACKNODEPMOVEM_PTOPCOUT“M_DATAPMOVEPMOVEM_PNEXTCOUTTOP“USINGNAMESPACESTDINCLUDE“LINKSTACKH“INTMAINLINKSTACKSTACKINTINIT101,3,5,7,4,2,8,0,6,9FORINTI0ICLASSSEQQUEUEPUBLICSEQQUEUEINTSZM_NREAR0,M_NFRONT0,M_NCOUNT0,M_NMAXSIZESZM_PELEMENTSNEWTYPESZIFM_PELEMENTSNULLCOUTVOIDSEQQUEUEMAKEEMPTYTHISM_NCOUNT0THISM_NFRONT0THISM_NREAR0TEMPLATEBOOLSEQQUEUEISEMPTYRETURNM_NCOUNT0TEMPLATEBOOLSEQQUEUEISFULLRETURNM_NCOUNTM_NMAXSIZETEMPLATEBOOLSEQQUEUEAPPENDCONSTTYPEITEMIFISFULLCOUTTYPESEQQUEUEDELETEIFISEMPTYCOUTTYPESEQQUEUEGETIFISEMPTYCOUTVOIDSEQQUEUEPRINTCOUT“REAR“USINGNAMESPACESTDINCLUDE“SEQQUEUEH“INTMAINSEQQUEUEQUEUE10INTINIT101,6,9,0,2,5,8,3,7,4FORINTI0ICLASSLINKQUEUETEMPLATECLASSQUEUENODEPRIVATEFRIENDCLASSLINKQUEUEQUEUENODECONSTTYPEITEM,QUEUENODENEXTNULLM_DATAITEM,M_PNEXTNEXTPRIVATETYPEM_DATAQUEUENODEM_PNEXTLINKQUEUEHINCLUDE“QUEUENODEH“TEMPLATECLASSLINKQUEUEPUBLICLINKQUEUEM_PREARNULL,M_PFRONTNULLLINKQUEUEMAKEEMPTYVOIDAPPENDCONSTTYPEITEM/INSERTDATATYPEDELETE/DELETEDATATYPEGETFRONT/GETDATAVOIDMAKEEMPTY/MAKETHEQUEUEEMPTYVOIDPRINT/PRINTTHEQUEUEBOOLISEMPTYCONSTRETURNM_PFRONTNULLPRIVATEQUEUENODEM_PREAR,M_PFRONTTEMPLATEVOIDLINKQUEUEMAKEEMPTYQUEUENODEPDELWHILEM_PFRONTPDELM_PFRONTM_PFRONTM_PFRONTM_PNEXTDELETEPDELTEMPLATEVOIDLINKQUEUEAPPENDCONSTTYPEITEMIFM_PFRONTNULLM_PFRONTM_PREARNEWQUEUENODEITEMELSEM_PREARM_PREARM_PNEXTNEWQUEUENODEITEMTEMPLATETYPELINKQUEUEDELETEIFISEMPTYCOUTPDELM_PFRONTTYPETEMPM_PFRONTM_DATAM_PFRONTM_PFRONTM_PNEXTDELETEPDELRETURNTEMPTEMPLATETYPELINKQUEUEGETFRONTIFISEMPTYCOUTM_DATATEMPLATEVOIDLINKQUEUEPRINTQUEUENODEPMOVEM_PFRONTCOUT“M_DATAPMOVEPMOVEM_PNEXTCOUTREAR“USINGNAMESPACESTDINCLUDE“LINKQUEUEH“INTMAINLINKQUEUEQUEUEINTINIT101,3,6,8,9,2,0,5,4,7FORINTI0ICLASSPRIORITYQUEUETEMPLATECLASSQUEUENODEPRIVATEFRIENDCLASSPRIORITYQUEUEQUEUENODECONSTTYPEITEM,QUEUENODENEXTNULLM_DATAITEM,M_PNEXTNEXTPRIVATETYPEM_DATAQUEUENODEM_PNEXTCOMPAREHTEMPLATECLASSCOMPARE/处理一般比较大小PUBLICSTATICBOOLLTTYPEITEM1,TYPEITEM2TEMPLATEBOOLCOMPARELTTYPEITEM1,TYPEITEM2RETURNITEM1CLASSPRIORITYQUEUE/CMPISDESIGNEDFORCOMPAREPUBLICPRIORITYQUEUEM_PREARNULL,M_PFRONTNULLPRIORITYQUEUEMAKEEMPTYVOIDMAKEEMPTY/MAKETHEQUEUEEMPTYVOIDAPPENDCONSTTYPEITEM/INSERTDATATYPEDELETE/DELETEDATATYPEGETFRONT/GETDATAVOIDPRINT/PRINTTHEQUEUEBOOLISEMPTYCONSTRETURNM_PFRONTNULLPRIVATEQUEUENODEM_PREAR,M_PFRONTTEMPLATEVOIDPRIORITYQUEUEMAKEEMPTYQUEUENODEPDELWHILEM_PFRONTPDELM_PFRONTM_PFRONTM_PFRONTM_PNEXTDELETEPDELTEMPLATEVOIDPRIORITYQUEUEAPPENDCONSTTYPEITEMIFM_PFRONTNULLM_PFRONTM_PREARNEWQUEUENODEITEMELSEM_PREARM_PREARM_PNEXTNEWQUEUENODEITEMTEMPLATETYPEPRIORITYQUEUEDELETEIFISEMPTYCOUTPDELM_PFRONT,PMOVEM_PFRONTWHILEPMOVEM_PNEXT/GETTHEMINIMIZEPRIORITYSDATA/CMPLTISUSEDFORCOMPARETHETWODATA,IFTHEFRONTONE/ISLESSTHANTHEBACK,THENRETURN1IFCMPLTPMOVEM_PNEXTM_DATA,PDELM_PNEXTM_DATAPDELPMOVEPMOVEPMOVEM_PNEXTPMOVEPDELPDELPDELM_PNEXTPMOVEM_PNEXTPDELM_PNEXTTYPETEMPPDELM_DATADELETEPDELRETURNTEMPTEMPLATETYPEPRIORITYQUEUEGETFRONTIFISEMPTYCOUTPDELM_PFRONT,PMOVEM_PFRONTM_PNEXTWHILEPMOVE/GETTHEMINIMIZEPRIORITYSDATAIFCMPLTPMOVEM_DATA,PDELM_DATAPDELPMOVEPMOVEPMOVEM_PNEXTRETURNPDELM_DATATEMPLATEVOIDPRIORITYQUEUEPRINTQUEUENODEPMOVEM_PFRONTCOUT“M_DATAPMOVEPMOVEM_PNEXTCOUTREAR“INCLUDEUSINGNAMESPACESTDINCLUDE“PRIORITYQUEUEH“INTMAINPRIORITYQUEUEQUEUEINTINIT101,9,3,5,0,8,2,4,6,7FORINTI0ISPE_QUEUEINTINIT25234,2,64,1,18,3,24,2,55,4SPECIALDATADATA5FORINTI0ICONSTCMYSTRINGCMP_STRCONSTBOOLOPERATORCONSTRETURNM_NCURLEN0CMYSTRINGCMYSTRINGCHARFRIENDOSTREAMPRIVATEVOIDNEXTPRIVATEINTM_NCURLENCHARM_PSTRINTM_PNEXTMYSTRINGCPPINCLUDEINCLUDEUSINGNAMESPACESTDINCLUDE“MYSTRINGH“CMYSTRINGCMYSTRING/CREATEEMPTYSTRINGM_PSTRNEWCHARMAXSIZE1IFM_PSTRCERRM_NCURLEN0M_PSTR00CMYSTRINGCMYSTRINGCONSTCHARINIT/INITIALIZETHESTRINGWITHCHARM_PSTRNEWCHARMAXSIZE1IFM_PSTRCERRM_NCURLENSTRLENINITSTRCPYM_PSTR,INITCMYSTRINGCMYSTRINGCONSTCMYSTRINGIFM_PSTRCERRM_NCURLENCOPYM_NCURLENSTRCPYM_PSTR,COPYM_PSTRINTCMYSTRINGFINDCMYSTRINGPARTCONST/STRINGMATCHKMPINTPOSP0,POST0INTLENGTHPPARTM_NCURLEN,LENGTHTTHISM_NCURLENPARTNEXTWHILEPOSPM_PSTRPOSTPOSPPOSTELSEIFPOSP0POSTELSEPOSPPARTM_PNEXTPOSP1DELETEPARTM_PNEXTIFPOSPM_NCURLENTHISM_PNEXTNEWINTLENGTHTHISM_PNEXT00FORINTI1IM_PNEXTI1WHILETHISM_PSTRITHISM_PSTRJIFTHISM_PSTRITHISM_PSTRJTHISM_PNEXTIJ1ELSETHISM_PNEXTI0/FORINTI0IM_PSTRCMYSTRINGIFPOSMAXSIZE|LENM_NCURLEN0TEMPM_PSTR00ELSEIFPOSLEN1M_NCURLENLENM_NCURLENPOSTEMPM_NCURLENLENFORINTI0,JPOSIM_PSTRIM_PSTRJTEMPM_PSTRLEN0RETURNTEMPBOOLCMYSTRINGOPERATORCONSTCMYSTRINGCMP_STRCONSTIFTHISM_NCURLENCMP_STRM_NCURLENRETURN0FORINTI0IM_NCURLENIIFTHISM_PSTRICMP_STRM_PSTRIRETURN0RETURN1BOOLCMYSTRINGOPERATORCONSTCMYSTRINGCMP_STRCONSTIFTHISCMP_STRRETURN0RETURN1BOOLCMYSTRINGOPERATORM_NCURLENCMP_STRM_NCURLENRETURNTHISM_NCURLENM_NCURLENIIFTHISM_PSTRICMP_STRM_PSTRIRETURNTHISM_PNEXTICONSTCMYSTRINGCMP_STRCONSTIFTHISM_PSTRTHISM_PSTRNEWCHARCOPYM_NCURLEN1STRCPYTHISM_PSTR,COPYM_PSTRRETURNTHISCMYSTRINGINTNTHISM_NCURLENCMYSTRINGTEMPTHISDELETETHISM_PSTRTHISM_PSTRNEWCHARLENGTH1FORINTI0IM_PSTRITEMPIFORINTINIM_PSTRIADDM_PSTRINTHISM_PSTRLENGTH0RETURNTHISCHAROSTREAMRETURNISTESTCPPINCLUDEUSINGNAMESPACESTDINCLUDE“MYSTRINGH“INTMAINCMYSTRINGTEST1“BABC“CMYSTRINGTEST2“ABABABCDEFB“COUTTEST2COUT“CLASSBINARYTREETEMPLATECLASSBINTREENODEPUBLICFRIENDCLASSBINARYTREEBINTREENODEM_PLEFTNULL,M_PRIGHTNULLBINTREENODETYPEITEM,BINTREENODELEFTNULL,BINTREENODERIGHTNULLM_DATAITEM,M_PLEFTLEFT,M_PRIGHTRIGHTTYPEGETDATACONST/GETTHDDATABINTREENODEGETLEFTCONST/GETTHELEFTNODEBINTREENODEGETRIGHTCONST/GETTHERIGHTNODEVOIDSETDATACONSTTYPEDATA/CHANGETHEDATAVOIDSETLEFTCONSTBINTREENODELEFT/CHANGETHDLEFTNODEVOIDSETRIGHTCONSTBINTREENODERIGHT/CHANGETHERIGHTNODEVOIDINORDER/INORDERTHETREEWITHTHEROOTOFTHENODEVOIDPREORDER/PERORDERTHETREEWITHTHEROOTOFTHENODEVOIDPOSTORDER/POSTODERTHETREEWITHTHEROOTOFTHENODEINTSIZE/GETSIZEINTHEIGHT/GETHEIGHTBINTREENODECOPYCONSTBINTREENODECOPY/COPYTHENODEVOIDDESTROY/DESTROYTHETREEWITHTHEROOTOFTHENODEIFTHISNULLTHISM_PLEFTDESTROYTHISM_PRIGHTDESTROYDELETETHISFRIENDBOOLEQUALCONSTBINTREENODES,CONSTBINTREENODET/ISEQUALPRIVATEBINTREENODEM_PLEFT,M_PRIGHTTYPEM_DATATEMPLATETYPEBINTREENODEGETDATACONSTRETURNTHISNULLM_DATA1TEMPLATEBINTREENODEBINTREENODEGETLEFTCONSTRETURNTHISNULLM_PLEFTNULLTEMPLATEBINTREENODEBINTREENODEGETRIGHTCONSTRETURNTHISNULLM_PRIGHTNULLTEMPLATEVOIDBINTREENODESETDATACONSTTYPEDATAIFTHISNULLM_DATADATATEMPLATEVOIDBINTREENODESETLEFTCONSTBINTREENODELEFTIFTHISNULLM_PLEFTLEFTTEMPLATEVOIDBINTREENODESETRIGHTCONSTBINTREENODERIGHTIFTHISNULLM_PRIGHTRIGHTTEMPLATEBINTREENODEBINTREENODECOPYCONSTBINTREENODECOPYIFCOPYNULLRETURNNULLBINTREENODETEMPNEWBINTREENODECOPYM_DATATEMPM_PLEFTCOPYCOPYM_PLEFTTEMPM_PRIGHTCOPYCOPYM_PRIGHTRETURNTEMPTEMPLATEBOOLEQUALCONSTBINTREENODES,CONSTBINTREENODETIFSNULLIFSRETURN0TEMPLATEVOIDBINTREENODEINORDERIFTHISNULLTHISM_PLEFTINORDERCOUT“M_DATATHISM_PRIGHTINORDERTEMPLATEVOIDBINTREENODEPREORDERIFTHISNULLCOUT“M_DATATHISM_PLEFTPREORDERTHISM_PRIGHTPREORDERTEMPLATEVOIDBINTREENODEPOSTORDERIFTHISNULLTHISM_PLEFTPOSTORDERTHISM_PRIGHTPOSTORDERCOUT“M_DATATEMPLATEINTBINTREENODESIZEIFTHISNULLRETURN0RETURN1THISM_PLEFTSIZETHISM_PRIGHTSIZETEMPLATEINTBINTREENODEHEIGHTIFTHISNULLRETURN1INTLHEIGHT,RHEIGHTLHEIGHTTHISM_PLEFTHEIGHTRHEIGHTTHISM_PRIGHTHEIGHTRETURN1LHEIGHTRHEIGHTLHEIGHTRHEIGHTBINARYTREEHINCLUDE“BINTREENODEH“TEMPLATECLASSBINARYTREEPUBLICBINARYTREEM_PROOTNULLBINARYTREECONSTTYPESTOPM_STOPSTOP,M_PROOTNULLBINARYTREEBINARYTREEVIRTUALBINARYTREEM_PROOTDESTROYVIRTUALBOOLISEMPTY/ISEMPTYRETURNM_PROOTNULLVIRTUALBINTREENODEGETLEFTBINTREENODECURRENT/GETTHELEFTNODEVIRTUALBINTREENODEGETRIGHTBINTREENODECURRENT/GETTHERIGHTNODEVIRTUALBINTREENODEGETPARENTBINTREENODECURRENT/GHETHDPARENTCONSTBINTREENODEGETROOTCONST/GETROOTVIRTUALBOOLINSERTCONSTTYPEITEM/INSERTANEWNODEVIRTUALBINTREENODEFINDCONSTTYPEITEMCONST/FINDTHDNODEWITHTHEDATAVOIDINORDERVOIDPREORDERVOIDPOSTORDERINTSIZE/GETSIZEINTHEIGHT/GETHEIGHTBINARYTREE/EVALUATENODEFRIENDBOOLOPERATORCONSTBINARYTREES,CONSTBINARYTREET/ISEQUALFRIENDOSTREAM/OUTPUTTHEDATAFRIENDISTREAM/INPUTTHEDATAPRIVATETYPEM_STOP/JUSTUSINGFORINPUTTHEDATABINTREENODEM_PROOT/FINDTHEPARENTOFCURRENTINTHETREEWITHTHEROOTOFSTARTBINTREENODEGETPARENTBINTREENODESTART,BINTREENODECURRENTVOIDPRINTBINTREENODESTART,INTN0/PRINTTHETREEWITHTHEROOTOFSTARTTEMPLATEBINARYTREEBINARYTREEBINARYTREEM_PROOTM_PROOTCOPYCOPYM_PROOTTEMPLATEBINTREENODEBINARYTREEGETLEFTBINTREENODECURRENTRETURNM_PROOTTEMPLATEBINTREENODEBINARYTREEGETRIGHTBINTREENODECURRENTRETURNM_PROOTTEMPLATECONSTBINTREENODEBINARYTREEGETROOTCONSTRETURNM_PROOTTEMPLATEBINTREENODEBINARYTREEGETPARENTBINTREENODESTART,BINTREENODECURRENTIFSTARTNULL|CURRENTNULLRETURNNULLIFSTARTM_PLEFTCURRENT|STARTM_PRIGHTCURRENTRETURNSTARTBINTREENODEPMOVEIFPMOVEGETPARENTSTARTM_PLEFT,CURRENTNULL/FINDTHEPARENTINTHELEFTSUBTREERETURNPMOVEELSERETURNGETPARENTSTARTM_PRIGHT,CURRENT/FINDTHEPARENTINTHERIGHTSUBTREETEMPLATEBINTREENODEBINARYTREEGETPARENTBINTREENODECURRENTRETURNM_PROOTNULL|CURRENTM_PROOTNULLGETPARENTM_PROOT,CURRENTTEMPLATEBOOLBINARYTREEINSERTCONSTTYPEITEMBINTREENODEPSTARTM_PROOT,NEWNODENEWBINTREENODEITEMIFM_PROOTNULLM_PROOTNEWNODERETURN1WHILE1