发布时间 : 星期四 文章数据结构典型例题更新完毕开始阅读22e8e67b168884868762d6f1
数为n，则有
n=n0+n1+n2
根据二叉树的性质3有
n=n2+1
又由哈夫曼树的构造原理可知，哈夫曼树中不存在度为l的结点，即nl＝0，所以有
n=n0+n2=n0+n0-1=2n0-1
[例10-30] 设给定字符集合{a，b，c，d，e，f} 的权值集合w={2，3，4，?，8，9}，试构造关于w的一颗哈夫曼树，并求其带权路径长度及各字符的哈夫曼编码。 解析：根据给定的权值集合构造的哈夫曼树如图10.19所示。 其加权路径长度WPL＝(9+7+8)×2+4×3十(2+3)×4＝80。 各字符的哈夫曼编码如下：
a 0000 b 0001 c 001 d 10 e 11 f 0l
注意：此题哈夫曼树形不唯一，因此哈夫曼编码也有多种方案，但WPL是一定的。 五、算法设计题
[例10-31] 给定一个二叉树t，试设计算法输出其嵌套括号的表示。
解析：首先输出根结点，然后再依次输出它的左子树和右子树，在输出左子树之前输出左括号，在输出右子树之前输出右括号；若左、右子树都为空，则无需输出。
具体算法如下： void disptree(bitree * t) (
if(t! =NULL) {
printf(\—>data)；
25
if(t—>lchild ! =NULL | | t—>rchild ! =NULL) {
printf (\； disptree(t—> lchild)； if(t—>rchild ! =NULL) printf(\，\； disptree(t—>rchild)； printf(\； } } }
[例10-32] 假设二叉树采用链式存储，编写一个二叉树后序遍历的非递归算法。
解析：根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点。先扫描根结点的所有左结点并入栈，然后扫描当前栈顶结点的右孩子并入栈，再扫描该右孩子的所有左结点并人栈，最后扫描当前栈顶结点的右孩子并人栈，反复进行，直到当前栈顶结点没有右孩子(此过程从根出发，查找最左下方第一个叶子结点，并将所经过的结点人栈)。若栈顶结点的左、右子树都已被访问，则访问它并出栈；否则以它的右孩子为根出发重复开始的过程。如此这般，直到栈空为止。其中的难点是如何判断一个结点的右孩子结点已访问过，为此用p保存刚访问过的结点，若t一>rchild＝＝p成立(在后序遍历中，t的右孩子结点必然在t之前被访问)，则说明t的左、右子树均已访问，现在应访问t。具体算法如下： void lastorder (bitree * t) {
bitree * stack [MaxSize]，* p；
int flag，top= -1； //置空栈 do {
while (t! =NULL) //将t的所有左结点人栈 { top++； stack[top]＝t t=t—>lchild； }
p=NULL； //p指向当前结点的前一个已访问结点 flag=1； //设置t的访问标志为已访问 while (top!＝-1&& flag) {
t=stack[top] //取当前栈顶元素
if(t—>rchild==p) //右子树不存在或已被访问，访问t {
printf(“％d”，t—>data)；
top--； //出栈 p=t； } else {
26
t=t一>rchild； //t指向其右子树
flag=0； //设置未被访问的标志 } }
} while(top!=-1)； //当栈非空 }
(例10-33) 设一棵完全二叉树采用顺序存储结构存储在数组bt[n+1](从下标为1到下标为n)中，请写出非递归的先序遍历算法。
解析：由二叉树的顺序存储可知，将完全二叉树的结点以层为序，同层从左到右进行编号，然后以编号为下标存储在数组bt中。根据二叉树性质5可得出结点间的存储与逻辑的对应关系。具体算法如下： void preoder ( int bt[]，int n) {
int root，top，stack [MaxSize]；
root=1； //root指向根结点 top= —1； //置空栈 while (root
while (root print (“％ d”，bt[root])； top++； //访问过的结点人栈 stack [top]=root； root=2 * root； //指向左孩子 } if(top!= -1) //指向栈顶元素的右孩子，并出栈 { root=stack[top] * 2+1； top--； } } } (例10-34) 假设二叉树采用链式存储结构，设计一个算法求二叉树中指定结点的层数。 解析：本题采用递归算法，设h返回p所指结点的高度，初始值为-1。找到指定的结 点时返回其层次；否则返回-1。1h作为一个中间变量在计算、搜索层次时使用，初始值为 1。具体算法如下： void level(bitree * t，bitree * p，int * h，int lh) { if(b = =NULL) h= -l； //空树时返回—1 else if (p==t) //找到结点p h=lh； else { level(t—>lchild，p，h，lh+1)； //在左子树中查找 27 if (* h = = - 1) level(t—>rchild，p，h，1h+1)； //在右子树中查找 } } [例10-35] 设计一个算法，判断一棵二叉树是否为完全二叉树。 解析：若二叉树采用链式存储结构，则根据完全二叉树的定义，对完全二叉树按层次遍历时应该满足：若某结点没有左孩子，则必无右孩子；若某结点缺孩子，则其所有的后继都是叶子。若不满足以上条件，则该二叉树就不是完全二叉树。具体算法如下： int fullbitreel (bitree * t) { bitree * s，* Q[MaxSize]； int rear=1，front=0，flag=1； //flag表示到目前为止所有结点均有2个孩子 if(t＝＝NULL) return 1； Q[rear]＝t //根结点地址人队 while (front front++； //出队 s=Q[front]； if (!flag && (s—>1child!＝NULL | | s—>rchil！＝NULL)) return 0； if (s—>1child＝＝NULL) { flag=0； //无左 if (p—>rchild! = NULL) //左空右不空，非完全二叉树 return 0； } else { Q一>[++rear]＝s—>lchild； //s结点的左孩子的地址人队 if (s一>rchild＝＝NULL) flag=0； //有左无右 else Q一>[++rear]＝s—>rchild； //s结点的右孩子的地址人队 } } return 1； } 若二叉树采用顺序存储结构，则只需判断从第一个结点位置到最后一个结点位置之间 没有空结点即可。假设二叉树存储在数组bt[n+1]中，具体算法如下： int fu11bitree2 (char bt[]，int n) { int i； for(i＝1；i<＝n；i++) 28