#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<windows.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char VertexType;
#define MAX_VER_NUM 30
char Data[13][2]={{'A','B'},{'A','C'},{'A','F'},{'A','L'},{'L','J'},{'L','M'},{'J','M'},{'M','B'},{'D','E'},{'G','I'},{'G','H'},{'G','K'},{'H','K'}};
FILE *pf;
typedef struct ArcBox//边的信息
{
    int iver;
    struct ArcBox *ilink;
    int jver;
    struct ArcBox *jlink;
    char *info;
    int mark;
}ArcBox;
typedef struct VerBox//顶点的信息
{
    VertexType data;
    ArcBox *firstedge;
}VerBox;
typedef struct Graph//图的信息
{
    int vernum;
    int arcnum;
    VerBox vertexs[MAX_VER_NUM];
}Graph;
typedef struct QNode//队列中的数据
{
    VerBox *data;
    struct QNode *next;
}QNode;
typedef struct Queue//队列
{
    QNode *front;
    QNode *rear;
}Queue;
typedef struct CSNode//兄弟孩子结构体
{
    int data;
    struct CSNode *firstchild;
    struct CSNode *nextsibling;
}CSNode;
int Visited[MAX_VER_NUM];//标记顶点是否被访问过
Status CreateGraph(Graph *G);//创建图
int LocateVer(Graph G,char v);//顶点位置
void ShowVerAdj(Graph *G);//查看顶点的邻接点
int FirstAdjVer(Graph *G ,int v);//第一邻接点
int NextAdjVer(Graph *G ,int v,int w);//下一邻接点
void NDV(ArcBox *p,int v,int w,int *n);//递归查找下一邻接点
void InitArcBoxmark(ArcBox *p);//初始化mark的值
void DFSGraph(Graph *G);//深度优先搜索图
void DFS(Graph *G,int v);//递归深度搜索
void BFSGraph(Graph *G);//广度优先搜索图
void InitQueue(Queue *Q);//初始化队列
void EnQueue(Queue *Q,VerBox *p);//入队
Status EmptyQueue(Queue Q);//队列是否为空
Status DeQueue(Queue *Q,VerBox **p);//出队
void DFSForest(Graph *G,CSNode **T);//图G深度优先生成树
void DFSTree(Graph *G,int v,CSNode *T);//递归生成树
void InOrderTraverseTree(Graph *G,CSNode *T);//中序遍历二叉树
void PreOrderTraverseTree(Graph *G,CSNode *T);//先序遍历二叉树
void BFSForest(Graph *G,CSNode **T);//图G广度优先生成树
void Searchv1(CSNode *T,int v1,CSNode **pr);//剃归搜索顶点v1在二叉树的结点
int main()
{
    Graph G;
    CSNode *DT,*BT;
    CreateGraph(&G);
    printf("图的邻接点信息如下：\n");
    ShowVerAdj(&G);
    printf("深度优先搜索信息如下:\n");
    DFSGraph(&G);
    printf("广度优先搜索信息如下:\n");
    BFSGraph(&G);
    /*深度优先生成二叉树*/
    DFSForest(&G,&DT);
    printf("深度优先搜索生成二叉树先序遍历:\n");
    PreOrderTraverseTree(&G,DT);putchar(10);
    printf("深度优先搜索生成二叉树中序遍历:\n");
    InOrderTraverseTree(&G,DT);putchar(10);
    /*广度优先生成二叉树*/
    printf("\n");
    BFSForest(&G,&BT);
    printf("广度优先搜索生成二叉树先序遍历:\n");
    PreOrderTraverseTree(&G,BT);putchar(10);
    printf("广度优先搜索生成二叉树中序遍历:\n");
    InOrderTraverseTree(&G,BT);putchar(10);
}
Status CreateGraph(Graph *G)//创建图
{
    int i,j,k,flaginfo;
    ArcBox *pnew;
    char v1,v2,c;
    printf("请输入顶点总数,边的总数,边是否含有其它信息(例:5,6,0):");
    //scanf("%d,%d,%d",&G->vernum,&G->arcnum,&flaginfo);
    Sleep(500);
    G->vernum=13;G->arcnum=13;flaginfo=0;
    printf("%d,%d,%d\n",G->vernum,G->arcnum,flaginfo);
    for(i=0;i<G->vernum;i++)
    {
        printf("请输入第%d个顶点的值:",i+1);
        //scanf(" %c",&(G->vertexs[i].data));
        Sleep(500);
        G->vertexs[i].data='A'+i;
        printf("%c\n",G->vertexs[i].data);
        G->vertexs[i].firstedge=NULL;
    }
    /*pf=fopen("F:\\C\\data.txt","r");
    if(pf==NULL)
    {
        printf("打开文件失败!\n");
        exit(-1);
    }*/
    for(k=0;k<G->arcnum;k++)
    {

        printf("请输入第%d条边的信息:",k+1);
        //scanf(" %c %c",&v1,&v2);
        //v1=fgetc(pf);
        //c=fgetc(pf);
        //v2=fgetc(pf);
        //c=fgetc(pf);
        Sleep(500);
        v1=Data[k][0];
        v2=Data[k][1];
        printf("(%c,%c)\n",v1,v2);
        i=LocateVer(*G,v1);
        j=LocateVer(*G,v2);
        if(i>=0 && j>=0)
        {
            pnew=(ArcBox *)malloc(1*sizeof(ArcBox));
            pnew->iver=i;
            pnew->jver=j;
            pnew->ilink=G->vertexs[i].firstedge;
            G->vertexs[i].firstedge=pnew;
            pnew->jlink=G->vertexs[j].firstedge;
            G->vertexs[j].firstedge=pnew;
            pnew->mark=FALSE;
        }
        else printf("顶点%c不存在！\n",i<0?v1:v2);
    }   
    return OK;
}
int LocateVer(Graph G,char v)//顶点位置
{
    int i=-1;
    for(i=0;i<G.vernum;i++)
    {
        if(toupper(G.vertexs[i].data)==toupper(v))
        {
            return i;
        }
    }
    return -1;
}
void ShowVerAdj(Graph *G)//查看顶点的邻接点
{
    int v,w;
    ArcBox *p;
    for(v=0;v<G->vernum;v++)
    {
        printf("[%d|%c]",v,G->vertexs[v].data);
        p=G->vertexs[v].firstedge;
        for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
        {
            printf("->[%d|%c]",w,G->vertexs[w].data);   
        }
        InitArcBoxmark(p);   
        printf("\n");
    }
}
int FirstAdjVer(Graph *G ,int v)
{
    ArcBox *p;
    int w=-1;
    p=G->vertexs[v].firstedge;
    if(p->iver==v)
    {   
        w=p->jver;
        p->mark=TRUE;
    }
    else if(p->jver==v)
    {
        w=p->iver;
        p->mark=TRUE;
    }
    return w;
}
int NextAdjVer(Graph *G,int v,int w)
{
    ArcBox *p;
    int n=-1;
    p=G->vertexs[v].firstedge;
    NDV(p,v,w,&n);
    return n;
}
void NDV(ArcBox *p,int v,int w,int *n)
{
    if((p->iver==v || p->jver==v) && (p->iver!=w && p->jver!=w) &&(p->mark==FALSE))
    {
        if(p->iver==v)
        {
            *n=p->jver;
            p->mark=TRUE;
        }
        else if(p->jver==v)
        {
            *n=p->iver;
            p->mark=TRUE;
        }
    }
    else
    {
        if(p->ilink!=NULL && *n==-1)
        {
            NDV(p->ilink,v,w,n);
        }
        if(p->jlink!=NULL && *n==-1)
        {
            NDV(p->jlink,v,w,n);
        }
    }
}
void InitArcBoxmark(ArcBox *p)//初始化mark的值
{
    p->mark=FALSE;
    if(p->ilink!=NULL)
    {
        InitArcBoxmark(p->ilink);        
    }
    if(p->jlink!=NULL)
    {
        InitArcBoxmark(p->ilink);
    }
}
void DFSGraph(Graph *G)
{
    int v;
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            DFS(G,v);
        }
    }
    printf("\n");
}
void DFS(Graph *G,int v)
{   
    int w;
    Visited[v]=TRUE;
    printf("%c ",G->vertexs[v].data);
    for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
    {
        if(Visited[w]==FALSE)
        {
            DFS(G,w);
        }
    }
}
void BFSGraph(Graph *G)//广度优先搜索图
{
    int v,w,u;
    VerBox *p;
    Queue Q;
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
        InitArcBoxmark(G->vertexs[v].firstedge);
    }
    InitQueue(&Q);
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            Visited[v]=TRUE;
            printf("%c ",G->vertexs[v].data);
            EnQueue(&Q,&G->vertexs[v]);
            while(EmptyQueue(Q)==0)
            {
                DeQueue(&Q,&p);
                u=LocateVer(*G,p->data);
                for(w=FirstAdjVer(G,u);w>=0;w=NextAdjVer(G,u,w))
                {
                    
                    if(Visited[w]==FALSE)
                    {
                        printf("%c ",G->vertexs[w].data);
                        Visited[w]=TRUE;
                        EnQueue(&Q,&G->vertexs[w]);               
                    }
                }
            }
        }
    }
    printf("\n");
}
void InitQueue(Queue *Q)
{
    Q->front=Q->rear=(QNode *)malloc(1*sizeof(QNode));
    Q->front->data=NULL;
    Q->front->next=NULL;
    return;
}
void EnQueue(Queue *Q,VerBox *p)
{
    QNode *pnew;
    pnew=(QNode *)malloc(1*sizeof(QNode));
    pnew->data=p;
    Q->rear->next=pnew;
    Q->rear=pnew;
    pnew->next=NULL;
}
Status EmptyQueue(Queue Q)
{
    if(Q.rear==Q.front)
        return 1;
    else return 0;
}
Status DeQueue(Queue *Q,VerBox **p)
{
    QNode *pDe;
    if(EmptyQueue(*Q)==1)
    {
        printf("队列为空不能出队！\n");
        return ERROR;
    }
    pDe=Q->front->next;
    (*p)=pDe->data;
    Q->front->next=pDe->next;
    if(pDe==Q->rear)
    {
        Q->rear=Q->front;
    }
    free(pDe);
    return OK;
}
void DFSForest(Graph *G,CSNode **T)
{
    CSNode *p,*q;
    int v=0;
    (*T)=p=q=NULL;
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
        InitArcBoxmark(G->vertexs[v].firstedge);
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            p=(CSNode *)malloc(1*sizeof(CSNode));
            p->data=LocateVer(*G,G->vertexs[v].data);
            p->firstchild=p->nextsibling=NULL;
            if((*T)==NULL)
            {
                (*T)=p;
            }
            else
            {
                q->nextsibling=p;
            }
            q=p;
            DFSTree(G,v,p);
        }
    }
}
void DFSTree(Graph *G,int v,CSNode *T)
{
    int first,w;
    CSNode *p,*q;
    Visited[v]=TRUE;
    first=TRUE;
    for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
    {
        if(Visited[w]==FALSE)
        {
            (p)=(CSNode *)malloc(1*sizeof(CSNode));
            (p)->data=LocateVer(*G,G->vertexs[w].data);
            (p)->firstchild=NULL;
            (p)->nextsibling=NULL;
            if(first==TRUE)
            {
                (T)->firstchild=p;
                first=FALSE;
            }
            else
            {
                q->nextsibling=p;
            }
            q=p;
            DFSTree(G,w,q);
        }
    }
}
void InOrderTraverseTree(Graph *G,CSNode *T)//中序遍历二叉树
{
    if(T!=NULL)
    {
        if(T->firstchild!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }
        printf("%c ",G->vertexs[T->data].data);
        if(T->nextsibling!=NULL)
        {
            InOrderTraverseTree(G,T->nextsibling);
        }        
    }
}
void PreOrderTraverseTree(Graph *G,CSNode *T)//先序遍历二叉树
{
    if(T!=NULL)
    {

        printf("%c ",G->vertexs[T->data].data);        
        if(T->firstchild!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }
        if(T->nextsibling!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }        
    }
}
void BFSForest(Graph *G,CSNode **T)//图G广度优先生成树
{
    int v,w,first=TRUE,v1;
    CSNode *pnew,*p,*p1,*pN,*pr;
    VerBox *u;
    Queue Q;
    *T=NULL;
    InitQueue(&Q);
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
        InitArcBoxmark(G->vertexs[v].firstedge);
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            Visited[v]=TRUE;
            pnew=(CSNode *)malloc(1*sizeof(CSNode));
            pnew->data=LocateVer(*G,G->vertexs[v].data);
            pnew->firstchild=pnew->nextsibling=NULL;
            if((*T)==NULL)
            {
                (*T)=pnew;
            }
            else
            {
                p->nextsibling=pnew;   
            }
            p=pnew;
            EnQueue(&Q,&G->vertexs[v]);
            while(EmptyQueue(Q)==0)
            {
                DeQueue(&Q,&u);
                v1=LocateVer(*G,u->data);
                first=TRUE;
                pr=pN=NULL;
                Searchv1(*T,v1,&pr);
                for(w=FirstAdjVer(G,v1);w>=0;w=NextAdjVer(G,v1,w))
                {   
                    if(Visited[w]==FALSE)
                    {
                        p1=(CSNode *)malloc(1*sizeof(CSNode));
                        p1->data=LocateVer(*G,G->vertexs[w].data);
                        p1->firstchild=NULL;
                        p1->nextsibling=NULL;
                        if(first==TRUE)
                        {
                            pr->firstchild=p1;
                            first=FALSE;
                        }
                        else
                        {
                            pN->nextsibling=p1;
                        }
                        pN=p1;
                        Visited[w]=TRUE;
                        EnQueue(&Q,&G->vertexs[w]);
                    }
                }
            }
        }
    }
}
void Searchv1(CSNode *T,int v1,CSNode **pr)
{
    if(T->data==v1)   
    {
        (*pr)=T;
    }
    else
    {
        if(T->firstchild!=NULL && (*pr)==NULL)
        {
            Searchv1(T->firstchild,v1,&(*pr));
        }
        if(T->nextsibling!=NULL && (*pr)==NULL)
        {
            Searchv1(T->nextsibling,v1,&(*pr));
        }
    }
}

[此贴子已经被作者于2017-5-27 21:23编辑过]

很久没弄数据结构了~不学习一下的话一时也看不出来~~

void PreOrderTraverseTree(Graph *G,CSNode *T)//先序遍历二叉树
{
    if(T!=NULL)
    {

        printf("%c ",G->vertexs[T->data].data);        
        if(T->firstchild!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);//为什么是调用中序遍历函数？完全搞不懂意图。
        }
        if(T->nextsibling!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }        
    }
}

[此贴子已经被作者于2017-5-28 00:00编辑过]

就是这儿出问题了，犯这种小错误还没发现。

你辛苦了！

原来这问题……花些时间看看应该可以看出来~话说你在二叉树蹉跎了好些岁月了~期待你什么时候更新一下~~

辛苦什么~其实我得要去看网上选修视频~今天(已经过了0点)下午要考试了~我其实都没怎么去看~~

加油，祝你考试顺利通过！我也觉得我在树和图上蹉跎了大量的时间，洗洗睡吧！

不急，不急，慢慢来。

[此贴子已经被作者于2017-5-28 06:07编辑过]

感觉这样慢慢来能学得比牢固~现在看课时数据结构这一节就学那么一个学期~感觉在这么短的时间内很难做到精通的~按老师的学习进度来说~感觉很多东西学得很表面~没啥时间和精力深入消化~很多东西还需要自己自学和领悟的~