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

《数据结构(牛小飞)树的遍历的应用.ppt》由会员分享，可在线阅读，更多相关《数据结构(牛小飞)树的遍历的应用.ppt（13页珍藏版）》请在三一办公上搜索。

1、树的遍历的应用,设树的存储结构为孩子兄弟链表,一、求树的深度,二、输出树中所有从根到叶子的路径,三、建立树的存储结构,class CSNode Object data;CSNode firstChild;CSNode nextSibling;,A,B,C,D,E,F,G,B,树的遍历的应用,一、求树的深度的算法：,1、如果T为空，则树的深度为0,2、求出T每棵子树的深度,3、从所有子树的深度中取最大，然后加1，即为树的深度,public int depth(Tree T)/只考虑逻辑结构,if(t=null)return 0;,for(p=T1,T2,Tn)/每棵子树,dp=depth(p),

2、a=max(d1,d2,dn),return(a+1),树的遍历的应用,public int depth(CSNode t)/二叉链表作为存储结构,if(t=null)return 0;/空树,p=t.firstchildNode;d=0;,while(p)/依次求子树的深度,return(d+1);,int d1=depth(p);,if(d1d)d=d1;,p=p.nextsibling;,树的遍历的应用,二、输出树中所有从根到叶子的路径的算法:,对左图所示的树，其输出结果为：,A B EA B FA CA D G H IA D G H JA D G H K,树的遍历的应用,对树先根遍历(

3、深度优先),1、T为空，栈中存放的是从根到T的父节点的路径,2、将T压栈，栈中存放的是从根到T的路径,递归访问T的子树,将T出栈,树的遍历的应用,二、输出树中所有从根到叶子的路径的算法:,public void AllPath(CSTree T,Stack S)/树的先根遍历/AllPath,Push(S,T.data);/树根压栈,p=T.firstchild/T的第一颗子树,while(p)/T的所有子树 AllPath(p,S);p=p.nextsibling;,Pop(S);/访问完T的所有子树,if(!T)PrintStack(S),return,树的遍历的应用,void OutPa

4、th(CStree T,Stack S),Push(S,T.data);,OutPath(T.firstchild,S);,OutPath(T.nextsibling,S);,if(!T)return;,利用二者的先序遍历结果相同,if(!T.firstchild)/”叶子”节点 printStack(S);pop(S);,树的遍历的应用,三、建树的存储结构的算法:,不同的存储方式相应有不同的算法。,假设以二元组(P,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。,树的遍历的应用,对左侧所示树的输入序列应为:,(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)

5、(E,G),(#,A),(A,B),(A,C),(A,D),(C,E),A,B,C,D,可见，算法中需要一个队列保存已建好的节点,树的遍历的应用,void CreatTree(CSTree T,Queue queue),树的遍历的应用,p=CSNode(child);,queue.add(p);,if(parent=#)T.rootNode=p;/所建为根节点,else/非根节点的情况,do while(child!=#);,将parent及child读入,创建节点节点入队列,T.rootNode=NULL;,if(child!=#)else break,m=queue.peek();/取队列

6、头元素(指针值)while(m.data!=parent)/查询双亲节点 queue.remove();m=queue.peek();,树的遍历的应用,if(m.firstchild!=null)m.firstchild=p;/链接第一个孩子节点else r=m.firstchild;/链接其它孩子节点 while(r.nextsibling)r=r.nextsibling;r.nextsibling=p;,非根节点的情况,树的遍历的应用,将parent及child读入,InputStreamReader isr=new InputStreamReader(System.in);BufferedReader br=new BufferedReader(isr);String s=br.readLine();char parent=s.charAt(0);char child=s.charAt(2);,