数据结构课件第六章树幻灯片.ppt

一、树的遍历 二、森林的遍历 三、树的遍历的应用 树的遍历可有三条有哪些信誉好的足球投注网站路径: 按层次遍历: 先根(次序)遍历: 后根(次序)遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 若树不空，则自上而下自左至右访问树中每个结点。 A B C D E F G H I J K 先根遍历时顶点的访问次序： A B E F C D G H I J K 后根遍历时顶点的访问次序： E F B C I J K H G D A 层次遍历时顶点的访问次序： A B C D E F G H I J K B C D E F G H I J K 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林； 3．森林中其它树构成的森林。 森林由三部分构成： 1. 先序遍历 森林的遍历 若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行先根遍历。 ２．中序遍历 若森林不空，则 中序遍历森林中第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。 树的遍历和二叉树遍历的对应关系 ？ 先根遍历 后根遍历 树 二叉树 森林 先序遍历 先序遍历 中序遍历 中序遍历 设树的存储结构为孩子兄弟链表 typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; 一、求树的深度 二、输出树中所有从根到叶子的路径 三、建树的存储结构 int TreeDepth(CSTree T) { if(!T) return 0; else { h1 = TreeDepth( T-firstchild ); h2 = TreeDepth( T-nextsibling); } } // TreeDepth return(max(h1+1, h2)); 一、求树的深度的算法： 二、输出树中所有从根到叶子的路径的算法: A B C D E F G H I J K 例如：对左图所示的树，其输出结果应为： A B E A B F A C A D G H I A D G H J A D G H K void AllPath( Bitree T, Stack S ) { if (T) { Push( S, T-data ); if (!T-Lchild !T-Rchild ) PrintStack(S); else { AllPath( T-Lchild, S ); AllPath( T-Rchild, S ); } Pop(S); } // if(T) } // AllPath // 输出二叉树上从根到所有叶子结点的路径 void OutPath( Bitree T, Stack S ) { while ( !T ) { Push(S, T-data ); if ( !T-firstchild ) Printstack(s); else OutPath( T-firstchild, s ); Pop(S); T = T-nextsibling; } // while } // OutPath // 输出森林中所有从根到叶的路径 三、建树的存储结构的算法: 和二叉树类似，不同的定义相应有不同的算法。 假设以二元组(F，C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子