{ BTCHINALR *q;
struct node1 *s[30]; int j,i,x;
printf(\建立二叉树,输入结点对应的编号和值,编号和值之间用逗号隔开\\n\\n\ printf(\ scanf(\ while(i != 0 && x != '$')
{q = (BTCHINALR*)malloc(sizeof(BTCHINALR)); /*建立一个新结点q*/ q->data = x; q->lchild = NULL; q->rchild = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1,对应的结点是根结点*/ {j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0) s[j]->lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(\
scanf(\
return s[1]; /*返回根结点地址*/ }
void inorder(BTCHINALR *bt) /*中序遍历二叉树(递归算法)*/ {if(bt != NULL)
{ inorder(bt->lchild); printf(\ inorder(bt->rchild); } }
void inorder_notrecursive(BTCHINALR *bt) /*中序遍历二叉树(非递归算法)*/ {BTCHINALR *q, *s[20]; int top = 0; int bool = 1; q = bt;
do {while(q != NULL)
{ top ++; s[top] = q; q = q->lchild; } if(top == 0) bool = 0; else { q = s[top]; top --;
printf(\ q = q->rchild; } }while(bool); }
21
main( )
{ BTCHINALR *bt; char ch; int i;
bt = createbt(); i = 1; while(i) {
printf(\中序遍历二叉树(递归按y键,非递归按n键): \ fflush(stdin); scanf(\
if(ch == 'y') inorder(bt); else inorder_notrecursive(bt); printf(\
printf(\继续操作吗?(继续按1键,结束按0键): \ fflush(stdin); scanf(\ } }
方法二:按先序遍历序列建立二叉树的二叉链表,已知先序序列为:
A B C φ φ D E φ G φ φ F φ φ φ
#define datatype char typedef struct node {datatype data;
struct node *lchild,*rchild; }JD;
JD *crt_bt_pre(JD *bt) { char ch;
printf(\ scanf(\
if(ch==' ') bt=NULL; else
22
{ bt=(JD *)malloc(sizeof(JD)); bt->data=ch;
bt->lchild=crt_bt_pre(bt->lchild); bt->rchild=crt_bt_pre(bt->rchild); }
return(bt);
}
23
实验三 图的创建与访问算法的设计
一、目的
本实验的目的是通过理解图的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。
二、题目
图的创建与访问算法的设计
三、实验类型
设计性。本实验设计了图的创建与访问算法。 四、要求及提示
说明:以下4个题中,任意选作一题。 1、【问题描述】
设有六个比赛项目,规定每个选手至多可参加三个项目,有五人报名参加比赛(如下表所示)设计比赛日程表,使得在尽可能短的时间内完成比赛。 姓 名 项目 1 项目 2 项目 3 丁 一 跳 高 跳 远 100 米 马 二 标 枪 铅 球 张 三 标 枪 100 米 200 米 李 四 铅 球 200 米 跳 高 王 五 跳 远 200 米 【基本要求】
实现以下基本操作: (1) 建立图。
(2) 输出比赛日程表。
(3) 对所建的图进行深度优先遍历,输出深度优先遍历序列。
2、【问题描述】
设有六个比赛项目,规定每个选手至多可参加四个项目,有五人报名参加比赛(如下表所示)设计比赛日程表,使得在尽可能短的时间内完成比赛。 姓名 张一 王二 李三 马四 董六
【基本要求】
实现以下基本操作: (1) 建立图。
(2) 输出比赛日程表。
(3) 对所建的图进行广度优先遍历,输出广度优先遍历序列。
24
项目1 跳高 铅球 标枪 100米 铅球 项目2 100米 跳高 跳远 200米 标枪 项目3 200米 200米 跳高 项目4 跳远
相关推荐: