c++ check if two binary search trees are the same

Given the root nodes of two binary search trees. If two binary search trees are identical, print 1, otherwise print 0. Two trees are identical if they are structurally identical and have nodes with the same values.

In the above image, both tree1 and tree2 are the same.

In order to determine whether two trees are the same, we need to traverse both trees at the same time, and while traversing we need to compare the data and child nodes of the trees.

The following is a step-by-step algorithm to check if two BSTs are the same:

1. If both trees are empty, return 1.

2. Otherwise, if both trees are non-empty

-check the data of the root node (tree1-> data == tree2-> data)

-Recursively check the left subtree, that is, call sameTree(tree1-> left_subtree, tree2-> left_subtree)

-Recursively check the right subtree, that is, call sameTree(tree1-> right_subtree, tree2-> right_subtree)

- Returns 1 if the value returned in the above three steps is true.

3. Otherwise return 0 (one is empty and the other is not).

The following is the implementation of the above method:

// c++程序检查两个bst是否相同
  
#include  
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; 
}

Output:

Both BSTs are identical

This article is about the method of checking whether two binary search trees are the same Introduction, I hope it will be helpful to friends in need!

The above is the detailed content of c++ check if two binary search trees are the same. For more information, please follow other related articles on the PHP Chinese website!