}

4．前序输出二叉树中各结点及其结点所在的层号。

void preorderlevel (BT t,int h) // t的层数为h { if (t!=NULL)

{ printf (“%d,%d”,t->data, h); preorderlevel (t->lchild, h+1); preorderlevel (t->rchild, h+1);

} }

5. 求二叉树的宽度

思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 int Width(BT *T)

{ int front=-1,rear=-1; // 队列初始化 int flag=0,count=0,p;

// p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值

if (T!=NULL) { rear++; q[rear]=T; flag=1; p=rear; }

while (front

if (T->lchild!=NULL) { rear++;

q[rear]=T->lchild; count++; }

if (T->rchild!=NULL) { rear++;

q[rear]=T->rchild; count++; }

if (front==p) { if (flag

flag=count;

count=0;

p=rear; }

}

13

// 当前层已遍历完毕

// p指向下一层最右边的结点

// endwhile

return(flag); }

．解：借助栈来进行对换。

Swap(BinTree*T)

{ BinTree *stack[100], *temp; int top=-1; root=T;

if (T!=NULL)

{

top++;

stack[top]=T; while(top>-1)

{ T=stack[top]; top--;

if (T->child!=NULL||T->rchild!=NULL)

{ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; }

if (T->lchild!=NULL) { top++;

stack[top]=T->lchild; }

if (T->rchild!=NULL) { top++;

stack[top]=T->rchild; }

} } }

main()

{ int I,j,k,l; printf(“\\n”);

root=CreateBinTree(); Inorder (root); i=CountNode (root); j=CountLeafs (root); k=Depth (root); l=Width (root);

printf(“\\nThe Node ’s Number:%d”,i); printf(“\\nThe Leafs’s Number:%d”,j); printf(“\\nThe Depth is:%d”,k);

14

交换结点的左右指针 6 //

printf(“\\nThe width is:%d”,l); Swap(root);

Printf(“\\nThe swapTree is:”); Inorder(root); }

7．解：

int h=-1,lh=1,count=0;charx=’c’; // 赋初值

Level (BinTree T,int h,int lh) // 求X结点在树只的层树 { if (T==Null)

h=0; else

if (T->data==x)

{ h=lh; count=h;} else

{ h++;

Level(T->lchild,h,lh); if (h==-1)

Level(T->rchild,h,lh);

} } main()

{ BinTree *(*newroot); Printf(“\\n”);

Root=CreateBinTree(); Inorder(root); Printf(“\\n”); Level(root,h,lh); Printf(“%d”,count); }

15

模拟考题

一． 读程序，写出运行结果

1．二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。

（用大写的英文字母表示，字母之间不要任何间隔符号，最后一个字母后面也不要间隔符号）

typedef struct BT A { datatype data; BT *lchild; BD BT *rchild; }BT; G C F void Preorder(BT *T) { if (T!=NULL) E { cout<< T->data;

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

解：ABCEDFG 先序遍历

2．二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。

typedef struct BT

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

int BTD(BT *T) G C F { int ldep,rdep; if (T==NULL) E 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

A { datatype data; // 定义结点

BT *lchild;

BD BT *rchild;

16

C E F G