二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）
深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。
DFS:ABDECFG
BFS:ABCDEFG
DFS实现：
数据结构：栈
父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可
BFS实现：
数据结构：队列
父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可
#include <iostream>#include <stdlib.h>#include <malloc.h>#include <Stack>#include <Queue>using namespace std;typedef struct Node {char data;struct Node *lchild;struct Node *rchild;} *Tree;//Tree 是一个node指针的类型定义int index = 0; //全局索引变量//二叉树构造器,按先序遍历顺序构造二叉树//无左子树或右子树用'#'表示void treeNodeConstructor(Tree &root, char data[]){char e = data[index++];if(e == '#'){root = NULL;}else{root = (Node *)malloc(sizeof(Node));root->data = e;treeNodeConstructor(root->lchild, data); //递归构建左子树treeNodeConstructor(root->rchild, data); //递归构建右子树}}//深度优先遍历void depthFirstSearch(Tree root){stack<Node *> nodeStack; //使用C++的STL标准模板库nodeStack.push(root);Node *node;while(!nodeStack.empty()){node = nodeStack.top();cout<<node->data;//遍历根结点nodeStack.pop();if(node->rchild){nodeStack.push(node->rchild); //先将右子树压栈}if(node->lchild){nodeStack.push(node->lchild); //再将左子树压栈}}}//广度优先遍历void breadthFirstSearch(Tree root){queue<Node *> nodeQueue; //使用C++的STL标准模板库nodeQueue.push(root);Node *node;while(!nodeQueue.empty()){node = nodeQueue.front();nodeQueue.pop();cout<<node->data;//遍历根结点if(node->lchild){nodeQueue.push(node->lchild); //先将左子树入队}if(node->rchild){nodeQueue.push(node->rchild); //再将右子树入队}}}int main() {//上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树char data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'};Tree tree;treeNodeConstructor(tree, data);printf("深度优先遍历二叉树结果: ");depthFirstSearch(tree);printf("\n\n广度优先遍历二叉树结果: ");breadthFirstSearch(tree);return 0;}
如果觉得《二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）》对你有帮助，请点赞、收藏，并留下你的观点哦！
