第7次上机作业题目

《第7次上机作业题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ImplementYourOwnBSTPrerequisites,Goals,andOutcomesPrerequisites:Studentsshouldhavemasteredthefollowingprerequisiteskills.•BinarySearchTree・KnowledgeofBinarySearchTreeandsomeoperationsofBSTGoals:Thisassignmentisdesignedtoreinforcethestudentsunderstandingofthestoreandbasic

2、operationsofBST.Outcomes:Studentssuccessfullycompletingthisassignmentwouldmasterthefollowingoutcomes.•UnderstandtheBSTanditsimplementationBackgroundBinarySearchTreeBinarySearchtreeisabinarytreeinwhicheachinternalnodexstoresanelementsuchthattheelementstoredintheleftsubtre

3、eofxarelessthanorequaltoxandelementsstoredintherightsubtreeofxarcgreaterthanorequaltox.Thisiscalledbinary-search-treeproperty.Thebasicoperationsonabinarysearchtreetaketimeproportionaltotheheightofthetree.Foracompletebinarytreewithnoden,suchoperationsrunin&(lgz?)worst-cas

4、etime.Ifthetreeisalinearchainofnnodes,however,thesameoperationstakes&(〃)worst-casetime.ImplementationofBinarySearchTreeBinarySearchTreecanbeimplementedasalinkeddatastructureinwhicheachnodeisanobjectwithtwopointerfields.Thethreepointerfieldsleft,rightcorrespondingtothelef

5、tchild,rightchildrespectivelyNILinanypointerfieldsignifiesthatthereexistsnocorrespondingchild・rootFig1.LinkedStorageStructureofBSTQueryingaBinarySearchTreeThemostcommonoperationsperformedonaBSTaresearchingforakeystoredinthetree.OtheroperationsareMINIMUM,MAXIMUM,SUCCESSOR

6、andPREDESESSOR.TheseoperationsruninO(/?)timewherehistheheightofthetreei.e.,histhenumberoflinksrootnodetothedeepestnode.TheTREE-SEARCH(x,k)algorithmsearchesthetreerootatxforanodewhosekeyvalueequalsk.Itreturnsapointertothenodeifitexists,otherwiseNILTREE-SEARCH(x,k)ifx=NIL.

7、OR.k=key[x]thenreturnxifA:

8、x]do2.ifRvkey[x]3・thenx<—left[x]4.elsex<—right[x]5.returnxTheTREE-MINIMUN(x)algorithmreturnsapointtothe