c++搜检两个二进制搜刮树是不是雷同【C#.Net教程】,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; 
}

输出：