树 树的遍历+排序1 2011 fabu.pptVIP

复习 树的定义和性质 二叉树的遍历 由遍历序列确定二叉树的问题 线索二叉树 堆 Huffman树 二叉排序树* 树 树和森林 内容提要 树的存储结构 树的遍历 森林 双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难 双亲表示法-示意 孩子表示法（孩子链表） 多重链表：每个结点有多个指针域，分别指向其子树的根 孩子表示法（孩子链表） Typedef struct CTree{ Node *nodelist; List *children; int root; int sizenode,size children; int MaxN; } CTree; 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点 操作容易 破坏了树的层次 孩子兄弟表示法（二叉树表示法）-结点定义 typedef struct CSNode{ datatype Elemdata; struct CSNode *firstchild, *nextsibling; }CSNode, *CSTree; 树的遍历方法 按层次遍历 先访问第一层上的结点，然后依次遍历第二层，……，第n层的结点 先序遍历（先根） 先访问树的根结点，然后依次先序遍历根的每棵子树 后序遍历（后根） 先依次后序遍历每棵子树，然后访问根结点 先序遍历：ABEF IGCDHJ KLNOM 后序遍历：EIFGBCJKNOLMHDA 层次遍历：ABCDE FGHI JKLMNO 树遍历的应用 ？如何求树的深度 ？输出树中所有从根到叶子的路径 ？建树的存储结构 提示不同的存储结构实现不同 一、求树的深度的算法： int Depth(CSTree T) {//T是二叉树表示法 if (T==NULL) return 0; else{ d1 = Depth(T-firstchild); d2 = Depth(T-nextsibling); return Max{d1+1,d2+2} } 一、求树的深度的算法： Int TreeDepth( CTree T ) { // T 是树的孩子链表存储结构， // 返回该树的深度 if (T.n == 0) return 0; else return Depth( T, T.r ); }// TreeDepth int Depth( CTree T, int root ) { max = 0;p = T.nodes[root].firstchild; while( p ) {h = Depth( T, p-child ); if ( h max ) max = h; p = p-nextchild;}//while return max+1;} 二、输出树中所有从根到叶子的路径的算法 输出二叉树上从根到所有叶子结点的路径 void AllPath( BiTreeT, StackS ) { 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 输出森林中所有从根到叶的路径 voidOutPath( CSTree T, Stack S ) { while( !T ) { Push(S, T-data ); if( !T-firstchild) Printstack(S); elseOutPath( T-firstchild, S ); Pop(S); T = T-nextsibling; }// while }// OutPath// 三、建树的存储结构的算法: 和二叉树类似，不同的定义相应有不同的算法。 假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。 见演示程序 森林 森林 可以分解成三部分： 1。森