C++ 두 개의 이진 검색 트리가 동일한지 확인합니다.

두 개의 이진 검색 트리의 루트 노드가 주어졌습니다. 두 개의 이진 검색 트리가 동일하면 1을 인쇄하고, 그렇지 않으면 0을 인쇄합니다. 두 트리가 구조적으로 동일하고 동일한 값을 가진 노드를 갖는 경우 동일합니다.

위 이미지에서는 tree1과 tree2가 모두 동일합니다.

두 트리가 동일한지 확인하려면 두 트리를 동시에 순회해야 하며 순회하는 동안 트리의 데이터와 하위 노드를 비교해야 합니다.

두 개의 BST가 동일한지 확인하는 단계별 알고리즘은 다음과 같습니다.

1 두 트리가 모두 비어 있으면 1을 반환합니다.

2. 그렇지 않고 두 트리가 모두 비어 있지 않은 경우

- 루트 노드의 데이터를 확인합니다(tree1-> 데이터 == tree2-> 데이터)

- 왼쪽 하위 트리를 재귀적으로 확인합니다. 즉, 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!