哈夫曼树的构造_哈夫曼树路径长度_哈夫曼树的权(2)

解：输出一棵二叉树的所有叶子结点的递归模型f()如下： f(b)：不做任何事件 若b=NULL f(b)：输出b结点的data域 若b为叶子结点 f(b)：f(b->lchild);f(b->rchild) 其他情况 void DispLeaf(BiTree b) { if (b!=NULL) { if (b->lchild==NULL && b->rchild==NULL) printf("%c ",b->data); else { DispLeaf(b->lchild); DispLeaf(b->rchild); } } } 例2:求高度BiTreeDepth(b) 求二叉树的高度的递归模型f()如下： f(NULL)=0 f(b)=MAX{f(b->lchild),f(b->rchild)}+1 其他情况 对应的算法如下： int BiTreeDepth(BiTree b) { int lchilddep,rchilddep; if (b==NULL) return(0); /*空树的高度为0*/ else { lchilddep=BiTreeDepth(b->lchild); /*求左子树的高度为lchilddep*/ rchilddep=BiTreeDepth(b->rchild); /*求右子树的高度为rchilddep*/ return (lchilddep>rchilddep)? (lchilddep+1): (rchilddep+1); } } 例3: 假设二叉树采用二叉链存储结构,设计一个算法判断两棵二叉树是否相似,所谓二叉树t1和t2是相似的指的是t1和t2都是空的二叉树；或者t1和t2的根结点是相似的,以及t1的左子树和t2的左子树是相似的且t1的右子树与t2的右子树是相似的。

解：判断两棵二叉树是否相似的递归模型f()如下： f(t1,t2)=true 若t1=t2=NULL f(t1,t2)=false 若t1、t2之一为NULL,另一不为NULL f(t1,t2)=f(t1->lchild,t2->lchild) & f(t1->rchild,t2->rchild) 其他情况 int Like(BiTree t1,BiTree t2) /*t1和t2两棵二叉树相似时返回1,否则返回0*/ { int like1,like2; if (t1==NULL && t2==NULL) return 1; else if (t1==NULL || t2==NULL) return 0; else { like1=Like(t1->lchild, t2->lchild); like2=Like(t1->rchild, t2->rchild); return (like1 & like2); /*返回like1和like2的与*/ } } 例4: 假设二叉树采用二叉链存储结构,设计一个算法Level()求二叉树中指定结点的层数。

解：本题采用递归算法,设h返回p所指结点的高度,其初值为0。找到指定的结点时返回其层次；否则返回0。lh作为一个中间变量在计算搜索层次时使用,其初值为1。对应的算法如下： void Level(BiTree T, BiTree p, int &h, int lh) /*找到*p结点后h为其层次,否则为0*/ { if (T==NULL) h=0; /*空树时返回0*/ else if (p==T) h=lh; /*找到结点p时*/ else { Level(b->lchild,p,h,lh+1); /*在左子树中递归查找*/ if (h==0) /*左子树中未找到时在右子树中递归查找*/ Level(b->rchild,p,h,lh+1); } } 本章小结 本章的基本学习要点如下： (1)掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、孩子结点、双亲结点、树的深度、森林等定义。哈夫曼树路径长度 (2)掌握树的表示,包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握树与二叉树的性质。 (5)重点掌握二叉树的存储结构,包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)灵活运用二叉树这种数据结构解决一些综合应用问题。 * 第6章 树和二叉树

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-33590-2.html