給定兩個二元搜尋樹的根節點。如果兩個二進位搜尋樹是相同的，則列印1，否則列印0.如果兩個樹在結構上相同且節點具有相同的值，則它們是相同的。
在上面的圖片中，tree1和tree2都是相同的。
為了確定兩棵樹是否相同，我們需要同時遍歷兩棵樹，並且在遍歷時我們需要比較樹木的資料和子節點。
以下是逐步演算法，以檢查兩個BST是否相同：
#1.如果兩棵樹都是空的，則回傳1。
2.否則，如果兩棵樹都是非空的
-檢查根節點的資料（tree1-> data == tree2-> data）
# -遞歸檢查左子樹，即呼叫sameTree（tree1-> left_subtree，tree2-> left_subtree）
-遞迴檢查右子樹，即呼叫sameTree（tree1-> right_subtree，tree2-> right_subtree）
-若上述三個步驟中傳回的值為true，則傳回1。
3.否則回傳0（一個是空的而另一個不是）。
以下是上述方法的實作：
// c++程序检查两个bst是否相同
#include <iostream>
using namespace std;
// BST节点
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// 创建新节点的实用程序函数
struct Node* newNode(int data)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
//函数执行顺序遍历
void inorder(Node* root)
{
if (root == NULL)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// 函数检查两个bst是否相同
int isIdentical(Node* root1, Node* root2)
{
// 检查这两棵树是否都是空的
if (root1 == NULL && root2 == NULL)
return 1;
// 如果树中的任意一个为非空，另一个为空，则返回false
else if (root1 != NULL && root2 == NULL)
return 0;
else if (root1 == NULL && root2 != NULL)
return 0;
else {
// 检查两个树的当前数据是否相等，并递归地检查左子树和右子树
if (root1->data == root2->data && isIdentical(root1->left, root2->left)
&& isIdentical(root1->right, root2->right))
return 1;
else
return 0;
}
}
// 驱动代码
int main()
{
struct Node* root1 = newNode(5);
struct Node* root2 = newNode(5);
root1->left = newNode(3);
root1->right = newNode(8);
root1->left->left = newNode(2);
root1->left->right = newNode(4);
root2->left = newNode(3);
root2->right = newNode(8);
root2->left->left = newNode(2);
root2->left->right = newNode(4);
if (isIdentical(root1, root2))
cout << "Both BSTs are identical";
else
cout << "BSTs are not identical";
return 0;
}輸出：
Both BSTs are identical
本篇文章就是關於檢查兩個二進位搜尋樹是否相同的方法介紹，希望對需要的朋友有幫助！
以上是c++檢查兩個二進位搜尋樹是否相同的詳細內容。更多資訊請關注PHP中文網其他相關文章！
