[Algorithms]二叉树遍历方法与代码实现

2023-09-25 19:05:25

[Algorithms]二叉树、图遍历方法与代码实现

1. 二叉树遍历方法

首先，是本文使用二叉树结构的一个声明。

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

一、前序遍历

原理：若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。

/* 前序遍历递归 */
void PreOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	printf("%c",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

二、中序遍历

原理：若二叉树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。

/* 中序遍历递归 */
void InOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	InOrderTraverse(T->lchild);
	printf("%c",T->data);
	InOrderTraverse(T->rchild);
}

三、后序遍历

原理：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nMqimKvN-1645500271630)(https://lkk2lqq.com/picture/后序遍历.png)]

/* 后序遍历递归 */
void PostOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c",T->data);
}

四、层序遍历

原理：若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，从左到右的顺序对结点逐个访问。

2. 图遍历方法

一、深度优先遍历(DFS)

邻接矩阵的遍历算法

/* 图的声明->邻接矩阵方式：可能内存的使用率低 */
#define MAXVEX 100
#define INFINITY 65535
typedef struct
{
    
	char vexs[MAXVEX]; /*顶点表*/
    int arc[MAXVEX][MAXVEX]; /*邻接矩阵，可看做边表*/
    int numVertexes,numEdges; /*图中当前的顶点数和边数*/
}MGraph;


bool visited[MAX];
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G,int i)
{
    int j;
    visited[i]=true;
    printf("%c",G.vexs[i]);
    for(j=0;j<G.numVertexes;j++)
    {
        if(G.arc[i][j] == 1 && !visited[j])
        {
            DFS(G,j);
        }
    }
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
    int i;
    for(i = 0;i < G.numVertexes;i++ )
    {
        visited[i] = false;
    }
    for(i = 0;i < G.numVertexes;i++)
    {
        if(!visited[i])
            DFS(G,i);
    }
}

邻接表的遍历算法

/* 图的声明->邻接表方式：链式存储，结构复杂 */
typedef struct EdgeNode /*边表结点*/
{
    int adjvex;
    int weight; /*权值非网图可以不需要*/
    struct EdgeNode *next;/*链域指向下一个邻接点*/
}EdgeNode;

typedef struct VertexNode /*顶点表结点*/
{
    int data;/*顶点域*/
    EdgeNode *firstedge;/*边表头指针*/
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes,numEdges; /*图中当前顶点数和边数*/
}GraphAdjList；

/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL,int i)
{
    EdgeNode *p;
    visited[i]=true;
    printf("%c",GL->adjlist[i].data);
    while(p)
    {
        if(!visited[p->adjvex])/*如果没走过这条路，那就走到下一个顶点*/
            DFS(GL,p->adjvex);
        p = p->next;
    }
}
/* 邻接表的深度遍历操作 */
void DFSTraverse(MGraph G)
{
    int i;
    for(i = 0;i < GL->numVertexes;i++ )
    {
        visited[i] = false;
    }
    for(i = 0;i < G->numVertexes;i++)
    {
        if(!visited[i])
            DFS(GL,i);
    }
}

二、广度优先遍历(BFS)

邻接矩阵的广度遍历算法

为了方便，直接把前文提到的声明放到这里，比较直观。

/* 图的声明->邻接矩阵方式：可能内存的使用率低 */
#define MAXVEX 100
#define INFINITY 65535
typedef struct
{
    
	char vexs[MAXVEX]; /*顶点表*/
    int arc[MAXVEX][MAXVEX]; /*邻接矩阵，可看做边表*/
    int numVertexes,numEdges; /*图中当前的顶点数和边数*/
}MGraph;

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G)
{
    int i,j;
    Queue Q;
    for(i = 0;i < G.numVertexes; i++)
    {
        visited[i] = false;
    }
    InitQueue(&Q);/*初始化辅助队列*/
    for(i = 0;i < G.numVertexes; i++)
    {
        if(!visited[i])
        {
            visited[i]=true;
            printf("%c",G.vexs[i]);
            EnQueue(&Q,i);
            while(!QueueEmpty(Q))
            {
                DeQueue(&Q,&i); /* 将队中元素出队列，赋值给i */
            	for(j = 0;j < G.numVertexes; j++)
                {
                    /* 若其他顶点与当前顶点存在边且未访问过 */
                    if(G.arc[i][j] == 1 && !visited[j])
                    {
                        visited[j]=true;
                        printf("%c",G.vexs[j]);
                        EnQueue(&Q,j);
                    }
                }
            }
            
        }
    }
}

邻接表的广度遍历算法

/* 图的声明->邻接表方式：链式存储，结构复杂 */
typedef struct EdgeNode /*边表结点*/
{
    int adjvex;
    int weight; /*权值非网图可以不需要*/
    struct EdgeNode *next;/*链域指向下一个邻接点*/
}EdgeNode;

typedef struct VertexNode /*顶点表结点*/
{
    int data;/*顶点域*/
    EdgeNode *firstedge;/*边表头指针*/
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes,numEdges; /*图中当前顶点数和边数*/
}GraphAdjList；

void BFSTraverse(GraphAdjList GL)
{
    int i;
    EdgeNode *p;
    Queue Q;
    for(i = 0; i < GL->numVertexes; i++)
    {
        visited[i]=false;
    }
    InitQueue(&Q);
    for(i = 0 ; i < GL->numVertexes; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            printf("%c",GL->adjList[i].data);
            EnQueue(&Q,i);
            while(!QueueEmpty(Q))
            {
                DeQueue(&Q,&i);
                /*以下代码参考邻接矩阵的话很好理解*/
                p = GL->adjList[i].firstedge; /*找到当前顶点边表链表头指针*/
                while(p)
                {
                    if(!visited[p->adjvex])
                    {
                        visited[p->adjvex] = true;
                        printf("%c",GL->adjList[p->adjvex].data);
                        EnQueue(&Q,p->adjvex);
                    }
                    p = p->next;
                }
            }
        }
    }
}

码农公寓