這篇文章將為大家詳細講解有關c++如何檢查兩個二進制搜索樹是否相同，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

專注于為中小企業提供成都網站設計、成都網站建設服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業商都免費做網站提供優質的服務。我們立足成都，凝聚了一批互聯網行業人才，有力地推動了上千企業的穩健成長，幫助中小企業通過網站建設實現規模擴充和轉變。

給定兩個二叉搜索樹的根節點。如果兩個二進制搜索樹是相同的，則打印1，否則打印0.如果兩個樹在結構上相同且節點具有相同的值，則它們是相同的。

在上面的圖像中，tree1和tree2都是相同的。

為了確定兩棵樹是否相同，我們需要同時遍歷兩棵樹，并且在遍歷時我們需要比較樹木的數據和子節點。

以下是逐步算法，以檢查兩個BST是否相同：

1.如果兩棵樹都是空的，則返回1。

2.否則，如果兩棵樹都是非空的

-檢查根節點的數據（tree1-> data == tree2-> data）

-遞歸檢查左子樹，即調用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++如何檢查兩個二進制搜索樹是否相同就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

名稱欄目：c++如何檢查兩個二進制搜索樹是否相同
轉載來于：http://m.newbst.com/article4/jesdoe.html

成都網站建設公司_創新互聯，為您提供全網營銷推廣、標簽優化、電子商務、網頁設計公司、響應式網站、營銷型網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯