数据结构
网络
关系数据库管理系统(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 次查看
