数据结构第六章一二次作业
- 格式：doc
- 大小：399.00 KB
- 文档页数：13
上机题 （1）编写完整程序，用先序遍历法建立二叉树的二叉链 表存储结构。输出该二叉树的先、中、后序遍历结 点访问次序以及层次遍历结点访问次序。（建议结 点数据域类型为char） // erchashu.cpp : Defines the entry point for the console application. //
#include "stdafx.h" #include #include typedef struct node { char data; struct node *lchild, *rchild; }*BiT, BiTNode;
BiT crtBT() { char ch; BiT bt; ch=getchar(); if(ch=='#') return NULL; bt=new BiTNode(); bt->data=ch; bt->lchild=crtBT(); bt->rchild=crtBT(); return bt; } void preorder(BiT bt) { if(bt) { printf("%c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } //printf("\n"); } void midorder(BiT bt) { if(bt) { midorder(bt->lchild); printf("%c",bt->data); midorder(bt->rchild); } //printf("\n"); } void lasorder(BiT bt) { if(bt) { lasorder(bt->lchild); lasorder(bt->rchild); printf("%c",bt->data); } //printf("\n"); } int main(int argc, char* argv[]) { BiT bt; bt=crtBT(); preorder(bt); printf("\n"); midorder(bt); printf("\n"); lasorder(bt); printf("\n"); return 0; } （2)从键盘输入n个数据建立n元完全二叉树顺序存储结 构。实现该完全二叉树的先、中、后序遍历。 #include "stdafx.h" #include #include void preorder(int j,int i,char *s) { if (j>i) return; printf("%c",s[j]); preorder(j*2+1,i,s); preorder(j*2+2,i,s); } void midorder(int j,int i,char *s) { if (j>i) return; preorder(j*2+1,i,s); printf("%c",s[j]); preorder(j*2+2,i,s); } void lasorder(int j,int i,char *s) { if (j>i) return; preorder(j*2+1,i,s); preorder(j*2+2,i,s); printf("%c",s[j]); } int main(int argc, char* argv[]) { int i=0; char *bt; char s[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"); return 0; }
算法 （1）已知二叉树（二叉链表）根结点指针为bt，求该二 叉树中的叶子数目。 int preorder(BiT bt) { int k=0; if(bt) { if(!bt->lchild&&!bt->rchild) k++; preorder(bt->lchild); preorder(bt->rchild); } return k; } （2）已知某二叉树（三叉链表）的根结点地址root，该 树中各结点的左、右儿子指针域已正确填充，写一 个算法将所有结点的双亲指针域正确填充。 void preorder(BiT bt) { if(bt==root) return ; if(bt) { bt->lchild->parent=bt; bt->rchild->parent=bt; preorder(bt->lchild); preorder(bt->rchild); } } （3）已知某二叉树（二叉链表）的根结点指针bt。编写 算法，将该二叉树中所有结点的左右子树互换。 void preorder(BiT bt) { char c; if(bt) { c=bt->lchild; bt->lchild=bt->rchild; bt->rchild=c; preorder(bt->lchild); preorder(bt->rchild); } } (4) 已知n个结点的完全二叉树结点数据域值按结点编 号次序顺序存于一维数组（元素下标范围0..n-1）。 编写算法，由该数组首地址以及数组长度n建立对 应的二叉链表存储结构。 void preorder(BiT bt,int n,char *s,int j) {
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(BiT bt,int n ,char *s,int j) */ 上机题 （1）编写完整程序，实现中序遍历线索二叉树存储结构、 线索化以及中序遍历。 #include "stdafx.h" #include #include
enum PT { LINK, THREAD }; typedef struct node { char data; struct node *lchild, *rchild; enum PT ltag, rtag; } *SBiT, SBiT_Node;
SBiT crtSBT() { char ch; SBiT bt; ch=getchar(); if(ch=='#') return NULL; bt=new SBiT_Node(); bt->data=ch; bt->lchild=crtSBT(); bt->rchild=crtSBT(); return bt; }
SBiT first(SBiT bt) { while(bt&&bt->ltag==LINK) bt=bt->lchild; return bt; }/ SBiT next(SBiT p) { if(p->rtag==THREAD) return p->rchild; return first(p->rchild); }
void midtravel(SBiT p,SBiT root) { p=first(root); while(p) { printf("%c",p->data); p=next(p); } }
void mit(SBiT bt, 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); } }
int main(int argc, char* argv[]) { SBiT bt; bt=crtSBT();
SBiT pr=NULL; mit(bt, pr); pr->rtag=THREAD; midtravel(pr,pr);
