資料結構
網路
關係資料庫管理系統 (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 次瀏覽
