c++ vérifie si deux arbres de recherche binaires sont identiques

Étant donné les nœuds racines de deux arbres de recherche binaires. Si deux arbres de recherche binaires sont identiques, imprimez 1, sinon imprimez 0. Deux arbres sont identiques s'ils sont structurellement identiques et ont des nœuds avec les mêmes valeurs.

Dans l'image ci-dessus, tree1 et tree2 sont identiques.

Afin de déterminer si deux arbres sont identiques, nous devons parcourir les deux arbres en même temps, et lors du parcours, nous devons comparer les données et les nœuds enfants des arbres.

Ce qui suit est un algorithme étape par étape pour vérifier si deux BST sont identiques :

Si les deux arbres sont vides, renvoyez 1.

2. Sinon, si les deux arbres ne sont pas vides

-vérifiez les données du nœud racine (tree1-> data == tree2-> data)

- Vérifiez récursivement le sous-arbre gauche, c'est-à-dire appelez SameTree(tree1-> left_subtree, tree2-> left_subtree)

- Vérifiez récursivement le sous-arbre droit, c'est-à-dire appelez SameTree(tree1-> right_subtree , tree2-> right_subtree)

- Renvoie 1 si la valeur renvoyée dans les trois étapes ci-dessus est vraie.

3. Sinon, retournez 0 (l'un est vide et l'autre ne l'est pas).

Ce qui suit est l'implémentation de la méthode ci-dessus :

// 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; 
}

Sortie :

Both BSTs are identical

Cet article concerne la vérification de deux recherches binaires arbres La même méthode est-elle introduite ? J'espère qu'elle sera utile aux amis qui en ont besoin !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!