老婆的考研题，不会做，求助 ( 积分: 200 )

  • 主题发起人 主题发起人 loogun
  • 开始时间 开始时间
L

loogun

Unregistered / Unconfirmed
GUEST, unregistred user!
1。已知序列35、39、50、18、30、33、39、32、34、15、10、20、1，请画出该序列的二叉排序树，并分别给出依次进行下列操作后的二叉树：
插入数据10
删除节点20
再删除节点18
2。写一算法，判断一个有向图是否是有向无环图。用邻接矩阵作为图的存储结构。要求先描述改数据结构。
 
1。已知序列35、39、50、18、30、33、39、32、34、15、10、20、1，请画出该序列的二叉排序树，并分别给出依次进行下列操作后的二叉树：
插入数据10
删除节点20
再删除节点18
2。写一算法，判断一个有向图是否是有向无环图。用邻接矩阵作为图的存储结构。要求先描述改数据结构。
 
太简单！！！，此题不会，估计今年考研希望不大，除非是特别烂的学校。
 
这难道是考研题？哇噻，我们学校数据结构的编程题都要简单好多呢
 
我这还有个２叉树的笔记，不过是ｂｏｒｌａｎｄｃ的，图的我帮你找找
/******************************** 树 ************************************/
/* 本应用程序实现下面的(1)和(2)。
(1)二叉树两个遍历算法的测试程序
递归遍历算法与非遍历算法：
Button1Click、Button2Click和Button5Click
(2)二叉树遍历算法的应用
统计结点数与计算树深：
Button3Click和Button4Click
(3)从图遍历 (仅C++Builder)
利用二叉树图，指出先根、中根、后根遍历的结点的顺序
(4)线索二叉树的测试程序
中序线索化的递归遍历算法与非遍历算法
线索二叉树的逻辑表示图，求前驱结点与后继结点
(5)画逻辑图 (仅C++Builder)
绘制线索二叉树的逻辑表示图
*/
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "UJG6.h"
#define ELEMTP int
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
/******************* (1)二叉树两个遍历算法的测试程序 *******************/
struct node
{ ELEMTP data;
/* 数据域 */
struct node *lch,*rch;
/* 左、右孩子指针域 */
} *root,*ss[30];
/* 根结点应是全局变量 */
String S;
/* 算法6.1 建立二叉树的算法(直接传递参数) */
struct node *create(int indx[],int x[]) /* 建立二叉树 */
{ struct node *t,*q;
int i=1,j;
while(indx!=0 &&
x!=0)
{ q=(struct node *)malloc(sizeof(struct node));
/* 分配结点 */
q->data=x;
q->lch=NULL;
q->rch=NULL;
ss[indx]=q;
if (indx==1) t=q;
/* t为树的根结点 */
else
{ j=indx/2;
/* 双亲结点编号 */
if (indx%2==0) ss[j]->lch=q;
/* 双亲结点左孩子编号 */
else
ss[j]->rch=q;
/* 双亲结点右孩子的编号 */
}
i++;
}
return t;
}
/* 算法6.2 先根遍历的递归算法 */
void predorder(struct node *p)
{
if(p!=NULL)
{ S = S + p->data + "
";
//printf("%4d", p->data);/* 访问根结点 */
predorder(p->lch);
/* 按先根次序遍历左子树 */
predorder(p->rch);
/* 按先根次序遍历右子树 */
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender) /* 测试算法6.2 */
{ // 采用图6.7(b)的数据表建立二叉树
int indx[]={0,1,2,3,4,6,9,0},x[]={0,11,12,13,14,15,16};
root=create(indx,x);
Form1->Memo1->Clear();
Form1->Memo1->Lines->Add("测试先根遍历递归算法6.2结果:");
S = "";
predorder(root);
Form1->Memo1->Lines->Add(S);
}
//---------------------------------------------------------------------------
/* 算法6.4 中根遍历的非递归算法 */
void inorderz(struct node *p)
{ struct node *q;
int top;
bool b;
q=p;
top=0;
/* 栈顶指针 */
b=true;
/* b=true继续循环;
b=false为栈空,结束循环 */
do
{ while(q!=NULL)
{ top++;
ss[top]=q;
q=q->lch;
}
if (top==0) b=false;
else
{ q=ss[top];
top--;
S = S + q->data + "
";/* 访问根结点 */
q=q->rch;
}
} while(b);
}
void __fastcall TForm1::Button2Click(TObject *Sender)/* 测试算法6.4 */
{ /* 采用图6.7(b)的数据表建立二叉树 */
int indx[]={0,1,2,3,4,6,9},x[]={0,11,12,13,14,15,16};
root=create(indx,x);
Memo1->Lines->Add("测试中根遍历非递归算法6.4结果:");
S = "";
inorderz(root);
Form1->Memo1->Lines->Add(S);
}
//---------------------------------------------------------------------------
/******************** (2)二叉树遍历算法的应用 ***********************/
int m, /* 结点总数 */
n, /* 叶子结点数 */
k;
/* 二叉树树深 */
/* 用中根遍历统计二叉树结点个数和叶子个数的算法:算法6.8 */
void injishu(struct node *t)
{ if (t!=NULL)
{ injishu(t->lch);
/* 中根遍历左子树 */
S = S + Format("%5d",ARRAYOFCONST((t->data)));/* 访问根结点 */
m++;
/* 结点计数 */
if(t->lch==NULL &&
t->rch==NULL) n++;
/* 叶子计数 */
injishu(t->rch);
/* 中根遍历右子树 */
}
}
void __fastcall TForm1::Button3Click(TObject *Sender)
{ struct node *t;
int indx[]={0,1,2,3,4,6,9},x[]={10,11,12,13,14,15,16};
t=create(indx,x);
S = "";
m=0;
n=0;
Form1->Memo1->Lines->Add("测试算法6.8, 中根遍历结果:");
injishu(t);
Form1->Memo1->Lines->Add(S);
Form1->Memo1->Lines->Add(Format(
"结点个数m=%d,叶子个数n=%d",ARRAYOFCONST((m,n))));
}
//---------------------------------------------------------------------------
/* 求二叉树的树深算法：算法6.9 */
void predeep(struct node *t,int i) // 先根递归遍历算法
{ if (t!=NULL)
{ S = S + Format("%5d",ARRAYOFCONST((t->data)));/* 访问根结点 */
i++;
if (k<i) k=i;
predeep(t->lch,i);
/* 先根遍历右子树 */
predeep(t->rch,i);
/* 先根遍历右子树 */
}
}
void __fastcall TForm1::Button4Click(TObject *Sender) /* 测试算法6.9 */
{ struct node *t;
int indx[]={0,1,2,3,4,6,9},x[]={10,11,12,13,14,15,16},i;
t=create(indx,x);
S = "";
k=0;
i=0;
Form1->Memo1->Lines->Add("测试算法6.9, 先根遍历结果:");
predeep(t,i);
Form1->Memo1->Lines->Add(S);
Form1->Memo1->Lines->Add(Format("树深k=%d", ARRAYOFCONST((k))));
}
//---------------------------------------------------------------------------
/**********************按层遍历二叉树算法的测试*********************/
// 按层遍历二叉树的算法6.7
void levelorderz(struct node *p) /* 按层遍历算法 */
{ struct node *q[30];
/* 辅助队列，设结点不超过29个 */
int front=0, rear=0;
/* 置空队列 */
if(p!=NULL) { rear++;
q[rear]=p;
} /* 根结点进队 */
while (front!=rear)
{ // 队首结点出队并访问
front++;
p=q[front];
S = S + p->data + "
";
if(p->lch!=NULL)
{ rear++;
q[rear]=p->lch;
};
/* p左孩子不空则进队 */
if(p->rch!=NULL)
{ rear++;
q[rear]=p->rch;
};
/* p右孩子不空则进队 */
}
free(q);
}
void __fastcall TForm1::Button5Click(TObject *Sender) // 测试算法6.7
{ // 采用图6.7(b)的数据表建立二叉树
int indx[]={0,1,2,3,4,5,6,7,8,9,18,0},x[]={0,11,12,13,14,15,16,17,0};
root=create(indx,x);
Form1->Memo1->Lines->Add("测试算法新增2叉树结果:");
S = "*按层遍历结点顺序* ";
levelorderz(root);
Form1->Memo1->Lines->Add(S);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button7Click(TObject *Sender)
{
struct node *t;
int indx[]={0,1,2,3,4,6,9,18,0},x[]={0,11,12,13,14,15,16,17,0},i;
t=create(indx,x);
S = "";
k=0;
i=0;
Form1->Memo1->Lines->Add("测试算法新增2叉树, 先根遍历结果:");
predeep(t,i);
Form1->Memo1->Lines->Add(S);
Form1->Memo1->Lines->Add(Format("树深k=%d", ARRAYOFCONST((k))));
}
//---------------------------------------------------------------------------
 
找到一个图的，不过不是判断，不知到你用的上用不上
/*
test1: 无向图的邻接表建立与遍历的源程序
test2: 有向无环图的拓扑排序和求关键路径的源程序
*/
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 20
struct ArcNode
{ int adjvex;
/* 弧所指向顶点的位置 */
struct ArcNode *nextarc;
/* 指向下一条弧的指针域 */
};
struct Vnode
{ int data;
/* 顶点数据域 */
struct ArcNode *firstarc;
/* 指向第一条依附该顶点的弧的指针域 */
};
struct Vnode AdjList[MaxSize];
int m,n,v;
void test1();
void test2();
void main()
{ clrscr();
// test1();
/* 无向图的邻接链表建立与遍历示范程序 */
test2();
/* 拓扑排序和求关键路径 */
}
void test1() /* 无向图的邻接表示范程序 */
{
int cord;
void creategraph(struct Vnode A[MaxSize]);
void dfs(struct Vnode A[MaxSize]);
void bfs(struct Vnode A[MaxSize]);
printf("* 无向图的邻接链表建立与遍历示范程序 */n");
do
{ printf("********主菜单***********/n");
printf("
1 建立无向图的邻接链表/n");
printf("
2 按深度遍历图/n");
printf("
3 按广度遍历图/n");
printf("
4 结束程序运行/n");
printf("*************************/n");
printf("
请输入您的选择号: ");
scanf("%d",&cord);
switch (cord)
{ case 1: creategraph(AdjList);
break;
case 2: dfs(AdjList);
break;
case 3: bfs(AdjList);
break;
case 4: exit(0);
}
} while(cord<=4);
}
void creategraph(struct Vnode A[MaxSize]) /* 建立无向图 */
{ int i,j,k;
struct ArcNode *p;
struct
{ int x,y;
} b[]={{5,8},{4,8},{6,7},{3,7},{3,6},
{2,5},{2,4},{1,3},{1,2}};
//printf("输入图的边数m和顶点数n(空格隔开): ");
//scanf("%d%d",&m,&n);
m=9;
n=8;
for (k=0;
k<n;
k++) /* 初始化顶点向量表 */
{ A[k].data=k+1;
A[k].firstarc=NULL;
}
for (k=0;
k<m;
k++)
{ //printf("输入和边关联的顶点号i和j(空格隔开): ");
//scanf("%d%d",&i,&j);
i=b[k].x;
j=b[k].y;
p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex=j;
p->nextarc=A[i-1].firstarc;
/* 每一个边结点都插入到链表首部 */
A[i-1].firstarc=p;
p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex=i;
p->nextarc=A[j-1].firstarc;
A[j-1].firstarc=p;
}
printf("/n显示邻接链表信息:/n");
for (k=0;
k<n;
k++) /* 显示已建立邻接链表信息 */
{ printf("%4d",A[k].data);
p=A[k].firstarc;
while(p)
{ printf("%4d",p->adjvex);
p=p->nextarc;
}
printf("/n");
}
}
void dfs(struct Vnode A[MaxSize])/*从一个顶点出发对图作深度优先遍历*/
{ struct ArcNode *p,*ar[MaxSize];/*ar为顺序栈,存放遍历过程边结点地址*/
int x,i,y,top=-1;
int visited[MaxSize];
/* 存放已遍历过的顶点的标记 */
for (i=0;
i<n;
i++) visited=0;
printf("/n输入遍历出发顶点: ");
scanf("%d",&x);
/* 遍历出发顶点的编号 */
visited[x-1]=1;
p=A[x-1].firstarc;
while(p || top>=0)
{ if(!p) { p=ar[top];
top--;
}
y=p->adjvex;
if(visited[y-1]==0)
{ visited[y-1]=1;
/* 若未遍历过,则从本顶点出发继续作深度优先
遍历,并把下一个顶点进栈 */
printf("→%d",y);
p=p->nextarc;
if(p) { top++;
ar[top]=p;
}
p=A[y-1].firstarc;
}
else
p=p->nextarc;
}
printf("/n");
}
void bfs(struct Vnode A[MaxSize])/*从一个顶点出发对图作广度优先遍历*/
{ struct ArcNode *p;
int x,i,y,front=-1,rear=-1;
int ar[MaxSize];
/* ar[]为顺序队列,存放刚遍历过的顶点的编号 */
int visited[MaxSize];
/* 存放已遍历过的顶点的标记 */
for (i=0;
i<n;
i++) visited=0;
printf("/n输入遍历出发顶点: ");
scanf("%d",&x);
/* 遍历出发顶点的编号 */
visited[x-1]=1;
p=A[x-1].firstarc;
while(p || front!=rear)
{ if(!p)
{ front++;
y=ar[front];
p=A[y-1].firstarc;
}
y=p->adjvex;
if(visited[y-1]==0)
{ visited[y-1]=1;
/* 若未遍历过,则从本顶点出发继续作广度优先
遍历,并把下一个顶点入队 */
printf("→%d",y);
rear++;
ar[rear]=y;
}
p=p->nextarc;
}
printf("/n");
}
/**********************************************************************/
typedef struct node /* 定义AOV网的邻接链表的边结点结构 */
{ int vex;
struct node *next;
} edgenode;
typedef struct vnode /* 定义AOV网的邻接链表的顶点结点结构 */
{ int id;
struct node *link;
} vexnode;
typedef struct node1 /* 定义AOE网的邻接链表的边结点结构 */
{ int adgvex;
int dut;
struct node1 *next;
} edgenode1;
typedef struct vnode1 /* 定义AOE网的邻接链表的顶点结点结构 */
{ int vertex;
int id;
struct node1 *link;
} vexnode1;
int na;
void test2() /* 有向无环图拓扑排序和求关键路径的示范程序 */
{
int create(vexnode1 dig[]);
int create1(vexnode dig[]);
void toposort(vexnode dig[],int n);
void criticalpath(vexnode1 dig[],int n);
vexnode1 dig[20];
/* AOE的顶点数组 */
vexnode dig2[20];
/* AOV的顶点数组 */
int cord=1;
printf("* 有向无环图拓扑排序和求关键路径的示范程序 */n");
while (cord>=0 &&
cord<5)
{ printf("********主菜单***********/n");
printf("
1 建立AOV邻接表/n");
printf("
2 建立AOE邻接表/n");
printf("
3 拓扑排序(AOV)/n");
printf("
4 求关键路径(AOE)/n");
printf("
0 结束/n");
printf("*************************/n");
printf("
请输入您的选择号: ");
scanf("%d",&cord);
switch (cord)
{ case 1: n=create1(dig2);
break;
case 2: { printf("输入AOE活动数: ");
scanf("%d",&na);
n=create(dig);
}
break;
case 3: toposort(dig2,n);
/* 须先建AOV网 */
break;
case 4: criticalpath(dig,n);
/* 须先建AOE网 */
break;
case 0: exit(0);
}
}
}
int create(vexnode1 dig[]) /* 建立有向图的AOE网邻接表 */
{ int i,j,a,b,c;
edgenode1 *p;
struct
{ int x,y,z;
} t[]={{0,0,0},{1,4,5},{1,3,4},{1,2,6},{2,5,1},
{3,5,1},{4,6,2},{5,8,5},{5,7,7},{6,8,4},
{7,9,2},{8,9,4},{0,0,0}};
//printf("输入AOE顶点数: ");
//scanf("%d%d",&i);
i=9;
for (j=1;
j<20;
j++) /* 初始化顶点数组 */
{ dig[j].vertex=j;
dig[j].id=0;
dig[j].link=NULL;
}
//printf("输入AOE边信息a b c: ");
//scanf("%d%d%d",&a,&b,&c);
/* a为始顶点,b为终顶点,c为活动的权 */
j=1;
a=t[j].x;
b=t[j].y;
c=t[j].z;
while(a!=0)
{ dig.id++;
p=(edgenode1 *)malloc(sizeof(edgenode1));
p->adgvex=b;
p->dut=c;
p->next=dig[a].link;
dig[a].link=p;
//printf("输入AOE边信息a b c: ");
//scanf("%d%d%d",&a,&b,&c);
/* a为始顶点,b为终顶点,c为活动的权 */
j++;
a=t[j].x;
b=t[j].y;
c=t[j].z;
}
printf("/n显示AOE图邻接链表:/n");
for (j=1;
j<=i;
j++) /* 显示已建立AOE图邻接链表信息 */
{ printf("%4d%4d",j,dig[j].id);
p=dig[j].link;
while(p!=0)
{ printf("%6d%3d",p->adgvex,p->dut);
p=p->next;
}
printf("/n");
}
return i;
}
int create1(vexnode dig[]) /* 建立有向无环图的AOV网邻接表 */
{ int i,j,a,b;
edgenode *p;
struct
{ int x,y;
} t[]={{0,0},{1,2},{1,3},{1,4},{3,2},{3,5},
{4,5},{6,4},{6,5},{0,0}};
//printf("输入AOV顶点数: ");
//scanf("%d%d",&i);
i=6;
for (j=1;
j<20;
j++) /* 初始化顶点数组 */
{ dig[j].id=0;
dig[j].link=NULL;
}
//printf("输入AOV边信息a b: ");
//scanf("%d%d",&a,&b);
/* a为始顶点,b为终顶点 */
j=1;
a=t[j].x;
b=t[j].y;
while(a!=0)
{ dig.id++;
p=(edgenode *)malloc(sizeof(edgenode));
p->vex=b;
p->next=dig[a].link;
dig[a].link=p;
//printf("输入AOV边信息a b: ");
//scanf("%d%d",&a,&b);
/* a为始顶点,b为终顶点 */
j++;
a=t[j].x;
b=t[j].y;
}
printf("/n显示AOV图邻接链表:/n顶点序号 入度id/n");
for (j=1;
j<=i;
j++) /* 显示已建立AOV图邻接链表信息 */
{ printf("%5d%8d",j,dig[j].id);
p=dig[j].link;
while(p!=0)
{ printf("%6d",p->vex);
p=p->next;
}
printf("/n");
}
return i;
}
void toposort(vexnode dig[],int n) /* 有向无环图拓扑排序 */
{ edgenode *p;
int i,j,k,top=0,m=0;
for (i=1;
i<=n;
i++) /* 把入度为0的顶点构成链表 */
if(dig.id==0) { dig.id=top;
top=i;
}
while(top>0)
{ j=top;
top=dig[top].id;
printf("%5d",j);
/* 输出入度为0的顶点 */
m++;
p=dig[j].link;
while(p!=NULL)
{ k=p->vex;
dig[k].id--;
if(dig[k].id==0)
{ dig[k].id=top;
top=k;
}
p=p->next;
}
}
printf("/n");
if (m<n) printf("该网中有环!/n");
}
void criticalpath(vexnode1 dig[],int n) /* 求关键路径 */
{ int front=0,rear=0;
int tpord[20],vl[20],ve[20];
int l[20],e[20],i,j,k,m;
edgenode1 *p;
for (i=1;
i<=n;
i++) ve=0;
for (i=1;
i<=n;
i++)
if(dig.id==0) tpord[++rear]=i;
m=0;
while(front!=rear)
{ front++;
j=tpord[front];
m++;
p=dig[j].link;
while(p)
{ k=p->adgvex;
dig[k].id--;
if(ve[j]+p->dut >
ve[k]) ve[k]=ve[j]+p->dut;
if(dig[k].id==0) tpord[++rear]=k;
p=p->next;
}
}
if(m<n) printf("该AOE网中有一个环!/n");
for (i=1;
i<=n;
i++) vl=ve[n];
for (i=n-1;
i>=1;
i--)
{ j=tpord;
p=dig[j].link;
/* 求vl[]数组的值 */
while(p)
{ k=p->adgvex;
if(vl[k]-p->dut <
vl[j]) vl[j]=vl[k]-p->dut;
p=p->next;
}
}
printf("输出最早、最晚发生时间/n");/*输出每个事件最早、最晚发生时间*/
printf("边起点 边终点 e l l-e/n");
i=0;
for (j=1;
j<=n;
j++) /* 计算活动的最早、最晚发生时间 */
{ p=dig[j].link;
while(p)
{ k=p->adgvex;
e[++i]=ve[j];
l=vl[k]-p->dut;
printf("%d/t%d/t%d/t%d/t%d/t",
dig[j].vertex,dig[k].vertex,e,l,l-e);
if(l==e) printf("是关键活动/n");
else
printf("/n");
p=p->next;
}
}
}

 
楼上的谢了，能不能帮我做出来
马上给分
 
/* 插入算法在test4已经改好
图的部分看最下面
(3) test3: * 二叉排序树建立与插入 *
本测试中利用算法的插入功能: 调用算法建立;调用中根遍历验证;
(4) test4: * 二叉排序树建立与插入 */#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxsize 50 /* 最大记录个数 */
void test3();
void test4();
void main()
{ clrscr();
test3();
test4();
}
/*********************** 顺序表的查找 ************************/
struct node
{ int key;
char ch;
};
struct node r[maxsize];
/* 算法8.1 */
void sequnt_search1(struct node r[],int n,int k)
{ int i=0;
while (i<n &&
r.key!=k) i++;
if (i<n) printf("找到%3d, 记录是r[%2d]/n",k,i);
else
printf("%3d未找到!/n",k);
}
/* 算法8.2 */
void sequnt_search2(struct node r[],int n,int k)
{ int i=0;
r[n].key=k;
while (r.key!=k) i++;
if (i<n) printf("找到%3d, 记录是r[%d]/n",k,i);
else
printf("%3d未找到!/n",k);
}

/* 折半查找算法8.3 */
void binary_search(struct node r[],int n,int k)
{ int low=0,high,m,find=0;
high=n-1;
do
{ m=(low+high)/2;
if (k==r[m].key)
{ printf("找到%3d, 记录是r[%d]/n",k,m);
find=1;
}
else
if (k<r[m].key) high=m-1;
else
if (k>r[m].key) low=m+1;
} while (find==0 &&
low<=high);
if (find==0) printf("%3d未找到!/n",k);
}
/* 二叉查找树的存储结构 */
struct nodeb
{ int key;
struct nodeb *lch,*rch;
} *root;
/* 二叉排序树查找算法8.4的功能: 若查找成功,则显示查找结果;
若查找不成功,则返回插入指针p */
struct nodeb *bstsrch(struct nodeb *t,struct nodeb *q,int k)
{ int flag;
struct nodeb *p;
p=NULL;
q=t;
flag=0;
while (q!=NULL &&
flag==0)
{ if (q->key==k)
{ printf("查找%d成功! ",q->key);
flag=1;
}
else
if (k<q->key) { p=q;
q=q->lch;
}
else
{ p=q;
q=q->rch;
}
}
if (flag==0) printf("查找%d失败! ",k);
return p;
}
/* 二叉排序树的插入算法8.5 */
void bstins(struct nodeb *t,struct nodeb *p,int k)
{ struct nodeb *r;
/* 若查找不成功,则在指针p处插入叶子结点 */
if (p!=NULL)
{ r=(struct nodeb *)malloc(sizeof(struct nodeb));
r->key=k;
r->lch=NULL;
r->rch=NULL;
printf("插入%d!",k);
if (t==NULL) t=r;
else
if (k<p->key) p->lch=r;
else
p->rch=r;
}
}
void test3()/* 测试插入算法8.4、8.5: 调用算法6.16建立;调用中根遍历验证 */
{ struct nodeb *create_binary(int x[],int n);
void inorder(struct nodeb *p);
struct nodeb *p,*q;
/* 采用图6.19的数据表建立二叉排序树 */
int x[]={0,10,6,18,3,20,2}, n=6;
root=create_binary(x,n);
printf("测试二叉排序树的插入: ");
p=bstsrch(root,q,4);
/* bstsrch()函数若查找不成功,则返回插入指针p */
bstins(root,p,4);
/* bstins()函数在指针p处插入结点 */
inorder(root);
/* 调用中根遍历验证插入结果 */
printf("/n");
}
void inorder(struct nodeb *p)
{ if(p!=NULL)
{ inorder(p->lch);
/* 按中根次序遍历左子树 */
printf("%4d", p->key);
/* 访问根结点 */
inorder(p->rch);
/* 按中根次序遍历右子树 */
}
}
/* 建立二叉排序树的算法6.16 */
struct nodeb *create_binary(int x[],int n)
{ void insertb(struct nodeb *t,struct nodeb *s);
struct nodeb *s,*t;
int i,k;
t=NULL;
for (i=1;i<=n;i++)
{ /* 输入值k */
k=x;
s=(struct nodeb *)malloc(sizeof(struct nodeb));
/* 分配结点 */
s->key=k;
s->lch=NULL;
s->rch=NULL;
if (t==NULL) t=s;
else
insertb(t,s);
}
return t;
}
/* 在二叉排序树中插入结点的非递归算法6.18 */
void insertb(struct nodeb *t,struct nodeb *s)
{ struct nodeb *p,*q;
if (t==NULL)
t=s;
else
{ p=t;
while (p!=NULL)
{ q=p;
/* 当p向子树结点移动时，q记录p的双亲位置 */
if (s->key <
t->key) p=p->lch;
else
p=p->rch;
}
if (s->key <
t->key) q->lch=s;
else
q->rch=s;
/* 当p为空时，q就是可插入的地方 */
}
}
void test4() /* 直接测试算法6.16(建立)、18(插入) */
{ /* 采用图6.19的数据表建立二叉排序树 */
int x[]={0,35,39,50,18,30,33,39,32,34,15,10,20,1}, n=13;
struct nodeb *r;
root=create_binary(x,n);
printf("测试二叉排序树的插入: ");
r=(struct nodeb *)malloc(sizeof(struct nodeb));
/* 分配结点内存 */
r->key=10;
r->lch=NULL;
r->rch=NULL;
/* 制作叶子结点 */
insertb(root,r);
/* 调用算法6.18插入结点 */
inorder(root);
/* 调用中根遍历验证插入结果 */
printf("/n");
}
/*图的判断笔记里有仔细看这段*/
void toposort(vexnode dig[],int n) /* 有向无环图拓扑排序 */
{ edgenode *p;
int i,j,k,top=0,m=0;
for (i=1;
i<=n;
i++) /* 把入度为0的顶点构成链表 */
if(dig.id==0) { dig.id=top;
top=i;
}
while(top>0)
{ j=top;
top=dig[top].id;
printf("%5d",j);
/* 输出入度为0的顶点 */
m++;
p=dig[j].link;
while(p!=NULL)
{ k=p->vex;
dig[k].id--;
if(dig[k].id==0)
{ dig[k].id=top;
top=k;
}
p=p->next;
}
}
printf("/n");
if (m<n) printf("该网中有环!/n");
}
 
准备考试去，呵呵
 
不如做烟酒生更好
 
接受答案了.
 
您必须登录或注册才可回复。

Similar threads

W
急，求助！有关二叉树的创建。(100分)
回复
3
查看
424
wolfmaster
W
大
请问一个算法问题。(100分)
回复
14
查看
391
LeonSu
L
G
一个来自实践的算法难题(300分)
2
回复
35
查看
682
Traveller
T
B
我坚决要娶黄蓉做老婆 (1分)
2
回复
20
查看
482
TanYiQiang
T
S
高分求助（500分，不够再加）三层结构，问题探讨！ (0分)
回复
9
查看
229
hugh_A
H
后退
顶部