C++ prüft, ob zwei binäre Suchbäume gleich sind

Gegeben sind die Wurzelknoten zweier binärer Suchbäume. Wenn zwei binäre Suchbäume identisch sind, geben Sie 1 aus, andernfalls geben Sie 0 aus. Zwei Bäume sind identisch, wenn sie strukturell identisch sind und Knoten mit denselben Werten haben.

Im obigen Bild sind Baum1 und Baum2 gleich.

Um festzustellen, ob zwei Bäume gleich sind, müssen wir beide Bäume gleichzeitig durchqueren und beim Durchqueren die Daten und untergeordneten Knoten der Bäume vergleichen.

Das Folgende ist ein schrittweiser Algorithmus, um zu überprüfen, ob zwei BSTs gleich sind:

1 Wenn beide Bäume leer sind, geben Sie 1 zurück.

2. Andernfalls, wenn beide Bäume nicht leer sind

-überprüfen Sie die Daten des Wurzelknotens (Baum1-> Daten == Baum2-> Daten)

- Rekursiv den linken Teilbaum prüfen, also sameTree(tree1-> left_subtree, tree2-> left_subtree) aufrufen

- Rekursiv den rechten Teilbaum prüfen, also sameTree(tree1-> right_subtree aufrufen , tree2-> right_subtree)

– Gibt 1 zurück, wenn der in den obigen drei Schritten zurückgegebene Wert wahr ist.

3. Andernfalls wird 0 zurückgegeben (einer ist leer und der andere nicht).

Das Folgende ist die Implementierung der obigen Methode:

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

Ausgabe:

Both BSTs are identical

In diesem Artikel geht es um die Methode zur Überprüfung, ob zwei Binärsuchen durchgeführt werden Bäume sind die gleichen Einführung, ich hoffe, es wird Freunden in Not hilfreich sein!

Das obige ist der detaillierte Inhalt vonC++ prüft, ob zwei binäre Suchbäume gleich sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!