数据结构C++PPT6

数据结构第6章树肖正信息与智能系统系[e-mail]26.1树的定义与术语DataStructure3术语DataStructure4术语DataStructure5术语DataStructure6GeneralTreeNode//GeneraltreenodeADTtemplateclassElemclassGTNode{public:GTNode(constElem&);//Constructor~GTNode();//DestructorElemvalue();//ReturnvalueboolisLeaf();//TRUEifisaleafGTNode*parent();//ReturnparentGTNode*leftmost_child();//FirstchildGTNode*right_sibling();//RightsiblingvoidsetValue(Elem&);//Setvaluevoidinsert_first(GTNodeElem*n);voidinsert_next(GTNodeElem*n);voidremove_first();//Removefirstchildvoidremove_next();//Removesibling}；DataStructure7树的ADT//GeneraltreeADTtemplateclassElemclassGenTree{private:voidprinthelp(GTNode*);//Printhelperfunctionpublic:GenTree();//Constructor~GenTree();//Destructorvoidclear();//SendnodestofreestoreGTNode*root();//Returntheroot//Combinetwosubtreesvoidnewroot(Elem&,GTNodeElem*,GTNodeElem*);voidprint();//Printatree};DataStructure8树的周游DataStructure9树的周游先根周游：RACDEBF后根周游：CDEAFBRRABFDECDataStructure10树的广度优先周游DataStructure11先根周游算法templateclassElemvoidGenTreeElem::printhelp(GTNodeElem*subroot){if(subroot-isLeaf())coutLeaf:;elsecoutInternal:;coutsubroot-value()\n;for(GTNodeElem*temp=subroot-leftmost_child();temp!=NULL;temp=temp-right_sibling())printhelp(temp);}DataStructure126.2父指针表示法DataStructure13EquivalenceClassProblemTheparentpointerrepresentationisgoodforanswering:Aretwoelementsinthesametree?//ReturnTRUEifnodesindifferenttreesboolGentree::differ(inta,intb){introot1=FIND(a);//Findrootforaintroot2=FIND(b);//Findrootforbreturnroot1!=root2;//Compareroots}DataStructure14Union/FindvoidGentree::UNION(inta,intb){introot1=FIND(a);//Findrootforaintroot2=FIND(b);//Findrootforbif(root1!=root2)array[root2]=root1;}intGentree::FIND(intcurr)const{while(array[curr]!=ROOT)curr=array[curr];returncurr;//Atroot}Wanttokeepthedepthsmall.Weightedunionrule:Jointhetreewithfewernodestothetreewithmorenodes.DataStructure15EquivalenceClassProcessing（1）DataStructure16EquivalenceClassProcessing（2）DataStructure17PathCompressionintGentree::FIND(intcurr)const{if(array[curr]==ROOT)returncurr;returnarray[curr]=FIND(array[curr]);}DataStructure186.3树的实现子结点表表示法DataStructure196.3.2左子节点/右兄弟节点表示法DataStructure20左子节点/右兄弟节点表示法DataStructure216.3.3动态结点表示法DataStructure22子结点指针链表DataStructure236.3.4动态左子结点/右兄弟结点表示法DataStructure24转换过程示例DataStructure25等价二叉树DataStructure26二叉树到森林DataStructure27转换过程示例DataStructure28等价的森林DataStructure29等价的二叉树表示DataStructure306.4K叉树K叉树的结点有K个子结点子结点的数目是固定的当K变大时，空指针的潜在数目会增加，并且叶结点与分支结点在所需空间大小上的差异也会更显著。当K增加时，对叶结点和分支结点采用不同的实现方法。DataStructure316.5树的顺序表示法