C．左右指针均为空    D. 左右指针均不为空

（二）应用题
 
1、一棵满 k 叉树，按层次遍历（从 1 开始对全部结点进行编号）存储在一维数组中，试计
算编号为 u 的结点的第 i 个孩子（若存在）的下标以及编号为 v 的结点的双亲结点（若存 在）的下标。
答：
结点下标为 u 的结点的第 i 个孩子的下标： k (u 1) 1 i
结点下标为 v 的结点的父母结点的下标： (v 2) / k 1
2、试求有 n 个叶结点的非满的完全二叉树的高度. 答：
完全二叉树中叶子结点数为 n，则根据完全二叉树的性质，度为 2 的结点数是 n-1， 而 完全二叉树中，度为 1 的结点数至多为 1，
所以具有 n 个叶子结点的完全二叉树结点数是 n+(n-1)+1=2n 或 2n-1（有或无度为 1 的 结点）。
由 于 具 有 2n( 或 2n-1) 个结 点 的 完 全二 叉树的深度是 log2(2n)+1( 或 log2(2n- 1)+1)，即 log2n+1,故 n 个叶结点的非满的完全二叉树的高度是 log2n+1。（最下层结 点数>=2）。

3、已知一棵度为 m 的树中有 N1 个度为 1 的结点，N2 个度为 2 的结点，……Nm 个度为 m 的结 点，问该树中有多少个叶子结点。请写出推导过程。
答：设 N 为总结点数，N0 为叶子结点数则：N=N0+N1+N2+……+Nm 又有：N-1=度的总数，则：N-1=N1*1+N2*2+……Nm*m 则有： N0=1+N2+2N3+……+(m-1)Nm

4．有七个带权结点，其权值分别为 3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈夫 曼树，并计算出带权路径长度 WPL。
答：

 

WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131

5、给定字母 a,b,c,d,e 的使用频率为 0.09,0.17,0.2,0.23,0.31。设计以该权值为基础的哈 夫曼树，并给出哈夫曼编码？平均长度是多少？
答： 构造的哈夫曼树如下：


- 17 -
 

 





c    d    e


a    b
哈夫曼编码如下：
c(00)
d(01)
a(100)
b(101)
e(11)
平均长度=0.09*3+0.17*3+0.2*2+0.23*2+0.31*2=2.26

6. 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的 基本目的是什么，并指出树和二叉树的主要区别。
解：
树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同， 也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示， 并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有：一是二叉树的度至多为 2，树无此限制；二是二叉树有左右子 树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；

7. 如果给出了一个二叉树结点的前序序列和中序序列，能否构造出此二叉树?若能，请证 明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造 出此二叉树?若能，请证明之。若不能，请给出反例。
解：
给定二叉树前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元 素是根结点，该元素将二叉树中序序列分成两部分，左边（设 l 个元素）表示左子树，若 左边无元素，则说明左子树为空；右边（设 r 个元素）是右子树，若为空，则右子树为空。 根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的 l 个结点序列和 中序序列根左边的 l 个结点序列构造左子树，由前序序列最后 r 个元素序列与中序序列根 右边的 r 个元素序列构造右子树。
由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部 分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相 同，后序序列相同，但却是两棵不同的二叉树。
（三）算法设计题 1．请利用栈的基本操作写出先序遍历二叉树的非递归形式的算法。要求 以二叉链表作为二
叉树的存储结构。函数原型如下：
 
void PreOrder(Bitree T)；

答：void PreOrder(Bitree T)
{
InitStack(S); Push(S,T); while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)
{
visit(p->data); push(S,p-
>lchild);
}
pop(S,p); if(!StackEmpty(S))
{
pop(S,p); push(S,p-
>rchlid);
}
}
}

2．试写一个判别给定二叉树是否为二叉排序树的递归算法，设此二叉树以二叉链表作存 储结构，且树中结点的关键字均不同。函数原型如下：
int Is_BSTree（BiTree T）；

答：int last=0,flag=1; int Is_BSTree（BiTree T）
{
if(T->lchild&&flag)    Is_BSTree(T->lchild); if(T->data<last)    flag=0;
last=T->data;
if(T->rchild&&flag)    Is_BSTree(T->rchild); return flag;
}

3．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该 算术表达式值的算法。 答：以二叉树表示算术表达式，根结点用于存储运算符。若能先分 别求出左子树和右子树 表示的子表达式的值，最后就可以根据根结点的运算符的要求，计 算出表达式的最后结果。 typedef struct node
{
ElemType    data;    float val;
char optr;    //只取‘+’， ‘-’， ‘*’，‘/’
 
struct node *lchild，*rchild
}BiNode,*BiTree;
float PostEval(BiTree bt)    // 以后序遍历算法求以二叉树表示的算术表达式的值
{
float lv,rv; if(bt!=null)
{
lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch(bt->optr)
{
case    ‘+’: value=lv+rv; break; case    ‘-’: value=lv-rv;break; case    ‘*’: value=lv*rv;break; case    ‘/’: value=lv/rv;
}
}
return(value);
}

4．设计算法， 已知一棵以二叉链表存储的二叉树，root 指向根结点，p 指向二叉树中任 一结点，编写算法求从根结点到 p 所指结点之间的路径（要求输出该路径上每个结点的数 据）。
答：
void path(Bintree    T, Bintree p)
{Bintree stack[max],q; int tag[max],top=0,find=0; q=T;
while ((q||top)&& find==0)
{while (q)
{stack[top]=q; tag[top++]=0; q=q-
>lchild;
}
if (top>0)
{q=stack[top-1];
if (tag[top-1]==1)
{if (q==p)
{for (i=0;i<top;i++) printf(“%d”,stack[i]->data); find=1;
}
else top--;
}
if (top>0&&!find)
{q=q->rchild;
 
tag[top-1]=1;
}
}
}
}

5．已知二叉树中的结点类型用 BinTreeNode 表示，被定义为：
struct BinTreeNode{
char data；
BinTreeNode    *leftChild，*rightChild；
}；
其中 data 为结点值域；leftChild 和 rightChild 分别为指向左、右孩子结点的指针域，根 据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。参数 BT 初始指向这 棵二叉树的根点。
int BtreeHeight（BinTreeNode *BT）；

答：算法如下
int BtreeHeight(BinTreeNode * BT)
{ int h1,h2,h; if（ BT==NULL）h=0；
else{
h1 = BTreeHeight（BT－>leftChild）； h2 = BTreeHeight（BT－>rightChild）； if（hl>h2）h=h1＋1；
else h=h2＋1；
}
return h;
}

6.设一棵二叉树以二叉链表为存储结构，结点结构为(lchild, data,rchild)，设计一个 算法将二叉树中所有结点的左，右子树相互交换。
解：
void exchange(BiTree bt)
{BiTree s； if(bt)
{s=bt->lchild;
bt->lchild=bt->rchild; bt-
>rchild=s; exchange(bt->lchild); exchange(bt->rchild);}
}

7.试写出复制一棵二叉树的算法。 解
：
 
BiTree    Copy(BiTree    t)//复制二叉树 t
{BiTree bt;
if (t==null) bt=null; else{
bt=(BiTree)malloc(sizeof(BiNode)); bt-
>data=t->data;
bt->lchild=Copy(t->lchild); bt->rchild=Copy(t-
>rchild);
}
return(bt);
}//结束 Copy

8．假设二叉树采用二叉链存储结构存储，试设计一个算法，输出从每个叶子结点到根结 点的路径。
解：
题目解析：采用 path 数组存放路径， pathlen 整数存放路径长度。递归模型如下： f(b,path,pathlen)：输出 path 值    当 b 为叶子结点 f(b,path,pathlen)：将 b->data 放入 path，pathlen++；    其他情况
f(b->lchild,path,pathlen)； f(b-
>rchild,path,pathlen)；
具体算法如下：
void Allpath(BTNode *b,ElemType path[],int pathlen)
//初始调用时 path 为空，pathlen 为 0
{
int i；
if (b!=NULL)
{ if (b->lchild==NULL&& b->rchild==NULL)    //*b 为叶子结点
{ printf(“%c 到根结点路径：%c”,b->data, b->data); for (i=pathlen-1;i>=0;i--)
printf (“%c”,path[i]); printf (“\n”);
}
else
{ path[pathlen]= b->data;    //将当前结点放入路径中 pathlen++;    //路径长度增 1
Allpath(b->lchild,path,pathlen); // 递 归 扫描 左子树 Allpath(b->rchild,path,pathlen); // 递 归扫描 右 子树 pathlen--;    //环境恢复
}
}
}

9．假设二叉树采用二叉链存储结构存储，试设计一个算法，输出该二叉树中第一条最长 的路径长度，并输出此路径上个结点的值。
 
解：
题目解析：采用 path 数组保存扫描到当前结点的路径， pathlen 保存扫描到当前结点的 路 径长度，longpath 数组保存最长的路径， longpathlen 保存最长路径长度。当 b 为空时， 表 示当前扫描的一个分支已扫描完毕，将 pathlen 与 longpathlen 进行比较，将较长路径 及路 径长度分别保存在 longpath 和 longpathlen 中。
具体算法如下：
void Longpath(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int longpathlen)
{
int i；
if (b==NULL)
{ if (pathlen>longpathlen)    // 若当前路径更长，将路径保存在
longpath 中
{ for (i=pathlen-1;i>=0;i--) longpath[i]=path[i];