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

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

news 2025/7/10 17:30:45

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

上一章，我们介绍了深度优先搜索（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