《数据结构与算法》实验指导V2016 }/*PreOrder*/
/*中序遍历二叉树，补充递归算法*/ void InOrder(BiTree p) {
if(p!=NULL) { InOrder (p->lchild);
printf(\ InOrder (p->rchild); }
}/*InOrder*/
/*后序遍历二叉树，补充递归算法*/ void PostOrder(BiTree p) {
if(p!=NULL)
{ PostOrder (p->lchild):
PostOrder (p->rchild); printf(\ }
}/*PostOrder*/
/*先序遍历的非递归算法*/ void RPreorder(BiTree p) {
BiTree stack[MAX],q; int top=0,i;
for(i=0; i while(q!=NULL) { printf(\ if(q->rchild!=NULL) _____stack[top++]=q->rchild_____; /*右指针进栈*/ if(q->lchild!=NULL) q=q->lchild; /*顺着左指针继续向下*/ else if(top>0) q=stack[--top]; /*左子树访问完，出栈继续访问右子树结点*/ else q=NULL; } }/*RPreorder*/ /*中序遍历的非递归算法*/ 常熟理工学院计算机科学与工程学院 5 《数据结构与算法》实验指导V2016 void RInorder(BiTree p) { BiTree stack[MAX],q; int top=0,i; for(i=0; i while(q!=NULL) { if(q->rchild!=NULL) _____stack[top++]=q->rchild_____; /*右指针进栈*/ if(q->lchild==NULL) printf(\else stack[top++]=q->lchild; /*左指针进栈*/ q=q->lchild; /*顺着左指针继续向下*/ else if(top>0) q=stack[--top]; /*左子树访问完，出栈继续访问右子树结点*/ else q=NULL; } }/*RInorder*/ /*后序遍历的非递归算法*/ void RPostorder(BiTree p) { BiTree stack[MAX],q; int i,top=0,flag[MAX]; for(i=0; i stack[i]=NULL; flag[i]=0; } q=p; while(q!=NULL||top!=0) { if(q!=NULL) /*当前结点进栈，先遍历其左子树*/ { stack[top]=q; flag[top]=0; top++; q=q->lchild; } else { 常熟理工学院计算机科学与工程学院 6 《数据结构与算法》实验指导V2016 while(top) { if(flag[top-1]==0) /*遍历结点的右子树*/ { q=stack[top-1]; q=q->rchild; flag[top-1]=1; break; } else { q=stack[--top]; printf(\遍历结点*/ } } } if(top==0) break; } }/*RPostorder*/ /*求二叉树的深度算法，补充递归算法*/ int depth(BiTree t) { int rd,ld; if(!t) return 0; else { rd=depth(B->lchild); ld=depth(B->rchild); if(rd>ld) return ld+1; else return rd+1; } }/*depth*/ /*建立结点*/ BiTree gettreenode(char x,BiTree lptr,BiTree rptr) { BiTree t; t=(BiTree)malloc(sizeof(struct BTNode)); t-> data = x; 常熟理工学院计算机科学与工程学院 7 《数据结构与算法》实验指导V2016 t->lchild = lptr; t->rchild = rptr; return(t); }/*gettreenode*/ /*以后序遍历的方式递归复制二叉树*/ BiTree copytree(BiTree t) { BiTree newlptr,newrptr,newnode; if(t==NULL) return NULL; if(t->lchild!=NULL) newlptr = copytree(t->lchild); else newlptr = NULL; if(t->rchild!=NULL) newrptr = copytree(t->rchild); else newrptr = NULL; newnode = gettreenode(t->data, newlptr, newrptr); return(newnode); }/*copytree*/ /*交换二叉树的结点的左右孩子*/ BiTree swap(BiTree b) { BiTree t,t1,t2; if(b==NULL) t=NULL; else { t=(BiTree)malloc(sizeof(struct BTNode)); t->data=b->data; t1=swap(b->lchild); /*递归交换左子树上的结点*/ t2=swap(b->rchild); /*递归交换右子树上的结点*/ t->lchild=t2; /*交换根t的左右子树*/ t->rchild=t1; } return(t); }/*swap*/ /*利用循环队列实现层次遍历*/ void ccOrder(BiTree t) { }/*ccOrder*/ 常熟理工学院计算机科学与工程学院 8
