数据结构以及应用算法教程参考答案（10）第六章

关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 6.37 解： // 先序遍历的非递归算法 Status POTraverse(BiTree& T,Status (*Visit)(TElemType e)) { BiTree p; Stack s; InitStack(s); p=T; while(p||!StackEmpty(s)){ if§{ // 如果根指针不空，访问根结点， // 右指针域压栈，继续遍历左子树 if(!Visit(p->data)) return ERROR; Push(s,p->rchild); p=p->lchild; } // 根指针已空，本子树已遍历完毕， // 退栈返回上一层，继续遍历未曾访问的结点 else Pop(s,p); } return OK; } 6.41 解： // 求位于先序序列中第k个位置的结点的值， // e中存放结点的返回值，i为计数器 Status PONodeK(TElemType& e,int& i,int k,BiTree& T) { if(T){ i++; if(i==k) e=T->data; else{ PONodeK(e,i,k,T->lchild); PONodeK(e,i,k,T->rchild); } } return OK; } 6.42 解： // 求二叉树中叶子结点的数目 Status POLeafNodeNum(int& i,BiTree& T) { if(T){ if(!T->lchild && !T->rchild) i++; POLeafNodeNum(i,T->lchild); POLeafNodeNum(i,T->rchild); } return OK; } 6.43 解： // 按先序交换二叉树的左右子树 Status ExchangeBiTree(BiTree& T) { BiTree p; if(T){ p=T->lchild; T->lchild=T->rchild; T->rchild=p; ExchangeBiTree(T->lchild); ExchangeBiTree(T->rchild); } return OK; } 6.44 解： // 求二叉树中以元素值为x的结点为根的子树的深度 Status ChildTreeDepth(BiTree& T,TElemType x,int& depth) { BiTree T1; if(PreOrderLocate(T,x,T1)){ depth=BiTDepth(T1); return OK; } else return ERROR; }

// 按先序在树中查找根为x的子树，T1为指向子树根的指针 Status PreOrderLocate(BiTree& T,TElemType x,BiTree& T1) { if(T){ if(T->data==x){ T1=T; return OK; } else{ if(PreOrderLocate(T->lchild,x,T1)) return OK; else{ if(PreOrderLocate(T->rchild,x,T1)) return OK; else return ERROR; } } } else return ERROR; }

// 求二叉树的深度 int BiTDepth(BiTree& T) { int ldep,rdep; if(!T) return 0; else{ ldep=BiTDepth(T->lchild)+1; rdep=BiTDepth(T->rchild)+1; return ldep>rdep?ldep:rdep; } } 6.45 解： // 删除以元素值为x的结点为根的子树 Status DelChildTree(BiTree& T,TElemType x) { if(T){ if(T->data==x){ DelBTree(T); T=NULL; return OK; } else{ if(DelChildTree(T->lchild,x)) return OK; else{ if(DelChildTree(T->rchild,x)) return OK; else return ERROR; } } } else return ERROR; } // 删除二叉树 Status DelBTree(BiTree& T) { if(T){ DelBTree(T->lchild); DelBTree(T->rchild); delete T; return OK; } else return ERROR; } 6.46 解： // 复制一棵二叉树 Status CopyBiTree(BiTree& T,BiTree& T1) { BiTree p; if(T){ p=new BiTNode; if(!p) return ERROR; p->data=T->data; T1=p; CopyBiTree(T->lchild,T1->lchild); CopyBiTree(T->rchild,T1->rchild); } else{ T1=T; } return OK; } 6.47 解： typedef BiTree QElemType; #include “c:\Yin\include\Queue.h” Status LevelOrderTraverse(BiTree& T,Status (*Visit)(TElemType e)) { QElemType p; Queue q; InitQueue(q);

if(T) EnQueue(q,T); while(!QueueEmpty(q)){ DeQueue(q,p); Visit(p->data); if(p->lchild) EnQueue(q,p->lchild); if(p->rchild) EnQueue(q,p->rchild); } return OK;

} 6.48 解： // 在二叉树T中求结点p和q的共同最小祖先e Status MinComAncst(BiTree& T,TElemType& e,TElemType *p,TElemType *q) { if(!T) return ERROR; BiTree T1,T2,pt=NULL; if(!CopyBiTree(T,T1)) return ERROR; if(!CopyBiTree(T,T2)) return ERROR; if(!PathTree(T1,p)) return ERROR;// 求根结点到结点p的路径树T1 else ShowBiTree(T1); cout<<endl; if(!PathTree(T2,q)) return ERROR;// 求根结点到结点q的路径树T2 else ShowBiTree(T2); cout<<endl; while(T1 && T2 && T1->dataT2->data){ pt=T1; if(T1->lchild){ T1=T1->lchild; T2=T2->lchild; } else{ if(T1->rchild){ T1=T1->rchild; T2=T2->rchild; } } } if(!pt) return ERROR; else{ e=pt->data; return OK; } } // 在二叉树T中求根到结点p的路径树，该操作将剪去除路径之外的所有分支 Status PathTree(BiTree& T,TElemType *p) { if(!T || !p) return ERROR; if(T->data*p){// 找到目标，删除目标的左右子树 if(T->lchild) DelBiTree(T->lchild); if(T->rchild) DelBiTree(T->rchild); return OK; } else{// 没找到目标，继续递归查找 if(PathTree(T->lchild,p)){// 目标在左子树中，删除右子树 if(T->rchild) DelBiTree(T->rchild); return OK; } else if(PathTree(T->rchild,p)){// 目标在右子树中，删除左子树 if(T->lchild) DelBiTree(T->lchild); return OK; } else return ERROR;// 找不到目标 } } 6.49 解： Status CompleteBiTree(BiTree& T) { int d; if(T){ d=BiTDepth(T->lchild)-BiTDepth(T->rchild); if(d<0 || d>1) return ERROR; else{ if(CompleteBiTree(T->lchild) && CompleteBiTree(T->rchild)) return OK; else return ERROR; } } else return OK; } 6.51 解： Status ShowBiTExpress(BiTree& T) { if(T){ if(T->lchild){ if(Low(T->lchild->data,T->data)){ cout<<’(’; ShowBiTExpress(T->lchild); cout<<’)’; } else ShowBiTExpress(T->lchild); } cout<data; if(T->rchild){ if(Low(T->rchild->data,T->data)){ cout<<’(’; ShowBiTExpress(T->rchild); cout<<’)’; } else ShowBiTExpress(T->rchild); } } return OK; }

Status Low(char a,char b) { if((a==’+’ || a==’-’) && (b==’*’ || b==’/’)) return TRUE; else return FALSE; } 6．52 解： int BiTreeThrive(BiTree& T) { int i,d,nn[20]; d=BiTDepth(T); BiTree p=T; Stack s1,s2; InitStack(s1); InitStack(s2); for(i=0;i<20;i++){ nn[i]=0; // 每层结点个数 }

if(p) Push(s1,p); else return 0; for(i=0;i<d;i++){ if(!StackEmpty(s1) && StackEmpty(s2)){ while(!StackEmpty(s1)){ Pop(s1,p); nn[i]++;// s1中存放第i层的结点 if(p->lchild) Push(s2,p->lchild);//s2中存放第i+1层结点 if(p->rchild) Push(s2,p->rchild); } } else{ if(StackEmpty(s1) && !StackEmpty(s2)){ while(!StackEmpty(s2)){ Pop(s2,p); nn[i]++; if(p->lchild) Push(s1,p->lchild); if(p->rchild) Push(s1,p->rchild); } } } } int max=nn[0]; for(i=0;i<d;i++) if(max<nn[i]) max=nn[i]; return max*d;

} 6.53 解： // 所有从根到叶子最长路径树 Status MaxPathBiTree(BiTree& T) { if(T){ if(BiTDepth(T)-BiTDepth(T->lchild)!=1) DelBiTree(T->lchild); else MaxPathBiTree(T->lchild); if(BiTDepth(T)-BiTDepth(T->rchild)!=1) DelBiTree(T->rchild); else MaxPathBiTree(T->rchild); } return OK; } // 从根到叶子最长路径中最左方的路径树 Status LMaxPathBiTree(BiTree& T) { if(T){ if(BiTDepth(T)-BiTDepth(T->lchild)==1){ DelBiTree(T->rchild); LMaxPathBiTree(T->lchild); } else{ DelBiTree(T->lchild); if(BiTDepth(T)-BiTDepth(T->rchild)1) LMaxPathBiTree(T->rchild); else DelBiTree(T->rchild); } } return OK; } 6.54 解： // 根据完全二叉顺序树创建完全二叉链表树 Status CreateCompleteBiTree(SqList& ST,BiTree& LT) { BiTree p; int i=0,len; if(ST.Length0) return OK; p=new BiTNode; if(!p) return ERROR; p->data=ST.Get(i); p->lchild=NULL; p->rchild=NULL; LT=p;

Queue q; InitQueue(q); EnQueue(q,p); len=ST.Length(); while(!QueueEmpty(q)&&i<len-1){ DeQueue(q,p); if(i<len-1 && i%2==0){ p->lchild=new BiTNode; if(!p->lchild) return ERROR; p->lchild->data=ST.Get(++i); p->lchild->lchild=NULL; p->lchild->rchild=NULL; EnQueue(q,p->lchild); } if(i<len-1 && i%2==1){ p->rchild=new BiTNode; if(!p->rchild) return ERROR; p->rchild->data=ST.Get(++i); p->rchild->lchild=NULL; p->rchild->rchild=NULL; EnQueue(q,p->rchild); } } return OK;

} 6.55 解： Status PreOrderTraverse(BiTree& T) { if(T){ T->DescNum=DescendNum(T); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } return OK; }

int DescendNum(BiTree& T) { if(!T) return 0; if(!T->lchild){ if(!T->rchild) return 0; else return DescendNum(T->rchild)+1; } else{ if(!T->rchild) return DescendNum(T->lchild)+1; else return DescendNum(T->rchild)+DescendNum(T->lchild)+2; } } 6.56 解： 先对二叉树T进行先序线索，得到先序线索二叉树Thrt。然后再进行查找。 // 先序线索二叉树算法 Status PreOrderThreading(BiThrTree& Thrt,BiThrTree& T) { BiThrTree pre; Thrt=new BiThrNode; // 为线索二叉树建立头结点 if(!Thrt) exit(OVERFLOW); Thrt->LTag=Thread; Thrt->RTag=Link; Thrt->lchild=Thrt;// 左子树回指 if(!T) Thrt->rchild=Thrt;// 若二叉树空，右子树回指 else{ Thrt->rchild=T; pre=Thrt; PreThreading(T,pre); // 先序遍历进行先序线索化 pre->rchild=Thrt; // 最后一个结点线索化 pre->RTag=Thread; Thrt->lchild=pre; } return OK; }

Status PreThreading(BiThrTree& T,BiThrTree& pre) { if(T){ if(!T->lchild){ T->LTag=Thread; T->lchild=pre; } if(pre && !pre->rchild){ pre->RTag=Thread; pre->rchild=T; } pre=T; if(T->LTagLink) PreThreading(T->lchild,pre); if(T->RTagLink) PreThreading(T->rchild,pre); } return OK; }

// 从二叉线索树上任一结点q开始查找结点p。 // 如果找到，将p的后继结点指针存于q中，返回TRUE；否则返回FALSE Status FindNextInBiThrTree(BiThrTree& q,TElemType *p) { BiThrTree pt=q; if(!pt) return FALSE; if(pt->data==*p){ if(pt->LTagLink) q=pt->lchild; else q=pt->rchild; return OK; } pt=q->rchild; while(pt!=q && pt->data!=*p){ if(pt->LTagLink) pt=pt->lchild; else pt=pt->rchild; } if(ptq) return FALSE; if(pt->data*p){ if(pt->LTag==Link) q=pt->lchild; else q=pt->rchild; } return OK; } 6.57 解： Status PostOrderThreading(BiThrTree& T,BiThrTree& pre);//首先建立后序线索树 Status FindNextInBiThrTree(BiThrTree& q,TElemType *p);//再进行查找

// 后序线索二叉树的算法 Status PostOrderThreading(BiThrTree& Thrt,BiThrTree& T) { BiThrTree pre; Thrt=new BiThrNode; // 为线索二叉树建立头结点 if(!Thrt) exit(OVERFLOW); Thrt->LTag=Link; Thrt->RTag=Thread; Thrt->rchild=Thrt;// 右子树回指 if(!T) Thrt->lchild=Thrt;// 若二叉树空，左子树回指 else{ Thrt->lchild=T; pre=Thrt; PostThreading(T,pre); // 后序遍历进行后序线索化 pre->rchild=Thrt;// 最后一个结点线索化 pre->RTag=Thread; Thrt->rchild=pre; } return OK; }

Status PostThreading(BiThrTree& T,BiThrTree& pre) { if(T){ if(T->LTagLink) PostThreading(T->lchild,pre); if(T->RTagLink) PostThreading(T->rchild,pre); if(!T->lchild){ T->LTag=Thread; T->lchild=pre; } if(pre && !pre->rchild){ pre->RTag=Thread; pre->rchild=T; } pre=T; } return OK; } 6.58 解： typedef char TElemType; typedef struct CSNode{ TElemType data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree; // 建立树的二叉链表表示 Status CreateTree(CSTree& T) { char ch; cout<<“输入结点的值(一个字符，’@'表示空树)”; cin>>ch; if(ch==’@’){ T=NULL; } else{ T=new CSNode; if(!T) return ERROR; T->data=ch; CreateTree(T->firstchild); CreateTree(T->nextsibling); } return OK; } // 输出树的各边 Status ShowTree(CSTree& T,CSTree& Father) { if(T && Father) cout<<"("<data<<","<data<<")"; if(T->firstchild) ShowTree(T->firstchild,T); if(T->nextsibling) ShowTree(T->nextsibling,Father); return OK; } 6.60 解： int LeafNum(CSTree& T) { if(T){ if(!T->firstchild) return 1+LeafNum(T->nextsibling); else return LeafNum(T->firstchild)+LeafNum(T->nextsibling); } else return 0; } 6.61 解： int DegreeNum(CSTree& T) { int d,dl,dr; if(T){ if(!T->firstchild) d=0; else d=1+RSiblingNum(T->firstchild); dl=DegreeNum(T->firstchild); dr=DegreeNum(T->nextsibling); return Max(d,dl,dr); // 三数中求最大者 } else return 0; } // 返回当前结点的兄弟数 int RSiblingNum(CSTree& T) { int i=0; while(T->nextsibling){ i++; T=T->nextsibling; } return i; } 6.62 解： // 树的深度 int Depth(CSTree& T) { int d1,d2; if(T){ d1=1+Depth(T->firstchild); d2=Depth(T->nextsibling); return d1>d2?d1:d2; } else return 0; }