数据结构单元练习7(7)

typedef struct BT

{ datatype data; // 定义结点 BT *lchild; BT *rchild; C BF A D G }BT;

E int BTD(BT *T) { int ldep,rdep; if (T==NULL) return 0; else

{ ldep= BTD (T->lchild); rdep= BTD (T->rchild); if (ldep>rdep) return ldep+1; else

return rdep+1;

} }

解：4 （求二叉树深度）

3．二叉树的结构如图所示，试写出执行下列算法后，少？

count的值为多typedef struct BT

{ datatype data; // 定义结点B BT *lchild; BT *rchild; }BT;

int count=0; void Leafnum(BT *T) {

if (T!=NULL)

C E A D F G { if(T->lchild==NULL && T->rchild==NULL) count++;

Leafnum(T->lchild); Leafnum(T->rchild); } }

解：3 （求叶结点数） (2，3，4改为程序填空)

二． 程序填空

1．填空完成二叉树按层次遍历的程序

typedef struct BT

{ datatype data; // 定义结点 BT *lchild;

BT *rchild; }BT;

void Levelorder(BT *T) // 层次遍历 { int i,j; BT *q[100],*p; p=T;

if ( p!=NULL ) { i=1;q[i]=p;j=2; } while (i!=j)

{ p=q[i];

cout<< p->data ;

if ( p->lchild!=NULL ) { q[j]= p->lchild ;j++;} if (p->rchild!=NULL)

{ q[j]= p->rchild ;j++; } i++; }

}

}

三． 应用题

1． 将下列二叉树转换为森林。 A B C D E F G H I J K 解： A B E D I H

C G F J K 2． 画 解：

D G B H J K A E C F 出和下列二叉树相应的森林。

I M （根右边的子树肯定是森林，而孩子结点的右子树均为兄弟）

3． 某二叉树的结点数据采用顺序存储，其结构如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20