数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究树的任意两个节点之间的路径打印 | 深度优先搜索 (DFS)
为了利用深度优先搜索 (DFS) 打印树中任意两个节点之间的路径，我们将遍历树并跟踪从源节点到目标节点的路径。DFS 通过尽可能深入地遍历并回溯来探索树。我们从源节点开始 DFS，并递归地访问其子节点。在遍历过程中，我们维护一个路径变量，该变量存储从源节点到当前节点的当前路径。如果我们在遍历期间遇到目标节点，则打印路径。这种方法允许我们使用 DFS 遍历查找并打印树中任意两个节点之间的路径。
使用的方法
深度优先搜索 (DFS)
深度优先搜索 (DFS)
为了打印树中任意两个节点之间的路径，我们可以使用深度优先搜索 (DFS) 方法。DFS 从选定的节点开始，沿着每个分支尽可能深入地进行探索，然后回溯。我们从根节点开始 DFS，并遍历树直到到达目标节点。在遍历过程中，我们跟踪从根节点到当前节点的路径。一旦找到目标节点，我们就打印该路径。如果未找到目标节点，我们将回溯并继续探索其他分支，直到遇到目标节点或所有路径都已探索完毕。这种 DFS 方法有助于我们识别并打印树中任意两个节点之间的路径。
算法
从树的根节点开始。
定义一个名为 printPathDFS 的递归函数，该函数将当前节点、目标节点和一个用于存储路径的向量作为参数。
在 printPathDFS 函数内部
将当前节点添加到路径向量中。
检查当前节点是否为目标节点。如果是，则打印向量并返回。
递归地为当前节点的每个子节点调用 printPathDFS 函数。
在探索所有子节点后，从路径向量中删除当前节点。
初始化一个空向量来存储路径。
调用 printPathDFS 函数，从根节点开始，并传递目标节点和路径向量。
如果在 DFS 遍历后未找到目标节点，则打印一条消息指示路径不存在。
示例
#include <iostream>
#include <vector>
using namespace std;
struct Element {
int val;
vector<Element*> children;
Element* parent;
Element(int value) {
val = value;
parent = nullptr;
}
};
bool printPathDFS(Element* currentElement, int targetElement, vector<int>& path) {
path.push_back(currentElement->val);
if (currentElement->val == targetElement) {
for (int i = 0; i < path.size(); i++) {
cout << path[i] << " ";
}
cout << endl;
return true;
}
for (Element* child : currentElement->children) {
if (printPathDFS(child, targetElement, path)) {
return true;
}
}
path.pop_back();
return false;
}
void printPathBetweenElements(Element* startElement, Element* endElement) {
vector<int> path;
if (startElement != nullptr && endElement != nullptr) {
printPathDFS(startElement, endElement->val, path);
} else {
cout << "One or both elements not found in the tree." << endl;
}
}
int main() {
// Create a sample tree
Element* root = new Element(1);
Element* element2 = new Element(2);
Element* element3 = new Element(3);
Element* element4 = new Element(4);
Element* element5 = new Element(5);
Element* element6 = new Element(6);
root->children.push_back(element2);
root->children.push_back(element3);
element2->parent = root;
element3->parent = root;
element2->children.push_back(element4);
element4->parent = element2;
element3->children.push_back(element5);
element3->children.push_back(element6);
element5->parent = element3;
element6->parent = element3;
int startElement = 21;
int endElement = 35;
Element* start = nullptr;
Element* end = nullptr;
// Find the start and end elements in the tree
for (Element* child : root->children) {
if (child->val == startElement) {
start = child;
}
if (child->val == endElement) {
end = child;
}
}
printPathBetweenElements(start, end);
return 0;
}
输出
One or both elements not found in the tree.
结论
本文主要介绍了如何使用深度优先搜索 (DFS) 方法打印树中任意两个节点之间的路径。详细解释了 DFS 算法，阐述了遍历树和查找路径的步骤。给出了 C 语言的代码实现，展示了修改后的 TreeNode 结构以及 DFS 遍历和打印路径的函数。文章最后展示了程序的输出，并强调了 DFS 在识别和打印树中节点之间路径的便利性。
566 次浏览
