当前位置: 首页 > news >正文

数据结构——深度优先搜索与广度优先搜索的实现

————————————本栏目旨在交流计算机知识,欢迎交流指正!———————————

        上一章,我们介绍了深度优先搜索(dfs)与广度优先搜索(bfs)的概念,这一张,我们将会用动态存储的方式来实现它。

如图所示,今天我们将用此图来作为范本实现我们的搜索:

首先,让我们回忆一下三大基础遍历方式:

先序遍历:ABCDEFGHK

中序遍历:BDCAEHGKF

后序遍历:DCBHKGFEA

我们这里将会介绍基础递归法来实现这三种遍历,但是在这之前,我们得先建树:

        首先,我们先书写.h文件里的外置引用函数与树节点和树头:

typedef int Element;
// 树的节点结构
typedef struct _tree_node {Element data;struct _tree_node *left;struct _tree_node *right;
} TreeNode;// 二叉树的树头
typedef struct {TreeNode *root;int count;
} BinaryTree;BinaryTree *createBinaryTree(TreeNode *root);
void releaseBinaryTree(BinaryTree *tree);TreeNode *createTreeNode(Element e);
void insertBinaryTree(BinaryTree *tree, TreeNode *parent, TreeNode *left, TreeNode *right);
void visitTreeNode(const TreeNode *node);void preOrderBTree(const BinaryTree *tree);
void inOrderBTree(const BinaryTree* tree);
void postOrderBTree(const BinaryTree* tree);
void levelOrderBTree(const BinaryTree *tree);void preOrderBtreeNoRecursion(const BinaryTree *tree);
void inOrderBtreeNoRecursion(const BinaryTree *tree);

###输出呈现函数###

void visitTreeNode(const TreeNode* node) {if (node)printf("\t%c", node->data);
}

 ###初始化建树的函数###

BinaryTree *createBinaryTree(TreeNode *root) {BinaryTree *tree = malloc(sizeof(BinaryTree));if (tree == NULL) {fprintf(stderr, "tree malloc failed!\n");return NULL;}if (root) {tree->root = root;tree->count = 1;} else {tree->root = NULL;tree->count = 0;}return tree;
}
//树头的建立TreeNode *createTreeNode(Element e) {TreeNode *node = malloc(sizeof(TreeNode));node->data = e;node->left = node->right = NULL;return node;
}
//节点的建立

###树的赋值插入函数###

void insertBinaryTree(BinaryTree* tree, TreeNode* parent, TreeNode* left, TreeNode* right) {if (tree && parent) {parent->left = left;parent->right = right;if (left) {tree->count++;}if (right) {tree->count++;}}
}

1、先序遍历:

        先序遍历讲究一个单边走到头再返回,于是我们可以将输出段放在递归接口之前,确保完整走完一边子树再走另一边。

        

static void preOrderNode(const TreeNode *node) {if (node) {visitTreeNode(node);preOrderNode(node->left);preOrderNode(node->right);}
}

2、中序遍历:

        中序遍历讲究一个“V”字型走向遍历,所以输出段应该放在左子树遍历与右子树遍历之间,在主体“V”上走过小“V”。

static void inOrderNode(const TreeNode *node) {if (node) {inOrderNode(node->left);visitTreeNode(node);inOrderNode(node->right);}
}

 3、后序遍历:

        后序遍历讲究起于微末,终于殿堂,瓮中捉鳖。先把子树从左到右从下到上从叶子结点开始遍历完毕,最后再变量根节点,所以当左子树和右子树递归完毕后才能输出。

static void postOrderNode(const TreeNode *node) {if (node) {postOrderNode(node->left);postOrderNode(node->right);visitTreeNode(node);}
}
//集成前、中、后序遍历
void preOrderBTree(const BinaryTree* tree) {preOrderNode(tree->root);printf("\n");
}void inOrderBTree(const BinaryTree* tree) {inOrderNode(tree->root);printf("\n");
}void postOrderBTree(const BinaryTree* tree) {postOrderNode(tree->root);printf("\n");
}

        好了,温习过基础深度遍历方法后,我们来介绍广度优先遍历,所谓广度优先遍历就是一层一层的遍历,不再追求走到叶子结点,而是从左到右一步步走完,所以,广度优先遍历多被用于寻找最短路的题目中。如何实现呢?这里我们尝试使用队列的知识:如果满足就入队,并且这一层入队完毕后把所有上一层次的点出队。这样就可以形成一层层的遍历了。

上代码:

/* 广度遍历* 1. 引入一个任务队列,先把根节点入队* 2. 从任务队列中,取出一个节点,处理他(访问)* 3. 如果2步的节点,有左那么就入队,有右那么就入队* 4. 重复第2步*/
void levelOrderBTree(const BinaryTree* tree) {// 申请一个任务队列,用顺序存储,循环队列,队列里每个元素应该是节点的地址
#define MaxQueueSize 8TreeNode* queue[MaxQueueSize];int front, rear;// 初始化系统front = rear = 0;queue[rear] = tree->root;rear = (rear + 1) % MaxQueueSize;// 开始循环系统处理事务while (rear != front) {TreeNode* node = queue[front];front = (front + 1) % MaxQueueSize;visitTreeNode(node);if (node->left) {queue[rear] = node->left;rear = (rear + 1) % MaxQueueSize;}if (node->right) {queue[rear] = node->right;rear = (rear + 1) % MaxQueueSize;}}
}

好了,介绍完深度优先遍历与广度优先遍历的写法后,我们还有一个拓展知识点——仔细思考一下,如果使用深度优先遍历,如果层数太多我们在写一个搜索时会时常遇到加载慢的问题,而如果我们使用记忆化搜索,随着数据量的增多,不免会积累海量的数据。下面,我们将介绍一种不基于递归的深度优先搜索写法,并用栈来实现。

        说到栈,我们回忆之前栏目中的栈结构:先进后出,后进先出,所以,假设我们要实现先序遍历,那么我们先出栈的必须是左子树,所以先压右子树进栈,再压左子树。最后出栈时,先出左子树,后出右子树。大体思路如下:

/* 非递归实现先序遍历,基本思路:* 先序的结果是当前节点、再左节点、最后右节点。把栈当做任务的暂存空间,* 先压右节点,再压左节点,一旦弹栈,出现的是左节点。* 基本步骤:* 1. 初始化部分*		将根节点压栈* 2. 循环处理任务部分*	2.1 弹栈,访问弹出来的节点,判断节点有右先压右,有左再压左,保证先右后左*	2.2 循环出栈,直到栈内无元素*/
void preOrderBtreeNoRecursion(const BinaryTree* tree) {ArrayStack stack;initArrayStack(&stack);pushArrayStack(&stack, tree->root);TreeNode *node;while (!isEmptyArrayStack(&stack)) {node = getTopArrayStack(&stack);popArrayStack(&stack);visitTreeNode(node);if (node->right) {pushArrayStack(&stack, node->right);}if (node->left) {pushArrayStack(&stack, node->left);}}
}/* 以根节点开始,整条左边进栈,从栈中弹出节点,开始访问* 如果这个节点有右孩子,把右孩子当做新节点* 再次整条边进栈,再弹栈*/
void inOrderBtreeNoRecursion(const BinaryTree* tree) {ArrayStack stack;initArrayStack(&stack);// pushArrayStack(&stack, tree->root);TreeNode *node = tree->root;while (!isEmptyArrayStack(&stack) || node) {if (node) {pushArrayStack(&stack, node);node = node->left;} else {node = getTopArrayStack(&stack);popArrayStack(&stack);visitTreeNode(node);node =node->right;}}
}

希望能对你有所帮助!

http://www.lryc.cn/news/583646.html

相关文章:

  • [附源码+数据库+毕业论]基于Spring Boot+mysql+vue结合内容推荐算法的学生咨询系统
  • RabbitMQ 4.1.1-Local random exchange体验
  • C++如何进行性能优化?
  • 19-C#静态方法与静态类
  • 【WEB】Polar靶场 21-25题 详细笔记
  • 从0开始学习R语言--Day42--LM检验
  • 异地组网
  • 数据分析框架和方法
  • Mac电脑,休眠以后,发现电量一直在减少,而且一个晚上,基本上是没了,开机都需要插电源的简单处理
  • 卫星通信终端天线的5种对星模式之二:功率检测型载波跟踪
  • 【PyTorch】PyTorch中数据准备工作(AI生成)
  • 深度学习——损失函数
  • Hexo + Butterfly + Vercel 完整个人Blog部署指南
  • Flask3.1打造极简CMS系统
  • 自动化Trae Apollo参数解释的批量获取
  • 股权结构解析
  • SpringBoot集成文件 - 大文件的上传(异步,分片,断点续传和秒传)
  • 专题一_双指针_查找总价格为目标值的两个商品
  • 拼多多正在错失即时零售?
  • ECR仓库CloudFormation模板完整指南
  • 【每日算法】专题六_模拟
  • WPF学习笔记(27)科学计算器
  • 1、专栏介绍以及目录
  • 周立功汽车软件ZXDoc深度解析:新能源汽车开发新基建的破局之道
  • eggNOG数据库注释文件
  • 以太网基础④IP 协议介绍与 IP 校验和算法实现
  • 【Linux网络编程】Socket - TCP
  • Java-----韩顺平单例设计模式学习笔记
  • swiglu 激活函数学习笔记
  • Java垃圾收集机制Test1