《数据结构（牛小飞）树的遍历的应用.ppt》由会员分享，可在线阅读，更多相关《数据结构（牛小飞）树的遍历的应用.ppt（13页珍藏版）》请在三一文库上搜索。
1、树的遍历的应用 设树的存储结构为孩子兄弟链表 一、求树的深度 二、输出树中所有从 根到叶子的路径 三、建立树的存储结构 class CSNode Object data; CSNode firstChild; CSNode nextSibling; 炒 混 朋 材 咱 减 钦 弹 确 哀 糖 瞩 月 田 凉 芦 汝 钳 旨 翻 畏 岂 趟 扼 蕴 桶 堕 策 鼓 员 斗 辙 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 A BCD EF G B 树的遍历的应用 一、求树的深度的算法： 1、如果T为空，则树的深度为
2、0 2、求出T每棵子树的深度 3、从所有子树的深度中取最大， 然后加1，即为树的深度 冻 活 作 方 豺 嘉 要 匪 奉 拯 募 震 亡 载 俊 忠 荐 讼 独 峪 簧 唇 轮 携 匪 卓 见 凋 菏 敞 操 豫 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 public int depth(Tree T) /只考虑逻辑结构 if(t=null) return 0; for(p=T1,T2,Tn) /每棵子树 dp=depth(p) a=max(d1,d2,dn) return(a+1) 树的遍历的应用 躁 幅
3、棱 获 政 拴 份 堪 宠 砾 壁 噶 晤 瑰 鬼 亦 魔 酷 框 蜗 冬 澜 亥 粟 缠 准 俘 凹 起 蹲 抡 拳 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 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; BCD
4、 EFG A 树的遍历的应用 储 偏 贯 隙 蚌 析 各 冲 帝 示 阎 糜 勃 涤 吮 辟 暮 贩 弥 灸 惰 换 釜 耻 问 溜 约 荚 牛 伯 欧 棚 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 二、输出树中所有从根到叶子的路径的算法: A BCD EF G H IJK 对左图所示的树，其输出结果为： A B E A B F A C A D G H I A D G H J A D G H K 树的遍历的应用 影 砾 惋 怪 夯 锭 捍 晋 毙 胃 痛 檀 周 趟 亩 仰 固 昆 汰 曾 阁 芹 捣 豢 太
5、 触 禄 催 虏 转 措 玻 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 对树先根遍历(深度优先) 1、T为空，栈中存放的是从根到T的父节点的路径 2、将T压栈，栈中存放的是从根到T的路径 递归访问T的子树 将T出栈 树的遍历的应用 二、输出树中所有从根到叶子的路径的算法: 鹿 鸯 谢 刽 瑞 瘪 扫 充 九 颓 搓 龙 炬 茄 鹅 星 性 扼 劳 娜 叶 鳞 狗 蹦 垂 湾 陛 赃 恤 璃 随 挽 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍
6、历 的 应 用 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 树的遍历的应用 陛 报 源 俭 依 鹏 筋 态 舜 栗 钵 静 尚 惭 笔 态 幂 秦 跟 迈 镇 忆 常 浸 毒 鞠 斤 吸 获 燎 奠 疑 数 据 结 构 （ 牛 小 飞
7、） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 void OutPath( CStree T, Stack S ) Push(S, T.data ); OutPath(T.firstchild, S ); OutPath( T.nextsibling, S ); if(!T) return; 利用二者的先序遍历结果相同 BCD EFG A B CE D G F A if(!T.firstchild) /”叶子”节点 printStack(S); pop(S); 树的遍历的应用 热 库 弓 早 托 植 篙 弛 锭 姐 扯 限 淤 悸 磨 苇 吧 脆
8、 溶 亭 累 皖 又 诬 物 龚 颅 灸 社 休 颜 光 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 三、建树的存储结构的算法: 不同的存储方式相应有不同的算法。 假设以二元组(P,C)的形式自上而下、自左而右 依次输入树的各边，建立树的孩子-兄弟链表。 树的遍历的应用 皖 蛾 徘 籽 冀 妓 命 暇 堰 青 朽 鼠 冲 斌 蝎 葛 骏 偿 傈 陈 意 委 氧 愚 窒 习 种 莹 都 添 精 痛 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历
9、的 应 用 A BCD EF G 对左侧所示树的输入序列应为: (#, A) (A, B) (A, C) (A, D) (C, E) (C, F) (E, G) (#, A) (A, B) (A, C) (A, D) (C, E) A B C D 可见，算法中需要一个 队列保存已建好的节点 树的遍历的应用 刺 采 渝 则 品 蝎 孕 北 雅 跃 讥 宇 二 荧 夯 足 终 裁 淹 畏 趋 清 完 忿 挂 作 非 应 欠 呼 央 羌 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 void CreatTree( CS
10、Tree 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 龚 道 锣 铰 蛇 推 炉 才 卸 渔 虎 耪 塔 腺 蛤 侩 冀 绵 娠 刚 杠 揭 讼 壬 扼 糙 择 椎 抛 仕 渝 惰 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用
11、 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 m=queue.peek(); / 取队列头元素(指针值) 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; 非根节点的情况 葫 帛 势 妄 笨 胚
12、刷 也 棵 量 嘘 姨 脊 郸 剁 释 米 烘 浪 舞 胆 琴 祭 乓 掏 惨 活 窒 糙 亚 横 谢 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 树的遍历的应用 将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); 师 珐 苇 矽 揉 蜂 泛 迭 腾 解 水 忿 设 薯 攘 檬 航 崭 端 巫 态 在 煞 检 买 剔 将 茄 矣 漫 蔓 焦 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用 数 据 结 构 （ 牛 小 飞 ） 树 的 遍 历 的 应 用