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

{ 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

{ front++; T=q[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; 层最右边的结点 }

} return(flag); }

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

Swap(BinTree*T)

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

// 当前层已遍历指向下一 // endwhile // p