6道题按要求编写，正确的高分
编写程序验证"二叉树"的基本功能 3
目的:
从键盘输入bitree
输出按层次遍历的结果
输出 距离根节点最近的叶子
输入:
ABD..E..C..
输出:
ABCDE //by_level
C //距离根节点最近的叶子
编写程序验证"二叉树"的基本功能 2
目的:
从键盘输入bitree: make_bitree
显示结点总数： count_all
显示度数为0的结点总数： count_N0
显示度数为1的结点总数： count_N1
显示度数为2的结点总数： count_N2
销毁bitree: destory_bitree
输入:
ABD..E..C..
输出:
5 //count_all
3 //count_N0
0 //count_N1
2 //count_N2
编写程序验证"二叉树"的基本功能 1
目的:
从键盘输入bitree: make_bitree
显示bitree内容： pre_order / in_order / post_order
销毁bitree: destory_bitree
输入:
ABD..E..C..
输出:
ABDEC //pre_order
DBEAC //in_order
DEBCA //post_order
编写程序验证"序列表"的基本功能
目的:
从键盘输入创建序列表: input
显示序列表内容： display
在指定位置插入元素: insert
删除指定位置的元素: remove
输入:
5 abcde //创建序列表
2 x //在位置2插入'x'
2 //删除位置2的元素
输出:
5 abcde
6 abxcde
5 abcde
编写程序验证"二叉排序树"的基本功能
目的:
从键盘输入字符串，按字典顺序创建BST, 以^表示结束
输出BST的先序和中序
读入一个字符，查找BST，返回F或T,表明找不到或找到.
输入:
BAC^//创建BST的内容
A //查找内容
输出:
BAC //pre_order
ABC //in_order
T //找到
编写程序验证图的遍历算法
目的:
从键盘输入图的节点数和边
编程分别实现图的深度优先和广度优先算法
读入指定节点，分别输出两种遍历方法访问节点的顺序
输入:
6 ABCDEF //6个节点
9 // 9 个边
AB AC AD BD CD CE CF DF EF //边的描述
输出:
ABDCEF //深度优先的遍历结果
ABCDEF //广度优先的遍历结果
#include "bitree.h"
void Visit(char ch)
{
printf("%c ",ch);
}
void PreOrder(BiTree root)
{
if (root!=NULL)
{
Visit(root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
void InOrder(BiTree root)
{
if (root!=NULL)
{
InOrder(root->LChild);
Visit(root->data);
InOrder(root->RChild);
}
}
void PostOrder(BiTree root)
{
if(root!=NULL)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
Visit(root->data);
}
}
void main()
{
BiTree T;
printf("请输入二叉树序列:\n");
CreateBiTree(&T);
printf("先序遍历序列为:");
PreOrder(T);
printf("\n中序遍历序列为:");
InOrder(T);
printf("\n后序遍历序列为:");
PostOrder(T);
getch();
}
//其中的bitree.h内容如下//
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
typedef char DataType;
typedef struct Node
{
DataType data;
struct Node *LChild;
struct Node *RChild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree *bt)
{
char ch;
ch = getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild)); //生成左子树
CreateBiTree(&((*bt)->RChild)); //生成右子树
}
}
#include "adjmatrix.h"
int LocateVertex(AdjMatrix *G,VertexData v)
{
int j=Error,k;
for(k=0;k<G->vexnum;k++)
if(G->vexs[k]==v)
{
j=k;
break;
}
return(j);
}
int CreateDN(AdjMatrix *G)
{
int i,j,k,weight;
VertexData v1,v2;
printf("输入图的顶点数和弧数\n");
fflush(stdin);
scanf("%d,%d",&G->arcnum,&G->vexnum);
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
for(i=0;i<G->vexnum;i++)
{
printf("输入图的顶点\n");
fflush(stdin);
scanf("%c",&G->vexs[i]);
}
for(k=0;k<G->arcnum;k++)
{
printf("输入一条弧的两个顶点及权值\n");
fflush(stdin);
scanf("%c,%c,%d",&v1,&v2,&weight);
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight;
}
return(Ok);
}
void main()
{
AdjMatrix G;
CreateDN(&G);
}
void DepthFirstSearch(Graph g,int v0)
{
visit(v0);
visited[v0]=True;
w=FirstAdjVertex(g,v0);
while(w!=-1)
{
if(!visited[w])
DepthFirstSearch(g,w);
w=NextAdjVertex(g,v0,w);
}
}
void BreadthFirstSearch(Graph g,int v0)
{
visit(v0);
visited[v0]=True;
InitQueue(&Q);
EnterQueue(&Q,v0);
while(!Empty(Q))
{
DeleteQueue(&Q,&v);
w=FirstAdjVertex(g,v);
while(w!=-1)
{
if(!visited(w))
{
visit(w);
visited[w]=True;
EnterQueue(&Q, w);
}
w=NextAdjVertex(g,v,w);
}
}
}