C++は2つの二分探索ツリーが同じかどうかをチェックします

2 つの二分探索ツリーのルート ノードが与えられたとします。 2 つの二分探索ツリーが同一の場合は 1 を出力し、そうでない場合は 0 を出力します。構造的に同一であり、同じ値のノードを持つ 2 つのツリーは同一です。

#上の画像では、tree1 とtree2 は両方とも同じです。

2 つのツリーが同じかどうかを判断するには、両方のツリーを同時に走査する必要があり、走査中にデータとツリーの子ノードを比較する必要があります。

次は、2 つの BST が同じかどうかを確認するための段階的なアルゴリズムです:

1. 両方のツリーが空の場合は、1 を返します。

2. それ以外の場合、両方のツリーが空でない場合は

# - ルート ノードのデータを確認します (tree1-> data ==tree2-> data)

- 左側のサブツリーを再帰的にチェックします。つまり、sameTree(tree1-> left_subtree,tree2-> left_subtree) を呼び出します。

-右側のサブツリーを再帰的にチェックします。つまり、sameTree(tree1-> right_subtree を呼び出します) 、tree2-> right_subtree)

- 上記の 3 つの手順で返された値が true の場合、1 を返します。

3. それ以外の場合は 0 を返します (1 つは空で、もう 1 つは空ではありません)。

上記のメソッドの実装は次のとおりです:

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

この記事は、2 つの二分探索が正しいかどうかを確認する方法についてです。木々も同じです はじめに、困っている友達のお役に立てれば幸いです!

以上がC++は2つの二分探索ツリーが同じかどうかをチェックしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。