文档介绍:该【数据结构第六章一二次作业 】是由【幸福人生】上传分享,文档一共【14】页,该文档可以免费在线阅读,需要了解更多关于【数据结构第六章一二次作业 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。数据结构第六章一二次作业
上机题
(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;
构。实现该完全二叉树的先、中、后序遍历。
#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->lchild);
preorder(bt->rchild);
}
}
(4)已知n个结点的完全二叉树结点数据域值按结点编
号次序顺序存于一维数组(元素下标范围0..n-1)。
编写算法,由该数组首地址以及数组长度n建立对
应的二叉链表存储结构。
voidpreorder(BiTbt,intn,char*s,intj)
{
if(bt)
{
bt->lchild=s[2*j+1];
bt->rchild=s[2*j+2];
preorder(bt->lchild);
preorder(bt->rchild);
}
}
/*调用方式
数组:ch[n];
s=ch;
j=0;
preorder(BiTbt,intn,char*s,intj)
*/
上机题
(1)编写完整程序,实现中序遍历线索二叉树存储结构、
线索化以及中序遍历。
#include""
#include<>
#include<>
enumPT{LINK,THREAD};
typedefstructnode
{chardata;
structnode*lchild,*rchild;
enumPTltag,rtag;
}*SBiT,SBiT_Node;
SBiTcrtSBT()
{
charch;
SBiTbt;
ch=getchar();
if(ch=='#')
returnNULL;
bt=newSBiT_Node();
bt->data=ch;
bt->lchild=crtSBT();
bt->rchild=crtSBT();
returnbt;
}
SBiTfirst(SBiTbt)
{while(bt&&bt->ltag==LINK)bt=bt->lchild;
returnbt;
}/
SBiTnext(SBiTp)
{if(p->rtag==THREAD)returnp->rchild;
returnfirst(p->rchild);
}
voidmidtravel(SBiTp,SBiTroot)
{p=first(root);
while(p){printf("%c",p->data);p=next(p);}
}
voidmit(SBiTbt,SBiT&pr)
{if(bt)
{mit(bt->lchild,pr);
if(pr)if(pr->rchild)pr->rtag=LINK;
else{pr->rtag=THREAD;pr->rchild=bt;}
if(bt->lchild)bt->ltag=LINK;
else{bt->ltag=THREAD;bt->lchild=pr;}
pr=bt;
mit(bt->rchild,pr);
}
}
intmain(intargc,char*argv[])
{
SBiTbt;
bt=crtSBT();
SBiTpr=NULL;
mit(bt,pr);
pr->rtag=THREAD;
midtravel(pr,pr);
printf("\n");
return0;
}
(2)编写完整程序,用堆栈实现前/中/后序非递归遍历,
并与递归遍历结果比较。
#include<>
#include<>
typedefstructNode{
chardata;
Node*leftchild;
Node*rightchild;
}Node;
/*
初始化一棵二叉树排序树。
*/
voidInitBinaryTree(Node**root,charelem)
{
*root=(Node*)malloc(sizeof(Node));
if(!(*root))
{
printf("Memoryallocationforrootfailed.\n");
return;
}
(*root)->data=elem;
(*root)->leftchild=NULL;
(*root)->rightchild=NULL;
}
/*
向二叉树排序树中插入结点。
*/
voidInsertNode(Node*root,charelem)
{
Node*newnode=NULL;
Node*p=root,*last_p=NULL;
newnode=(Node*)malloc(sizeof(Node));
if(!newnode)
{
printf("Memoryallocationfornewnodefailed.\n");
return;
}
newnode->data=elem;
newnode->leftchild=NULL;
newnode->rightchild=NULL;
while(NULL!=p)
{
last_p=p;
if(newnode->data<p->data)
{
p=p->leftchild;
}
elseif(newnode->data>p->data)
{
p=p->rightchild;
}
else
{
printf("Nodetobeinsertedhasexisted.\n");
free(newnode);
return;
}
}
p=last_p;
if(newnode->data<p->data)
{
p->leftchild=newnode;
}
else
{
p->rightchild=newnode;
}
}
/*
创建一棵二叉树排序树。
*/
voidCreatBinarySearchTree(Node**root,chardata[],intnum)
{
inti;
for(i=0;i<num;i++)
{
if(NULL==*root)
{
InitBinaryTree(root,data[i]);
}
else
{
InsertNode(*root,data[i]);
}
}
}
/*
前序遍历二叉树,递归方法。
*/
voidPreOrderRec(Node*root)
{
if(NULL!=root)
{
printf("%c",root->data);
PreOrderRec(root->leftchild);
PreOrderRec(root->rightchild);
}
}
/*
前序遍历二叉树,非递归方法。
*/
voidPreOrderNoRec(Node*root)
{printf("非递归方法:");
Node*p=root;
Node*stack[30];
intnum=0;
while(NULL!=p||num>0)
{
while(NULL!=p)
{
printf("%c",p->data);
stack[num++]=p;
p=p->leftchild;
}
num--;