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

《数据结构第六章一二次作业.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、上机题（1）编写完整程序，用先序遍历法建立二叉树的二叉链表存储结构。输出该二叉树的先、中、后序遍历结点访问次序以及层次遍历结点访问次序。（建议结点数据域类型为char）//erchashu.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include#includetypedefstructnode{chardata;structnode*lchild,*rchild;}*BiT,BiTNode;BiTcrtBT(){charch;BiTbt;ch=ge

2、tchar();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(BiTbt){if(bt){midorder(bt->lchild);printf("%c",bt->data);midorder(bt

3、->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);printf("");midorder(bt);printf("");lasorder(bt);printf("");return0;}（2)从键盘输入n个数据建立n元完全二叉树顺序存储结构

4、。实现该完全二叉树的先、中、后序遍历。#include"stdafx.h"#include#includevoidpreorder(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(in

5、tj,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",i);preorder(0,i,bt);printf("");midorder(0,i,bt);printf("");lasorder(0,i,bt);printf("");ret

6、urn0;}算法（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

7、;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->lchild);preorder(bt->r