《数据结构与算法》(清华)典型例题

学习必备 欢迎下载

(例10-29) 已知哈夫曼树的叶子结点数为no，试推导出该哈夫曼树共有多少个结点。

解析：设度为1的结点数为n1，度为2的结点数为n2，结点总数为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)；

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 {

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 (rooto) {

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)； //在左子树中查找 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； //有左无右