資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究統計權重字串中不包含任何重複字元的樹的節點數
為了準備深度優先搜尋(DFS)遍歷，識別樹的中心節點，其權重字串不包含任何重複字元。我們從根節點開始遍歷每個節點，跟蹤我們已經在權重字串中遇到的字元。如果遇到已經存在於集合中的字元，我們就停止沿該路徑向下導航。對於我們在遍歷過程中經過的每個節點，我們增加一個計數變數。DFS遍歷完成後，計數變數將表示樹中權重字串不包含任何重複字元的節點數。
使用的方法
深度優先搜尋(DFS)
遞迴方法
深度優先搜尋(DFS)
深度優先搜尋 (DFS) 演算法用於更深入地遍歷樹。在檢查權重字串不包含重複字元的樹的節點時，DFS 從根節點開始，儘可能深入地探索每個分支，必要時回溯。在遍歷過程中，維護一個字元集合來檢查重複字元。如果發現重複字元，則停止該方向的遍歷。DFS 透過對每個訪問過的節點遞增一個計數變數，有效地計算樹中滿足條件的節點數。
演算法
從樹的根節點開始。
將計數變數初始化為 0。
初始化一個集合來跟蹤已訪問的字元。
執行樹的 DFS 遍歷。
如果當前節點無效，則返回。
將當前節點的字元新增到已訪問字元集合中。
如果該字元已存在於集合中，則停止沿該路徑向下導航。
否則，將計數變數加 1。
遞迴遍歷當前節點的左子節點。
遞迴遍歷當前節點的右子節點。
DFS 遍歷完成後，計數變數將包含樹中權重字串不包含重複字元的節點數。
返回計數。
示例
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
// Global variables
int count = 0;
set<char> purgeSet;
// Structure representing a hub node
struct Hub {
char character;
Hub* child1;
Hub* child2;
};
// Recursive DFS traversal function
void traverseHub(Hub* hub) {
if (hub == nullptr)
return;
purgeSet.insert(hub->character);
if (purgeSet.count(hub->character) > 1)
return;
count++;
traverseHub(hub->child1);
traverseHub(hub->child2);
}
int main() {
// Create a sample tree
Hub* root = new Hub{'A', nullptr, nullptr};
root->child1 = new Hub{'B', nullptr, nullptr};
root->child2 = new Hub{'C', nullptr, nullptr};
root->child1->child1 = new Hub{'D', nullptr, nullptr};
root->child1->child2 = new Hub{'E', nullptr, nullptr};
root->child2->child1 = new Hub{'F', nullptr, nullptr};
root->child2->child2 = new Hub{'G', nullptr, nullptr};
// Traverse the tree
traverseHub(root);
// Output the count
cout << "Number of hubs with unique characters: " << count << endl;
// Clean up the allocated memory
// ...
return 0;
}
輸出
Number of hubs with unique characters: 7
遞迴方法
遞迴方法涉及執行遞迴操作。從一個節點和一個已訪問字元集合開始。如果節點無效，則返回 0。檢查當前節點的字元是否已在已訪問字元集合中。如果是，則返回 0。否則：將字元新增到集合中。遞迴地計算左子樹和右子樹中滿足條件的節點數，並將更新後的已訪問字元集合傳遞下去。將計數加 1 並返回兩個子樹計數的總和。這種方法遞迴地遍歷每個節點，檢查重複項，並且僅當未找到重複項時才增加計數，確保權重字串不包含任何重複字元。
演算法
從一個節點和一個已訪問字元集合開始。
如果節點無效，則返回 0。
檢查當前節點的字元是否已存在於已訪問字元集合中。
如果存在重複字元，則返回 0。
否則，將字元新增到已訪問字元集合中。
遞迴呼叫左子樹的計算，傳遞更新後的已訪問字元集合，並存儲結果。
遞迴呼叫右子樹的計算，傳遞更新後的已訪問字元集合，並存儲結果。
將計數加 1。
返回從兩個子樹獲得的計數之和，加上增加的計數。
示例
#include <iostream>
#include <unordered_set>
struct Node {
char data;
Node* left;
Node* right;
};
Node* createNode(char data) {
Node* newNode = new Node();
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
int countNodes(Node* node, std::unordered_set<char>& encounteredChars) {
if (node == nullptr)
return 0;
if (encounteredChars.find(node->data) != encounteredChars.end())
return 0;
encounteredChars.insert(node->data);
int leftCount = countNodes(node->left, encounteredChars);
int rightCount = countNodes(node->right, encounteredChars);
return leftCount + rightCount + 1;
}
int main() {
Node* root = createNode('A');
root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');
root->right->right = createNode('F');
std::unordered_set<char> encounteredChars;
int totalCount = countNodes(root, encounteredChars);
std::cout << "Total number of nodes: " << totalCount << std::endl;
return 0;
}
輸出
Total number of nodes: 6
結論
本文提供了一種演算法方法來計算樹中權重字串不包含任何重複字元的節點數。它介紹了一個逐步過程，使用深度優先搜尋 (DFS) 遍歷來有效地遍歷樹並維護一個已訪問字元集合。透過檢查重複字元併為每個合格節點遞增計數變數，該演算法精確地計算樹中指定的節點數。C語言中的程式碼示例演示了該演算法在諸如計數節點、檢查重複字元和查詢二叉樹高度等任務中的各種實現。
53 次檢視
