数据结构(牛小飞)树的遍历的应用.pptVIP

树的遍历的应用设树的存储结构为孩子兄弟链表一、求树的深度二、输出树中所有从根到叶子的路径三、建立树的存储结构classCSNode{Objectdata;CSNodefirstChild;CSNodenextSibling;}ABCDEFGB树的遍历的应用一、求树的深度的算法：1、如果T为空，则树的深度为02、求出T每棵子树的深度3、从所有子树的深度中取最大，然后加1，即为树的深度树的遍历的应用publicintdepth(TreeT){//只考虑逻辑结构if(t==null)return0;for(p=T1,T2,…Tn){//每棵子树d[p]=depth(p)a=max(d[1],d[2],…d[n])return(a+1)}树的遍历的应用publicintdepth(CSNodet){//二叉链表作为存储结构}if(t==null)return0;//空树p=t.firstchildNode;d=0;while(p){//依次求子树的深度}return(d+1);intd1=depth(p);if(d1d)d=d1;p=p.nextsibling;BCDEFGA树的遍历的应用二、输出树中所有从根到叶子的路径的算法:ABCDEFGHIJK对左图所示的树，其输出结果为：ABEABFACADGHIADGHJADGHK对树先根遍历(深度优先)T为空，栈中存放的是从根到T的父节点的路径将T压栈，栈中存放的是从根到T的路径递归访问T的子树将T出栈123二、输出树中所有从根到叶子的路径的算法:树的遍历的应用树的遍历的应用publicvoidAllPath(CSTreeT,StackS){//树的先根遍历}//AllPathPush(S,T.data);//树根压栈p=T.firstchild//T的第一颗子树while(p){//T的所有子树AllPath(p,S);p=p.nextsibling;}Pop(S);//访问完T的所有子树if(!T){PrintStack(S),return}树的遍历的应用voidOutPath(CStreeT,StackS){Push(S,T.data);OutPath(T.firstchild,S);OutPath(T.nextsibling,S);if(!T)return;}利用二者的先序遍历结果相同BCDEFGABCEDGFAif(!T.firstchild){//”叶子”节点printStack(S);pop(S);}不同的存储方式相应有不同的算法。01假设以二元组(P,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。02三、建树的存储结构的算法:树的遍历的应用树的遍历的应用ABCDEFG对左侧所示树的输入序列应为:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)ABCD可见，算法中需要一个队列保存已建好的节点树的遍历的应用voidCreatTree(CSTreeT,Queuequeue){} p=CSNode(child);queue.add(p);if(parent==?#?)T.rootNode=p;//所建为根节点else{ }//非根节点的情况do{ }while(child!=‘#’);将parent及child读入创建节点节点入队列T.rootNode=NULL;if(child!=‘#’){}elsebreak