森林的孩子兄弟表示.ppt

《森林的孩子兄弟表示.ppt》由会员分享，可在线阅读，更多相关《森林的孩子兄弟表示.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、森林的孩子兄弟表示法的设计与实现 以奇渠基本要求（1）设计森林的孩子兄弟存储结构。要求实现森林的先根、中根、后根遍历。（2）求森林的规模（森林中树的数目）、森林的高度（森林中树的最大高度）、森林的叶子数（森林中所有树的叶子之和）。（3）在森林的孩子兄弟链表示中，设计并实现相应函数，求相应二叉树的高度和叶子数。森林的孩子兄弟存储结构森林的结点类模板定义同树的结点类模板定义一致templatestruct ChildSiblingForestNode T data;ChildSiblingForestNode *firstChild;ChildSiblingForestNode *nextSibl

2、ing;ChildSiblingForestNode();ChildSiblingForestNode(T val,ChildSiblingForestNode*fChild=NULL,ChildSiblingForestNode*nSibling=NULL);森林的先根遍历森林先根遍历的递归算法思想：若森林为空，则返回；否则，1）访问森林中的第一棵树的根结点；2）先根遍历第一棵树的根结点的子树森林；3）先根遍历除第一棵树外其他树组成的森林。右图所示森林由先根遍历后得到：A、B、C、D、E、F、G、H、J、I森林的先根遍历的递归算法实现templatevoid ChildSiblingFore

3、st:PreRootOrderHelp(ChildSiblingForestNode*r,void(*Visit)(const T&)constif(r!=NULL)/判断森林是否为空(*Visit)(r-data);/访问森林中的第一棵树的根结点PreRootOrderHelp(r-firstChild,Visit);/先根遍历第一棵树的根结点的子树森林PreRootOrderHelp(r-nextSibling,Visit);/先根遍历除第一棵树外其他树组成的森林森林的中根遍历森林中根遍历的递归算法思想：若森林为空，则返回；否则，1）中根遍历第一棵树的根结点的子树森林；2）访问森林中的第一

4、棵树的根结点；3）中根遍历除第一棵树外其他树组成的森林。右图所示森林由中根遍历后得到：B、C、D、A、F、E、J、H、I、G森林的中根遍历的递归算法实现templatevoid ChildSiblingForest:InRootOrderHelp(ChildSiblingForestNode*r,void(*Visit)(const T&)constif(r!=NULL)/判断森林是否为空InRootOrderHelp(r-firstChild,Visit);/中根遍历第一棵树的根结点的子树森林(*Visit)(r-data);/访问森林中的第一棵树的根结点InRootOrderHelp(r-

5、nextSibling,Visit);/中根遍历除第一棵树外其他树组成的森林森林的后根遍历森林后根遍历的递归算法思想：若森林为空，则返回；否则，1）后根遍历第一棵树的根结点的子树森林；2）后根遍历除第一棵树外其他树组成的森林；3）访问森林中的第一棵树的根结点。右图所示森林由后根遍历后得到：D、C、B、F、J、I、H、G、E、A森林的后根遍历的递归算法实现templatevoid ChildSiblingForest:PostRootOrderHelp(ChildSiblingForestNode*r,void(*Visit)(const T&)constif(r!=NULL)/判断森林是否为空

6、PostRootOrderHelp(r-firstChild,Visit);/后根遍历第一棵树的根结点的子树森林PostRootOrderHelp(r-nextSibling,Visit);/后根遍历除第一棵树外其他树组成的森林(*Visit)(r-data);/访问森林中的第一棵树的根结点森林的层序遍历森林层序遍历采用非递归利用队列的辅助完成：若森林为空，则返回；否则，1）将森林里的各树的根结点入队；2）若队列不为空，则出队并访问；3）将2）出队得到的结点的子树组成的森林进行1）和2）步。右图所示森林由层序遍历后得到：A、E、G、B、C、D、F、H、I、J森林的层序遍历的非递归算法实现tem

7、platevoid ChildSiblingForest:LevelOrder(void(*Visit)(const T&)const ChildSiblingForestNode*cur,*i;queueChildSiblingForestNode*q;cur=root;while(cur!=NULL)q.push(cur);cur=cur-nextSibling;while(!q.empty()cur=q.front();q.pop();(*Visit)(cur-data);for(i=cur-firstChild;i!=NULL;i=i-nextSibling)q.push(i);求森林

8、的规模（森林中树的数目）用森林的孩子兄弟表示存储结构求树的数目，只需要从第一棵树的根结点向其右兄弟遍历计数即可，有图为孩子兄弟表示法表示森林。template int ChildSiblingForest:TreeNum()const ChildSiblingForestNode*cur=root;int num=0;while(cur!=NULL)num+;cur=cur-nextSibling;return num;森林的高度（森林中树的最大高度）求森林的高度可以先求每棵树的高度，再求森林高度。求树的高度的递归算法实现template int ChildSiblingForest:Tree

9、HeightHelp(ChildSiblingForestNode*r)const int _max=0;if(r-firstChild=NULL)return 1;for(auto i=r-firstChild;i!=NULL;i=i-nextSibling)_max=max(TreeHeightHelp(i)+1,_max);return _max;森林的高度（森林中树的最大高度）template int ChildSiblingForest:Height()constChildSiblingForestNode*p;int MaxHeight=0,height;for(p=root;p!

10、=NULL;p=p-nextSibling)height=TreeHeightHelp(p);/调用求树的高度的递归函数MaxHeight=(MaxHeight height)?height:MaxHeight;return MaxHeight;森林的叶子数（森林中所有树的叶子之和）求森林的叶子数同样可以向求高度一样，先求森林中每一棵树是叶子数，然后求森林的叶子数。求树的叶子的递归算法实现template int ChildSiblingForest:LeftNumHelp(ChildSiblingForestNode*r)const if(r=NULL)return 0;if(!r-firs

11、tChild)return 1;int sum=0;for(auto i=r-firstChild;i!=NULL;i=i-nextSibling)sum+=LeftNumHelp(i);return sum;森林的叶子数（森林中所有树的叶子之和）利用求树的递归算法求森林的叶子数template int ChildSiblingForest:LeftNum()const int sum=0;auto cur=root;while(cur!=NULL)sum+=LeftNumHelp(cur);cur=cur-nextSibling;return sum;相应二叉树的高度求对应二叉树的高度递归算

12、法思想若对应二叉树根为空，则返回0；否则，对对应二叉树的左子树调用高度递归算法求左子树高度；对对应二叉树的右子树调用高度递归算法求左子树高度；比较左子树与右子树的高度。相应二叉树的高度的递归算法实现template int ChildSiblingForest:BinTreeHeightHelp(ChildSiblingForestNode*r)const if(r=NULL)return 0;return max(BinTreeHeightHelp(r-firstChild),BinTreeHeightHelp(r-nextSibling)+1;相应二叉树的叶子数求对应二叉树的叶子递归算法思

13、想若对应二叉树根为空，则返回0；否则，对对应二叉树的左子树调用求叶子数递归算法求左子树叶子数；对对应二叉树的右子树调用求叶子树递归算法求左子树叶子数；将左子树与右子树的叶子数相加。相应二叉树的求叶子数的递归算法实现template int ChildSiblingForest:BinTreeLeafNumHelp(ChildSiblingForestNode*r)const if(r=NULL)return 0;if(r-firstChild=NULL&r-nextSibling=NULL)return 1;return BinTreeHeightHelp(r-firstChild)+BinTreeHeightHelp(r-nextSibling);代码运行结果谢谢！