严蔚敏++数据结构习题集答案(4)

p=rear; /* p指向下一层最右边的结点*/ }

} /* endwhile*/ return(flag); }

6.25 以二叉链表为存储结构，写一算法交换各结点的左右子树。 解：

思想：借助栈来进行对换。

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; } }

} /*endwhile*/ } /*endif*/

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); printf(“\\nThe width is:%d”,l); Swap(root);

Printf(“\\nThe swapTree is:”); Inorder(root); } 6．26 以二叉表为存储结构，写一个拷贝二叉表的算法哦（BinTree root,BinTree *newroot）,其中新树的结点是动态申请的，为什么newroot要说明为BinTree形指针的指针？ 解：

CopyTree(BinTree root,BinTree *(newroot)) }

if(root!=Null) {

*newroot=(BinTree *)malloc(sizeof(BinTree)); (*newroot)->data=root->data;

CopyTree(root->lchild,&(*newroot)->lchild); CopyTree(root->rchild,&(*newroot)->rchild); Inorder(*newroot); }

else return(Null); }

main() {

BinTree *newroot; int I,j,k,l; printf(“\\n”);

root=CreateBinTree(); Inorder(root); Printf(“\\n”); /*Swap(root);*/ &(*newroot)=Null;

CopyTree(root,&*newroot); }

6．27 以二叉树表为存储结构，分别写处在二叉树中查找值为x的结点在树中层数的算法。 解：

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); }

6.28一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。 解：

思想：采用栈，先让跟结点如栈，然后退栈，如有左右孩子，则先让右孩子如栈，然后左孩子如栈，如此反复实现前序遍历。

typedef struct {

int data[100];

int top; }seqstack; seqstack *s;

Perorder(char a[],int n) {

int i=1,count=1; s->top=-1;

if(n==0)return(0); else {

if(I<=n) {

s->top++;

s->data[s->top]=a[I]; }

while(count

printf(“%c”,s->data[s->top]); count++; s->top--;

if(s->data[s->top]);==a[i]) { /*若栈顶结点为a[i]结点，则退栈，保证父结点比孩子结点先退栈 */ printf(“%c”,s->data[s->top]); count++; s->top--; }

if((2*i+1)

i=2*i; s->top++;

s->data[s->top]=a[i+1]; s->top++;

s->data[s->top]=a[i];

}

else if(a*i

{

i=2*i; s->top++;

s->data[s->top]=a[i]; }

else if(i/2%2==1)i=i/2/2+1;

/*父结点没有右兄弟，回到祖父结点大右兄弟*/ else i=i/2+1; /*回到父结点的右兄弟*/ } } } main() {

char A[]=“kognwyuvb”; int n=strlen(A);

s=(seqstack *)malloc(sizeof(seqstack)); printf(“\\n”); Perorder(A,n); }

6．29 以二叉树表为存储结构，写一算法对二叉树进行层次遍历（定义见习题6.13）。提示：应使用队列来保存各层的结点。 解：

void TransLevel(BinTree *T) {

int front=0,rear=0; int p;

if(T!=Null) {

printf(“%c”,T->data); q[rear]=T; rear++; }

while(front

T=q[front]; Front++;

if(T->lchild!=Null) {

printf(“%c”,T->lchild->data); q[rear]=T->lchild; rear++;

}

if(T->rchild!=Null) {

printf(“%c”,T->rchild->dara); q[rear]=T->rchild;

rear++; } }

}

main() {

printf(“\\n”);

root=CreateBinTree(); Inorder(root); Printf(“\\n”); TransLevel(root); }

6．30 以二叉树表为存储结构，写一算法用括号形式（keyLT,RT）打印二叉树，其中key是根结点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一给结点x的树打印形式是x，而不应是（x，，）d的形式。 解：

viod Print(BinTree T) /*哟感括号形式打印二叉树*/ {

if(T!=Null) {

if(T->lchild==Null&&T->rchild==Null) /*只有根结点*/ printf(“%c”,T->data);

else /*T->lchild!=Null||T->rchild!=Null*/ {

printf(“(”);

printf(“%c”,T->data);

if(T->lchild->lchild==Null&&T->lchild->rchild==Null) printf(“)”); Print(T->lchild);

if(T->rchild!=Nulll)printf(“,”); printf(“)”); printf(“)”); } } } main() {

printf(“\\n”);

root=CreateBinTree(); Inorder(root); printf(“\\n”); Print(root); }

6.31以线索链表为存储结构，分别写出在前序线索树中查找给定结点*p的后继，以及在后序线索树中查找*p的后序前趋的算法。 解：

① 找结点p的前序后继

BinTheNode * PreorderSuccessor(BinThrNode *p) {

BinThrNode *q;

if(p->rtag==T …… 此处隐藏：1778字，全部文档内容请下载后查看。喜欢就下载吧 ……