资源描述:
《数据结构第六章一二次作业》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、上机题(1)编写完整程序,用先序遍历法建立二叉树的二叉链表存储结构。输出该二叉树的先、中、后序遍历结点访问次序以及层次遍历结点访问次序。(建议结点数据域类型为char)//erchashu.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include#includetypedefstructnode{chardata;structnode*lchild,*rchild;}*BiT,BiTN
2、ode;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("");}voidmidorder(Bi
3、Tbt){if(bt){midorder(bt->lchild);printf("%c",bt->data);midorder(bt->rchild);}//printf("");}voidlasorder(BiTbt){if(bt){lasorder(bt->lchild);lasorder(bt->rchild);printf("%c",bt->data);}//printf("");}intmain(intargc,char*argv[]){BiTbt;bt=crtBT();preorder(bt);pr
4、intf("");midorder(bt);printf("");lasorder(bt);printf("");return0;}(2)从键盘输入n个数据建立n元完全二叉树顺序存储结构。实现该完全二叉树的先、中、后序遍历。#include"stdafx.h"#include#includevoidpreorder(intj,inti,char*s){if(j>i)return;printf("%c",s[j]);preorder(j*2+1,i,s);preorder
5、(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*
6、bt;chars[100];scanf("%s",s);bt=s;while(s[i]!=0){i++;}//printf("%d",i);preorder(0,i,bt);printf("");midorder(0,i,bt);printf("");lasorder(0,i,bt);printf("");return0;}算法(1)已知二叉树(二叉链表)根结点指针为bt,求该二叉树中的叶子数目。intpreorder(BiTbt){intk=0;if(bt){if(!bt->lchild&&!bt->
7、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)
8、;}}(3)已知某二叉树(二叉链表)的根结点指针bt。编写算法,将该二叉树中所有结点的左右子树互换。voidpreorder(BiTbt){charc;if(bt){c=bt->lchild;bt->lchild=bt->rchild;bt->rchild=c;preorder(bt->lchild);preorder(bt->r