DFS和BFS在二叉树中的应用
文章目录一、前言二、二叉树
1.树的定义2.树的初始化与建立 三、堆栈
1.栈的定义2.栈的初始化3.入栈和出栈操作 四、队列
1.队列的定义2.队列的初始化3.入队和出队操作 五、DFS六、BFS七、代码以及运行结果
1.完整代码2.运行结果 八、总结评价
一、前言
在学习完深度优先搜索和广度优先搜索后，结合堆栈与队列的性质，在二叉树中实现深度优先遍历（即前序遍历）和广度优先遍历（即层次遍历）。共涉及一下知识点：
二叉树的定义与建立（初始化，插入节点）堆栈的定义与建立（初始化，入栈，出栈）队列的定义与建立（初始化，入队，出队）DFS的实现BFS的实现
本篇文章综合性比较强，涉及内容比较多，请仔细学习。
二、二叉树
二叉树是树的一种，有且只有一个根节点，出根节点之外有两个互不相交的子集，称为左子树和右子树。两个子树本身又都是二叉树。
1.树的定义需要定义一个二叉树的节点类型，包括节点值，以及节点的左孩子和右孩子。
typedef struct TreeNode *BinTree;
struct TreeNode
{
int Data;
BinTree LeftChild;
BinTree RightChild;
};
2.树的初始化与建立
建立一棵二叉树，首先需要分配空间，其次将节点值输入并赋值，最后创建并更新其左右子树，选择递归的方式建立。
BinTree BuildBinTree()
{
int ch;
scanf("%d",&ch);
BinTree T;
T=(BinTree)malloc(sizeof(struct TreeNode));
if(ch==-1)//如果输入为-1，表明节点为空
{
T=NULL;
return T;
}
else{
T->Data=ch;
printf("input %d LeftChild Value:",ch);
T->LeftChild=BuildBinTree();
printf("input %d RightChild Value:",ch);
T->RightChild=BuildBinTree();
}
return T;
}
三、堆栈
栈是限定仅在表尾进行插入和删除操作的线性表。又称为先进后出的线性表。
1.栈的定义建立一个堆栈，首先要开辟一定空间的数组，并且定义一个栈顶指针。
typedef struct SNode *Stack;
struct SNode{
int Data[MAXSIZE];
int top;
};
2.栈的初始化
分配一个堆栈类型的空间，将栈顶指针指向-1
Stack initS()
{
Stack S;
S=(Stack)malloc(sizeof(struct SNode));
S->top=-1;
return S;
}
3.入栈和出栈操作
入栈首先判断堆栈是否已满，如果没满则将数据压入栈，栈顶指针向后移动一位。
出栈首先判断堆栈是否为空，如果不空则将数据弹出栈，栈顶指针向前移动一位。
void Push(Stack Ptrs,int x)
{
if(Ptrs->top==MAXSIZE-1) printf("stack is full!n");
else Ptrs->Data[++(Ptrs->top)]=x;
}
int Pop(Stack Ptrs)
{
if(Ptrs->top==-1) printf("stack is empty!");
else return Ptrs->Data[(Ptrs->top)--];
}
四、队列
与栈相反，队列是一种先进先出的线性表。只允许在表的一端进行插入元素，在另一端删除元素。
1.队列的定义首先开一个数组，其次设置一个队首和队尾标记。
typedef struct QNode
{
int Data[MAXSIZE];
int front;
int rear;
}*Queue;
2.队列的初始化
开辟空间，将队首队尾标记置0。
Queue initQ()
{
Queue Q;
Q=(Queue)malloc(sizeof(struct QNode));
Q->front=0;
Q->rear=0;
return Q;
}
3.入队和出队操作
判断队列是否已满，如果不满则更新队尾标记，将数据存入队列
判断队列是否为空，如果不空则更新队首标记，将数据弹出队列
void AddQ(Queue PtrQ,int x)
{
if((PtrQ->rear+1)%MAXSIZE==PtrQ->front) printf("Queue is full!n");
PtrQ->rear=(PtrQ->rear+1)%MAXSIZE;
PtrQ->Data[PtrQ->rear]=x;
}
int DeleteQ(Queue PtrQ)
{
if(PtrQ->front==PtrQ->rear) printf("Queue is empty!n");
else{
PtrQ->front=(PtrQ->front+1)%MAXSIZE;
return PtrQ->Data[PtrQ->front];
}
}
五、DFS
深度优先搜索遍历即类似于树的先序遍历，是树的先序遍历的推广。
思路为：
从根节点出发，访问根节点，将根节点入栈左子树不为空，则将根节点弹出，访问左子树节点，重复第一步操作右子树不为空，则将根节点弹出，访问右子树节点，重复第一步操作直至所有节点都访问过
具体代码实现如下：
void DFS(BinTree T,Stack S)
{
if(T==NULL) return;
Push(S,T->Data);
printf("%d ",Pop(S));
DFS(T->LeftChild,S);
DFS(T->RightChild,S);
}
六、BFS
广度优先搜索遍历类似于树的层次遍历。
思路为：
一层一层的访问二叉树首先访问根节点其次访问其左右子树节点再次对其左右子树做第一步操作直至每一层都遍历完成
具体代码如下：
int flag=0;//根节点标记
void BFS(BinTree T,Queue Q)
{
if(T==NULL) return;
if(!flag)//根节点
{
AddQ(Q,T->Data);
printf("%d ",DeleteQ(Q));
flag=1;
}
//左右孩子节点
AddQ(Q,T->LeftChild->Data);
printf("%d ",DeleteQ(Q));
AddQ(Q,T->RightChild->Data);
printf("%d ",DeleteQ(Q));
BFS(T->LeftChild,Q);
BFS(T->RightChild,Q);
}
七、代码以及运行结果
1.完整代码
#include2.运行结果#include #define MAXSIZE 100 typedef struct TreeNode *BinTree; struct TreeNode { int Data; BinTree LeftChild; BinTree RightChild; }; typedef struct SNode *Stack; struct SNode{ int Data[MAXSIZE]; int top; }; typedef struct QNode { int Data[MAXSIZE]; int front; int rear; }*Queue; BinTree BuildBinTree() { int ch; scanf("%d",&ch); BinTree T; T=(BinTree)malloc(sizeof(struct TreeNode)); if(ch==-1)//如果输入为-1，表明节点为空 { T=NULL; return T; } else{ T->Data=ch; printf("input %d LeftChild Value:",ch); T->LeftChild=BuildBinTree(); printf("input %d RightChild Value:",ch); T->RightChild=BuildBinTree(); } return T; } Stack initS() { Stack S; S=(Stack)malloc(sizeof(struct SNode)); S->top=-1; return S; } void Push(Stack Ptrs,int x) { if(Ptrs->top==MAXSIZE-1) printf("stack is full!n"); else Ptrs->Data[++(Ptrs->top)]=x; } int Pop(Stack Ptrs) { if(Ptrs->top==-1) printf("stack is empty!"); else return Ptrs->Data[(Ptrs->top)--]; } Queue initQ() { Queue Q; Q=(Queue)malloc(sizeof(struct QNode)); Q->front=0; Q->rear=0; return Q; } void AddQ(Queue PtrQ,int x) { if((PtrQ->rear+1)%MAXSIZE==PtrQ->front) printf("Queue is full!n"); PtrQ->rear=(PtrQ->rear+1)%MAXSIZE; PtrQ->Data[PtrQ->rear]=x; } int DeleteQ(Queue PtrQ) { if(PtrQ->front==PtrQ->rear) printf("Queue is empty!n"); else{ PtrQ->front=(PtrQ->front+1)%MAXSIZE; return PtrQ->Data[PtrQ->front]; } } void DFS(BinTree T,Stack S) { if(T==NULL) return; Push(S,T->Data); printf("%d ",Pop(S)); DFS(T->LeftChild,S); DFS(T->RightChild,S); } int flag=0; void BFS(BinTree T,Queue Q) { if(T==NULL) return; if(!flag)//根节点 { AddQ(Q,T->Data); printf("%d ",DeleteQ(Q)); flag=1; } //左右孩子节点 AddQ(Q,T->LeftChild->Data); printf("%d ",DeleteQ(Q)); AddQ(Q,T->RightChild->Data); printf("%d ",DeleteQ(Q)); BFS(T->LeftChild,Q); BFS(T->RightChild,Q); } int main() { Stack S=initS(); Queue Q=initQ(); BinTree T=BuildBinTree(T); printf("DFS:"); DFS(T,S); printf("n"); printf("BFS:"); BFS(T,Q); return 0; }
建立一课二叉树，如下图：
以下为遍历结果：
八、总结评价
深度优先搜索和广度优先搜索是各类算法比赛经常出现的考点，因此，对其的熟练掌握显得尤为重要。
本篇文章树为载体，结合数据结构一书中的基本知识，对DFS和BFS进行讲解和编写，不仅在于帮助大家实现对两种搜索算法的理解，更是对数据结构基础的夯实与打磨。
有问题欢迎各位大佬指出
算法系列将持续更新，欢迎关注，一起学习
