数据结构第六章一二次作业.doc

上机题(1)编写完整程序,用先序遍历法建立二叉树的二叉链表存储结构。输出该二叉树的先、中、后序遍历结点访问次序以及层次遍历结点访问次序。(建议结点数据域类型为char)//:Definestheentrypointfortheconsoleapplication.//#include""#include<>#include<>typedefstructnode{chardata;structnode*lchild,*rchild;}*BiT,BiTNode;BiTcrtBT(){charch;BiTbt;ch=getchar();if(ch=='#')returnNULL;bt=newBiTNode();bt->data=ch;bt->lchild=crtBT();bt->rchild=crtBT();returnbt;}voidpreorder(BiTbt){if(bt){printf("%c",bt->data);preorder(bt->lchild);preorder(bt->rchild);}//printf("\n");}voidmidorder(BiTbt){if(bt){midorder(bt->lchild);printf("%c",bt->data);midorder(bt->rchild);}//printf("\n");}voidlasorder(BiTbt){if(bt){lasorder(bt->lchild);lasorder(bt->rchild);printf("%c",bt->data);}//printf("\n");}intmain(intargc,char*argv[]){BiTbt;bt=crtBT();preorder(bt);printf("\n");midorder(bt);printf("\n");lasorder(bt);printf("\n");return0;}(2)从键盘输入n个数据建立n元完全二叉树顺序存储结构。实现该完全二叉树的先、中、后序遍历。#include""#include<>#include<>voidpreorder(intj,inti,char*s){ if(j>i)return; printf("%c",s[j]);preorder(j*2+1,i,s);preorder(j*2+2,i,s);}voidmidorder(intj,inti,char*s){if(j>i)return;preorder(j*2+1,i,s);printf("%c",s[j]);preorder(j*2+2,i,s);}voidlasorder(intj,inti,char*s){if(j>i)return;preorder(j*2+1,i,s);preorder(j*2+2,i,s); printf("%c",s[j]);}intmain(intargc,char*argv[]){inti=0;char*bt; chars[100]; scanf("%s",s); bt=s; while(s[i]!=0) { i++; } //printf("%d\n",i);preorder(0,i,bt); printf("\n"); midorder(0,i,bt); printf("\n"); lasorder(0,i,bt); printf("\n");return0;}算法(1)已知二叉树(二叉链表)根结点指针为bt,求该二叉树中的叶子数目。intpreorder(BiTbt){ intk=0;if(bt){if(!bt->lchild&&!bt->rchild)k++;preorder(bt->lchild);preorder(bt->rchild);} returnk;}(2)已知某二叉树(三叉链表)的根结点地址root,该树中各结点的左、右儿子指针域已正确填充,写一个算法将所有结点的双亲指针域正确填充。voidpreorder(BiTbt){ if(bt==root)return;if(bt){ bt->lchild->parent=bt;bt->rchild->parent=bt;preorder(bt->lchild);preorder(bt->rchild);}}(3)已知某二叉树(二叉链表)的根结点指针bt。编写算法,将该二叉树中所有结点的左右子树互换。voidpreorder(BiTbt){ charc;if(bt){ c=bt->lchild; bt->lchild=bt->rchild; bt->rchild=c;preorder(bt