数据结构实验报告6-二叉树与哈夫曼树

《数据结构与算法》实验指导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