数据结构课后习题答案（修订版）(5)

/*判断该数组里面的数据是否由小到大排列，若是则其为一棵二叉排序树*/ void Test(int order[ ]) { int j; int k=sizeof(order)/sizeof(order[0]);/*计算数组的长度*/ for(j=0;jorder[j+1]) break; }

if(j=k-1) printf(“该二叉树为二叉排序树\\n”); else printf(“该二叉树不是二叉排序树\\n”); }

4.2. 具体算法如下：

typedef struct BtreeNode /*定义一个二叉树的结点*/ {

int data;

struct BTreeNode *lchild; struct BTreeNode *rchild; } *Btree

/*计算二叉树高度的递归算法如下*/ int depth（Btree T） { int d,p=0; /*p记录该二叉树的高度，初始值等于0*/ if（T= =NULL）return p; /*空二叉树的高度为0*/ else { d=depth（T->lchild）; /*考虑该二叉树的左子树，递归调用*/ if（d>p）p=d; /*p始终记录最大的子树高度*/ d=depth（T->rchild）;/*考虑该二叉树的右子树，递归调用*/ if （d>p）p=d; /*p始终记录最大的子树高度*/ }

return （p+1）; /*子树的最大高度加1为返回树的高度*/

}

4.4. 算法如下：

#define TreeSize 100

#define StackSize TreeSize/2 void exit(int); typedef struct {

char nodes[TreeSize]; int num; }BTree;

typedef struct

{

int s[StackSize]; int top; }SeqStack;

void InitStack(SeqStack *s) {s->top=-1;}

int StackEmpty(SeqStack*s) {return s->top= = -1;}

void push(SeqStack *s,int x) {

if(s->top>=StackSize){

printf(“Error:the stack is overflow!\\n”); exit (-2); }

s->s[++s->top]=x; }

int pop(SeqStack *s) {

if(StackEmpty(s){

printf(“Error:the stack is overflow!\\n”); exit(-2); }

return s->s[s->top]; }

void preorders(BTree *tree) {

int i=1; SeqStack s; InitStack(&s); If(tree->num>0) do { printf(“%c”,tree->nodes[i]); while(i*2<=tree->num){ if(i*2+1<=tree->num)push(&s,i*2+1); i*=2; printf(“%c”,tree->nodes[i]; } if(!StackEmpty(&s))i=pop($s); else break; }while(2); }

4.5. 递归算法如下：下面的num和leaf函数分别计算二叉树结点总数和叶子总数。

typedef char datatype; typedef struct node{ datatype d;

struct node*lchild,*rchild; }BinNode;

typedef BinNode *BinTree; int num（BinTree p） {

if（！p）return 0;

else return 1+num（p->lchild）+num（p->rchild）; }

int leaf（BinTree p） {

if（！p）return 0; else { if（p->lchild= =NULL&&p->rchild= =NULL）return 1; else return（ leaf（p->lchild）+leaf（p->rchild）; } }

4.6. 参考答案：假设用于通信的电文与出现的概率依次为：a（7）,b（19）,c（2）,d（6）,e（32）,f（3）,g（21）,h（10），则最终得到的哈夫曼编码依次为：a（0010）,b（10）,c（00000）,d（0001）,e（01）,f（00001）,g（11）,h（0011）；具体实现可以参考本章算法7.5。

37.计算二叉树宽度的算法如下（计算二叉树高度的算法可以参考本章习题15）：

typedef struct{ int front,rear; int count;

BinNode*datas[QueueSize]; }CirQueue;

void InitQueue(CirQueue*Q) {Q->front=Q->rear=Q->count=0;} int QueueEmpty(CirQueue*Q) {return Q->front= =0;}

int QueueFull(CirQueue*Q) {return Q->count= =QueueSize;}

void EnQueue(CirQueue *Q,BinNode*p) {

if(QueueFull(Q)) {

print(“Error:the queue is full!\\n”); exit(-2); }

Q->count++;

Q->data[Q->rear]=p;

Q->rear=(Q->rear+1)%QueueSize; }

BinNode*DeQueue(CirQueue*Q) {

BinQueue*t;

If(QueueEmpty(Q){

Printf(“Error:the queue is empty!\\n”); Exit(-2); }

t=Q->data[Q->front]; Q->count--;

Q->front=(Q->front+1)%QueueSize; Return t; }

int width(BinNode *p) {

CirQueue q; BinNode*t;

int max-width=0,width=0; InitQueue(&q,p); if(p) {

EnQueue(&q,p);

EnQueue(&q,NULL); While(!QueueEmpty(&q)) {

t=DeQueue(&q); if(t) {

width++;

if(t->lchild)EnQueue(&q,t->lchild); if(t->rchild)EnQueue(&q,t->rchild); } else {

if(!QueueEmpty(&q))EnQueue(&q,NULL); if(width>max-width=width; width=0; } } }

return max-width; }

习题八答案

1．答：（1）√（2）╳（3）√（4）╳ (5)╳ (6)√ (7)√ (8)√ (9)╳ (10)╳ (11)√ (12)√ (13)√ 2．答：（1）D（2）B（3）B（4）B（5）A（6）B（7）D（8）C（9）C、D（10）D（11）A

5．答：① ID(A)=1 OD(A)=3 ID(B)=2 OD(B)=1 ID(C)=2 OD(C)=1 ID(D)=2 OD(D)=1 ②二个强连通分量：

○A

B ○D ○ 3 ○A ○C ○

B ○D ○

C ○

3.(2)．答：①邻接矩阵

0 1 1 1 0 0 1 0 A= 1 0 0 1

0 1 0 0

②

③

④

0 1 2 3 0 1 2 3 A B C D A B C D 3 2 3 Λ2 0 0 Λ1 Λ ΛΛ 1 2 0 1 2 3 A B C D 3 1 2 0 1 2 3 3 2 0 1 ΛΛΛ 0 2 Λ 0 0 Λ 0 1 Λ Λ Λ Λ Λ Λ