在 C++ 中比较两个 BST 的节点
Comparing nodes of two BSTs in C++
我需要将一个 BST 的每个节点与另一个 BST 的所有节点进行比较。
类似于您在数组中进行比较的方式:
string arr[10];
string arr2[10];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
compare(arr[j], arr2[i]);
}
}
但是您在 bst1 中遍历的不是外部 for 循环,而是在 bst2 中遍历内部 for 循环。然后将 bst1 的节点与 bst2 的所有节点进行比较,然后移动到 bst1 的下一个节点并将其与 bst2 的所有节点进行比较,依此类推
我似乎无法理解如何实现遍历。任何帮助将不胜感激
想法是在 Tree1
的根节点上调用 traverse
,并将其中的每个节点传递给另一个函数 compare
,该函数在 [的根节点上调用=14=]并将传递的节点与其中的每个节点进行比较。
#include <iostream>
struct Node
{
int val;
Node *left, *right;
};
void compare(Node *curr2, Node *curr1)
{
if (curr2 == nullptr)
return;
compare(curr2->left, curr1);
if (curr2->val == curr1->val) // replace with your comparison function
cout << "Match found for " << curr1->val << endl;
compare(curr2->right, curr1);
}
void traverse(Node *curr1, Node *root2)
{
if (curr1 == nullptr)
return;
traverse(curr1->left, root2);
compare(root2, curr1);
traverse(curr1->right, root2);
}
int main()
{
Node *root1, *root2;
traverse(root1, root2);
}
我需要将一个 BST 的每个节点与另一个 BST 的所有节点进行比较。
类似于您在数组中进行比较的方式:
string arr[10];
string arr2[10];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
compare(arr[j], arr2[i]);
}
}
但是您在 bst1 中遍历的不是外部 for 循环,而是在 bst2 中遍历内部 for 循环。然后将 bst1 的节点与 bst2 的所有节点进行比较,然后移动到 bst1 的下一个节点并将其与 bst2 的所有节点进行比较,依此类推
我似乎无法理解如何实现遍历。任何帮助将不胜感激
想法是在 Tree1
的根节点上调用 traverse
,并将其中的每个节点传递给另一个函数 compare
,该函数在 [的根节点上调用=14=]并将传递的节点与其中的每个节点进行比较。
#include <iostream>
struct Node
{
int val;
Node *left, *right;
};
void compare(Node *curr2, Node *curr1)
{
if (curr2 == nullptr)
return;
compare(curr2->left, curr1);
if (curr2->val == curr1->val) // replace with your comparison function
cout << "Match found for " << curr1->val << endl;
compare(curr2->right, curr1);
}
void traverse(Node *curr1, Node *root2)
{
if (curr1 == nullptr)
return;
traverse(curr1->left, root2);
compare(root2, curr1);
traverse(curr1->right, root2);
}
int main()
{
Node *root1, *root2;
traverse(root1, root2);
}