c++如何检查两个二进制搜索树是否相同-创新互联

这篇文章将为大家详细讲解有关c++如何检查两个二进制搜索树是否相同,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

成都创新互联专注于龙华企业网站建设,成都响应式网站建设,成都做商城网站。龙华网站建设公司,为龙华等地区提供建站服务。全流程按需网站策划,专业设计,全程项目跟踪,成都创新互联专业和态度为您提供的服务

给定两个二叉搜索树的根节点。如果两个二进制搜索树是相同的,则打印1,否则打印0.如果两个树在结构上相同且节点具有相同的值,则它们是相同的。

c++如何检查两个二进制搜索树是否相同

在上面的图像中,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  
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++如何检查两个二进制搜索树是否相同就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


本文名称:c++如何检查两个二进制搜索树是否相同-创新互联
标题路径:http://scyanting.com/article/jspje.html