操作系统教程北京大学出版第六章_树.ppt

void main() { /* ABC＃＃DE＃G＃＃F＃＃＃ */ bitree *head=NULL; int count=0; head=crt_bt_pre(head); countleaf(head,count); printf(count of leaf node is %d\n,count); } 创建树并求二叉树的叶子结点算法 * 求二叉树深度算法 void treedepth(bitree *bt,int *l,int *h) { int l1=0,l2=0,h1=0,h2=0; if(bt!=NULL) { (*l)++; if (*l*h) *h=*l; treedepth(bt-lchild,l1,h1); treedepth(bt-rchild,l2,h2); if (h1h2) *h=*h+h1; else *h=*h+h2; } } void main() { /* ABC＃＃DE＃G＃＃F＃＃＃ */ bitree *head=NULL; int level=0,high=0; head=crt_bt_pre(head); treedepth(head,level,high); printf(depth of tree is %d\n,high); } * 6.5 树和森林 树、森林与二叉树的转换 在树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可唯一地对应导一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。 * A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 存储 存储 解释 解释 树与二叉树转换 * 将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45° A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树其右子树一定为空 * 将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I * 森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转， 构成二叉树型结构 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J * 二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支有哪些信誉好的足球投注网站到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J * 6.6 二叉树的应用 哈夫曼树(Huffman)——带权路径长度最短的树 定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~ 路径长度：路径上的分支数 树的路径长度：从树根到每一个结点的路径长度之和 树的带权路径长度：树中所有带权结点的路径长度之和 * Huffman树——设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点 的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫~ 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 d c a b 2 4 7 5 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 * a b c d 7 5 2 4 WPL